media/cast/test/cast_benchmarks.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4 //
   5 // This program benchmarks the theoretical throughput of the cast library.
   6 // It runs using a fake clock, simulated network and fake codecs. This allows
   7 // tests to run much faster than real time.
   8 // To run the program, run:
   9 // $ ./out/Release/cast_benchmarks | tee benchmarkoutput.asc
  10 // This may take a while, when it is done, you can view the data with
  11 // meshlab by running:
  12 // $ meshlab benchmarkoutput.asc
  13 // After starting meshlab, turn on Render->Show Axis. The red axis will
  14 // represent bandwidth (in megabits) the blue axis will be packet drop
  15 // (in percent) and the green axis will be latency (in milliseconds).
  16 //
  17 // This program can also be used for profiling. On linux it has
  18 // built-in support for this. Simply set the environment variable
  19 // PROFILE_FILE before running it, like so:
  20 // $ export PROFILE_FILE=cast_benchmark.profile
  21 // Then after running the program, you can view the profile with:
  22 // $ pprof ./out/Release/cast_benchmarks $PROFILE_FILE --gv
  23
  24 #include <math.h>
  25 #include <stdint.h>
  26
  27 #include <map>
  28 #include <vector>
  29
  30 #include "base/at_exit.h"
  31 #include "base/bind.h"
  32 #include "base/bind_helpers.h"
  33 #include "base/command_line.h"
  34 #include "base/debug/profiler.h"
  35 #include "base/memory/weak_ptr.h"
  36 #include "base/run_loop.h"
  37 #include "base/stl_util.h"
  38 #include "base/strings/string_number_conversions.h"
  39 #include "base/strings/stringprintf.h"
  40 #include "base/test/simple_test_tick_clock.h"
  41 #include "base/threading/thread.h"
  42 #include "base/time/tick_clock.h"
  43 #include "media/base/audio_bus.h"
  44 #include "media/base/video_frame.h"
  45 #include "media/cast/cast_config.h"
  46 #include "media/cast/cast_environment.h"
  47 #include "media/cast/cast_receiver.h"
  48 #include "media/cast/cast_sender.h"
  49 #include "media/cast/logging/simple_event_subscriber.h"
  50 #include "media/cast/net/cast_transport_config.h"
  51 #include "media/cast/net/cast_transport_defines.h"
  52 #include "media/cast/net/cast_transport_sender.h"
  53 #include "media/cast/net/cast_transport_sender_impl.h"
  54 #include "media/cast/test/fake_single_thread_task_runner.h"
  55 #include "media/cast/test/loopback_transport.h"
  56 #include "media/cast/test/skewed_single_thread_task_runner.h"
  57 #include "media/cast/test/skewed_tick_clock.h"
  58 #include "media/cast/test/utility/audio_utility.h"
  59 #include "media/cast/test/utility/default_config.h"
  60 #include "media/cast/test/utility/test_util.h"
  61 #include "media/cast/test/utility/udp_proxy.h"
  62 #include "media/cast/test/utility/video_utility.h"
  63 #include "testing/gtest/include/gtest/gtest.h"
  64
  65 namespace media {
  66 namespace cast {
  67
  68 namespace {
  69
  70 static const int64 kStartMillisecond = INT64_C(1245);
  71 static const int kAudioChannels = 2;
  72 static const int kTargetPlayoutDelayMs = 300;
  73
  74 // The tests are commonly implemented with |kFrameTimerMs| RunTask function;
  75 // a normal video is 30 fps hence the 33 ms between frames.
  76 static const int kFrameTimerMs = 33;
  77
  78 void UpdateCastTransportStatus(CastTransportStatus status) {
  79   bool result = (status == TRANSPORT_AUDIO_INITIALIZED ||
  80                  status == TRANSPORT_VIDEO_INITIALIZED);
  81   EXPECT_TRUE(result);
  82 }
  83
  84 void ExpectSuccessAndRunCallback(const base::Closure& done_cb,
  85                                  OperationalStatus status) {
  86   EXPECT_EQ(STATUS_INITIALIZED, status);
  87   done_cb.Run();
  88 }
  89
  90 void IgnoreRawEvents(const std::vector<PacketEvent>& packet_events,
  91                      const std::vector<FrameEvent>& frame_events) {
  92 }
  93
  94 }  // namespace
  95
  96 // Wraps a CastTransportSender and records some statistics about
  97 // the data that goes through it.
  98 class CastTransportSenderWrapper : public CastTransportSender {
  99  public:
 100   // Takes ownership of |transport|.
 101   void Init(CastTransportSender* transport,
 102             uint64* encoded_video_bytes,
 103             uint64* encoded_audio_bytes) {
 104     transport_.reset(transport);
 105     encoded_video_bytes_ = encoded_video_bytes;
 106     encoded_audio_bytes_ = encoded_audio_bytes;
 107   }
 108
 109   void InitializeAudio(const CastTransportRtpConfig& config,
 110                        const RtcpCastMessageCallback& cast_message_cb,
 111                        const RtcpRttCallback& rtt_cb) final {
 112     audio_ssrc_ = config.ssrc;
 113     transport_->InitializeAudio(config, cast_message_cb, rtt_cb);
 114   }
 115
 116   void InitializeVideo(const CastTransportRtpConfig& config,
 117                        const RtcpCastMessageCallback& cast_message_cb,
 118                        const RtcpRttCallback& rtt_cb) final {
 119     video_ssrc_ = config.ssrc;
 120     transport_->InitializeVideo(config, cast_message_cb, rtt_cb);
 121   }
 122
 123   void InsertFrame(uint32 ssrc, const EncodedFrame& frame) final {
 124     if (ssrc == audio_ssrc_) {
 125       *encoded_audio_bytes_ += frame.data.size();
 126     } else if (ssrc == video_ssrc_) {
 127       *encoded_video_bytes_ += frame.data.size();
 128     }
 129     transport_->InsertFrame(ssrc, frame);
 130   }
 131
 132   void SendSenderReport(uint32 ssrc,
 133                         base::TimeTicks current_time,
 134                         uint32 current_time_as_rtp_timestamp) final {
 135     transport_->SendSenderReport(ssrc,
 136                                  current_time,
 137                                  current_time_as_rtp_timestamp);
 138   }
 139
 140   void CancelSendingFrames(uint32 ssrc,
 141                            const std::vector<uint32>& frame_ids) final {
 142     transport_->CancelSendingFrames(ssrc, frame_ids);
 143   }
 144
 145   void ResendFrameForKickstart(uint32 ssrc, uint32 frame_id) final {
 146     transport_->ResendFrameForKickstart(ssrc, frame_id);
 147   }
 148
 149   PacketReceiverCallback PacketReceiverForTesting() final {
 150     return transport_->PacketReceiverForTesting();
 151   }
 152
 153   void AddValidSsrc(uint32 ssrc) final {
 154     return transport_->AddValidSsrc(ssrc);
 155   }
 156
 157   void SendRtcpFromRtpReceiver(
 158       uint32 ssrc,
 159       uint32 sender_ssrc,
 160       const RtcpTimeData& time_data,
 161       const RtcpCastMessage* cast_message,
 162       base::TimeDelta target_delay,
 163       const ReceiverRtcpEventSubscriber::RtcpEvents* rtcp_events,
 164       const RtpReceiverStatistics* rtp_receiver_statistics) final {
 165     return transport_->SendRtcpFromRtpReceiver(ssrc,
 166                                                sender_ssrc,
 167                                                time_data,
 168                                                cast_message,
 169                                                target_delay,
 170                                                rtcp_events,
 171                                                rtp_receiver_statistics);
 172   }
 173
 174  private:
 175   scoped_ptr<CastTransportSender> transport_;
 176   uint32 audio_ssrc_, video_ssrc_;
 177   uint64* encoded_video_bytes_;
 178   uint64* encoded_audio_bytes_;
 179 };
 180
 181 struct MeasuringPoint {
 182   MeasuringPoint(double bitrate_, double latency_, double percent_packet_drop_)
 183       : bitrate(bitrate_),
 184         latency(latency_),
 185         percent_packet_drop(percent_packet_drop_) {}
 186   bool operator<=(const MeasuringPoint& other) const {
 187     return bitrate >= other.bitrate && latency <= other.latency &&
 188            percent_packet_drop <= other.percent_packet_drop;
 189   }
 190   bool operator>=(const MeasuringPoint& other) const {
 191     return bitrate <= other.bitrate && latency >= other.latency &&
 192            percent_packet_drop >= other.percent_packet_drop;
 193   }
 194
 195   std::string AsString() const {
 196     return base::StringPrintf(
 197         "%f Mbit/s %f ms %f %% ", bitrate, latency, percent_packet_drop);
 198   }
 199
 200   double bitrate;
 201   double latency;
 202   double percent_packet_drop;
 203 };
 204
 205 class RunOneBenchmark {
 206  public:
 207   RunOneBenchmark()
 208       : start_time_(),
 209         task_runner_(new test::FakeSingleThreadTaskRunner(&testing_clock_)),
 210         testing_clock_sender_(new test::SkewedTickClock(&testing_clock_)),
 211         task_runner_sender_(
 212             new test::SkewedSingleThreadTaskRunner(task_runner_)),
 213         testing_clock_receiver_(new test::SkewedTickClock(&testing_clock_)),
 214         task_runner_receiver_(
 215             new test::SkewedSingleThreadTaskRunner(task_runner_)),
 216         cast_environment_sender_(new CastEnvironment(
 217             scoped_ptr<base::TickClock>(testing_clock_sender_).Pass(),
 218             task_runner_sender_,
 219             task_runner_sender_,
 220             task_runner_sender_)),
 221         cast_environment_receiver_(new CastEnvironment(
 222             scoped_ptr<base::TickClock>(testing_clock_receiver_).Pass(),
 223             task_runner_receiver_,
 224             task_runner_receiver_,
 225             task_runner_receiver_)),
 226         receiver_to_sender_(cast_environment_receiver_),
 227         sender_to_receiver_(cast_environment_sender_),
 228         video_bytes_encoded_(0),
 229         audio_bytes_encoded_(0),
 230         frames_sent_(0) {
 231     testing_clock_.Advance(
 232         base::TimeDelta::FromMilliseconds(kStartMillisecond));
 233   }
 234
 235   void Configure(Codec video_codec,
 236                  Codec audio_codec,
 237                  int audio_sampling_frequency,
 238                  int max_number_of_video_buffers_used) {
 239     audio_sender_config_.ssrc = 1;
 240     audio_sender_config_.receiver_ssrc = 2;
 241     audio_sender_config_.max_playout_delay =
 242         base::TimeDelta::FromMilliseconds(kTargetPlayoutDelayMs);
 243     audio_sender_config_.rtp_payload_type = 96;
 244     audio_sender_config_.use_external_encoder = false;
 245     audio_sender_config_.frequency = audio_sampling_frequency;
 246     audio_sender_config_.channels = kAudioChannels;
 247     audio_sender_config_.bitrate = kDefaultAudioEncoderBitrate;
 248     audio_sender_config_.codec = audio_codec;
 249
 250     audio_receiver_config_.receiver_ssrc =
 251         audio_sender_config_.receiver_ssrc;
 252     audio_receiver_config_.sender_ssrc = audio_sender_config_.ssrc;
 253     audio_receiver_config_.rtp_payload_type =
 254         audio_sender_config_.rtp_payload_type;
 255     audio_receiver_config_.rtp_timebase = audio_sender_config_.frequency;
 256     audio_receiver_config_.channels = kAudioChannels;
 257     audio_receiver_config_.target_frame_rate = 100;
 258     audio_receiver_config_.codec = audio_sender_config_.codec;
 259     audio_receiver_config_.rtp_max_delay_ms = kTargetPlayoutDelayMs;
 260
 261     video_sender_config_.ssrc = 3;
 262     video_sender_config_.receiver_ssrc = 4;
 263     video_sender_config_.max_playout_delay =
 264         base::TimeDelta::FromMilliseconds(kTargetPlayoutDelayMs);
 265     video_sender_config_.rtp_payload_type = 97;
 266     video_sender_config_.use_external_encoder = false;
 267 #if 0
 268     video_sender_config_.max_bitrate = 10000000;  // 10Mbit max
 269     video_sender_config_.min_bitrate = 1000000;   // 1Mbit min
 270     video_sender_config_.start_bitrate = 1000000; // 1Mbit start
 271 #else
 272     video_sender_config_.max_bitrate = 4000000;  // 4Mbit all the time
 273     video_sender_config_.min_bitrate = 4000000;
 274     video_sender_config_.start_bitrate = 4000000;
 275 #endif
 276     video_sender_config_.max_qp = 56;
 277     video_sender_config_.min_qp = 4;
 278     video_sender_config_.max_frame_rate = 30;
 279     video_sender_config_.max_number_of_video_buffers_used =
 280         max_number_of_video_buffers_used;
 281     video_sender_config_.codec = video_codec;
 282
 283     video_receiver_config_.receiver_ssrc =
 284         video_sender_config_.receiver_ssrc;
 285     video_receiver_config_.sender_ssrc = video_sender_config_.ssrc;
 286     video_receiver_config_.rtp_payload_type =
 287         video_sender_config_.rtp_payload_type;
 288     video_receiver_config_.codec = video_sender_config_.codec;
 289     video_receiver_config_.rtp_timebase = kVideoFrequency;
 290     video_receiver_config_.channels = 1;
 291     video_receiver_config_.target_frame_rate = 100;
 292     video_receiver_config_.rtp_max_delay_ms = kTargetPlayoutDelayMs;
 293   }
 294
 295   void SetSenderClockSkew(double skew, base::TimeDelta offset) {
 296     testing_clock_sender_->SetSkew(skew, offset);
 297     task_runner_sender_->SetSkew(1.0 / skew);
 298   }
 299
 300   void SetReceiverClockSkew(double skew, base::TimeDelta offset) {
 301     testing_clock_receiver_->SetSkew(skew, offset);
 302     task_runner_receiver_->SetSkew(1.0 / skew);
 303   }
 304
 305   void Create(const MeasuringPoint& p) {
 306     net::IPEndPoint dummy_endpoint;
 307     transport_sender_.Init(
 308         new CastTransportSenderImpl(
 309             NULL,
 310             testing_clock_sender_,
 311             dummy_endpoint,
 312             dummy_endpoint,
 313             make_scoped_ptr(new base::DictionaryValue),
 314             base::Bind(&UpdateCastTransportStatus),
 315             base::Bind(&IgnoreRawEvents),
 316             base::TimeDelta::FromSeconds(1),
 317             task_runner_sender_,
 318             PacketReceiverCallback(),
 319             &sender_to_receiver_),
 320         &video_bytes_encoded_,
 321         &audio_bytes_encoded_);
 322
 323     transport_receiver_.reset(
 324         new CastTransportSenderImpl(
 325             NULL,
 326             testing_clock_receiver_,
 327             dummy_endpoint,
 328             dummy_endpoint,
 329             make_scoped_ptr(new base::DictionaryValue),
 330             base::Bind(&UpdateCastTransportStatus),
 331             base::Bind(&IgnoreRawEvents),
 332             base::TimeDelta::FromSeconds(1),
 333             task_runner_receiver_,
 334             base::Bind(&RunOneBenchmark::ReceivePacket, base::Unretained(this)),
 335             &receiver_to_sender_));
 336
 337     cast_receiver_ = CastReceiver::Create(cast_environment_receiver_,
 338                                           audio_receiver_config_,
 339                                           video_receiver_config_,
 340                                           transport_receiver_.get());
 341
 342     cast_sender_ =
 343         CastSender::Create(cast_environment_sender_, &transport_sender_);
 344
 345     // Initializing audio and video senders.  The funny dance here is to
 346     // synchronize on the asynchronous initialization process.
 347     base::RunLoop run_loop;
 348     base::WeakPtrFactory<RunOneBenchmark> weak_factory(this);
 349     cast_sender_->InitializeAudio(
 350         audio_sender_config_,
 351         base::Bind(&ExpectSuccessAndRunCallback, run_loop.QuitClosure()));
 352     run_loop.Run();  // Wait for quit closure to run.
 353     weak_factory.InvalidateWeakPtrs();
 354     cast_sender_->InitializeVideo(
 355         video_sender_config_,
 356         base::Bind(&ExpectSuccessAndRunCallback, run_loop.QuitClosure()),
 357         CreateDefaultVideoEncodeAcceleratorCallback(),
 358         CreateDefaultVideoEncodeMemoryCallback());
 359     run_loop.Run();  // Wait for quit closure to run.
 360     weak_factory.InvalidateWeakPtrs();
 361
 362     receiver_to_sender_.Initialize(
 363         CreateSimplePipe(p).Pass(),
 364         transport_sender_.PacketReceiverForTesting(),
 365         task_runner_, &testing_clock_);
 366     sender_to_receiver_.Initialize(
 367         CreateSimplePipe(p).Pass(),
 368         transport_receiver_->PacketReceiverForTesting(),
 369         task_runner_, &testing_clock_);
 370   }
 371
 372   void ReceivePacket(scoped_ptr<Packet> packet) {
 373     cast_receiver_->ReceivePacket(packet.Pass());
 374   }
 375
 376   virtual ~RunOneBenchmark() {
 377     cast_sender_.reset();
 378     cast_receiver_.reset();
 379     task_runner_->RunTasks();
 380   }
 381
 382   void SendFakeVideoFrame() {
 383     frames_sent_++;
 384     cast_sender_->video_frame_input()->InsertRawVideoFrame(
 385         media::VideoFrame::CreateBlackFrame(gfx::Size(2, 2)),
 386         testing_clock_sender_->NowTicks());
 387   }
 388
 389   void RunTasks(int ms) {
 390     task_runner_->Sleep(base::TimeDelta::FromMilliseconds(ms));
 391   }
 392
 393   void BasicPlayerGotVideoFrame(
 394       const scoped_refptr<media::VideoFrame>& video_frame,
 395       const base::TimeTicks& render_time,
 396       bool continuous) {
 397     video_ticks_.push_back(
 398         std::make_pair(testing_clock_receiver_->NowTicks(), render_time));
 399     cast_receiver_->RequestDecodedVideoFrame(base::Bind(
 400         &RunOneBenchmark::BasicPlayerGotVideoFrame, base::Unretained(this)));
 401   }
 402
 403   void BasicPlayerGotAudioFrame(scoped_ptr<AudioBus> audio_bus,
 404                                 const base::TimeTicks& playout_time,
 405                                 bool is_continuous) {
 406     audio_ticks_.push_back(
 407         std::make_pair(testing_clock_receiver_->NowTicks(), playout_time));
 408     cast_receiver_->RequestDecodedAudioFrame(base::Bind(
 409         &RunOneBenchmark::BasicPlayerGotAudioFrame, base::Unretained(this)));
 410   }
 411
 412   void StartBasicPlayer() {
 413     cast_receiver_->RequestDecodedVideoFrame(base::Bind(
 414         &RunOneBenchmark::BasicPlayerGotVideoFrame, base::Unretained(this)));
 415     cast_receiver_->RequestDecodedAudioFrame(base::Bind(
 416         &RunOneBenchmark::BasicPlayerGotAudioFrame, base::Unretained(this)));
 417   }
 418
 419   scoped_ptr<test::PacketPipe> CreateSimplePipe(const MeasuringPoint& p) {
 420     scoped_ptr<test::PacketPipe> pipe = test::NewBuffer(65536, p.bitrate);
 421     pipe->AppendToPipe(
 422         test::NewRandomDrop(p.percent_packet_drop / 100.0).Pass());
 423     pipe->AppendToPipe(test::NewConstantDelay(p.latency / 1000.0));
 424     return pipe.Pass();
 425   }
 426
 427   void Run(const MeasuringPoint& p) {
 428     available_bitrate_ = p.bitrate;
 429     Configure(
 430         CODEC_VIDEO_FAKE, CODEC_AUDIO_PCM16, 32000, 1);
 431     Create(p);
 432     StartBasicPlayer();
 433
 434     for (int frame = 0; frame < 1000; frame++) {
 435       SendFakeVideoFrame();
 436       RunTasks(kFrameTimerMs);
 437     }
 438     RunTasks(100 * kFrameTimerMs);  // Empty the pipeline.
 439     VLOG(1) << "=============INPUTS============";
 440     VLOG(1) << "Bitrate: " << p.bitrate << " mbit/s";
 441     VLOG(1) << "Latency: " << p.latency << " ms";
 442     VLOG(1) << "Packet drop drop: " << p.percent_packet_drop << "%";
 443     VLOG(1) << "=============OUTPUTS============";
 444     VLOG(1) << "Frames lost: " << frames_lost();
 445     VLOG(1) << "Late frames: " << late_frames();
 446     VLOG(1) << "Playout margin: " << frame_playout_buffer().AsString();
 447     VLOG(1) << "Video bandwidth used: " << video_bandwidth() << " mbit/s ("
 448             << (video_bandwidth() * 100 / desired_video_bitrate()) << "%)";
 449     VLOG(1) << "Good run: " << SimpleGood();
 450   }
 451
 452   // Metrics
 453   int frames_lost() const { return frames_sent_ - video_ticks_.size(); }
 454
 455   int late_frames() const {
 456     int frames = 0;
 457     // Ignore the first two seconds of video or so.
 458     for (size_t i = 60; i < video_ticks_.size(); i++) {
 459       if (video_ticks_[i].first > video_ticks_[i].second) {
 460         frames++;
 461       }
 462     }
 463     return frames;
 464   }
 465
 466   test::MeanAndError frame_playout_buffer() const {
 467     std::vector<double> values;
 468     for (size_t i = 0; i < video_ticks_.size(); i++) {
 469       values.push_back(
 470           (video_ticks_[i].second - video_ticks_[i].first).InMillisecondsF());
 471     }
 472     return test::MeanAndError(values);
 473   }
 474
 475   // Mbits per second
 476   double video_bandwidth() const {
 477     double seconds = (kFrameTimerMs * frames_sent_ / 1000.0);
 478     double megabits = video_bytes_encoded_ * 8 / 1000000.0;
 479     return megabits / seconds;
 480   }
 481
 482   // Mbits per second
 483   double audio_bandwidth() const {
 484     double seconds = (kFrameTimerMs * frames_sent_ / 1000.0);
 485     double megabits = audio_bytes_encoded_ * 8 / 1000000.0;
 486     return megabits / seconds;
 487   }
 488
 489   double desired_video_bitrate() {
 490     return std::min<double>(available_bitrate_,
 491                             video_sender_config_.max_bitrate / 1000000.0);
 492   }
 493
 494   bool SimpleGood() {
 495     return frames_lost() <= 1 && late_frames() <= 1 &&
 496            video_bandwidth() > desired_video_bitrate() * 0.8 &&
 497            video_bandwidth() < desired_video_bitrate() * 1.2;
 498   }
 499
 500  private:
 501   FrameReceiverConfig audio_receiver_config_;
 502   FrameReceiverConfig video_receiver_config_;
 503   AudioSenderConfig audio_sender_config_;
 504   VideoSenderConfig video_sender_config_;
 505
 506   base::TimeTicks start_time_;
 507
 508   // These run in "test time"
 509   base::SimpleTestTickClock testing_clock_;
 510   scoped_refptr<test::FakeSingleThreadTaskRunner> task_runner_;
 511
 512   // These run on the sender timeline.
 513   test::SkewedTickClock* testing_clock_sender_;
 514   scoped_refptr<test::SkewedSingleThreadTaskRunner> task_runner_sender_;
 515
 516   // These run on the receiver timeline.
 517   test::SkewedTickClock* testing_clock_receiver_;
 518   scoped_refptr<test::SkewedSingleThreadTaskRunner> task_runner_receiver_;
 519
 520   scoped_refptr<CastEnvironment> cast_environment_sender_;
 521   scoped_refptr<CastEnvironment> cast_environment_receiver_;
 522
 523   LoopBackTransport receiver_to_sender_;
 524   LoopBackTransport sender_to_receiver_;
 525   CastTransportSenderWrapper transport_sender_;
 526   scoped_ptr<CastTransportSender> transport_receiver_;
 527   uint64 video_bytes_encoded_;
 528   uint64 audio_bytes_encoded_;
 529
 530   scoped_ptr<CastReceiver> cast_receiver_;
 531   scoped_ptr<CastSender> cast_sender_;
 532
 533   int frames_sent_;
 534   double available_bitrate_;
 535   std::vector<std::pair<base::TimeTicks, base::TimeTicks> > audio_ticks_;
 536   std::vector<std::pair<base::TimeTicks, base::TimeTicks> > video_ticks_;
 537 };
 538
 539 enum CacheResult { FOUND_TRUE, FOUND_FALSE, NOT_FOUND };
 540
 541 template <class T>
 542 class BenchmarkCache {
 543  public:
 544   CacheResult Lookup(const T& x) {
 545     base::AutoLock key(lock_);
 546     for (size_t i = 0; i < results_.size(); i++) {
 547       if (results_[i].second) {
 548         if (x <= results_[i].first) {
 549           VLOG(2) << "TRUE because: " << x.AsString()
 550                   << " <= " << results_[i].first.AsString();
 551           return FOUND_TRUE;
 552         }
 553       } else {
 554         if (x >= results_[i].first) {
 555           VLOG(2) << "FALSE because: " << x.AsString()
 556                   << " >= " << results_[i].first.AsString();
 557           return FOUND_FALSE;
 558         }
 559       }
 560     }
 561     return NOT_FOUND;
 562   }
 563
 564   void Add(const T& x, bool result) {
 565     base::AutoLock key(lock_);
 566     VLOG(2) << "Cache Insert: " << x.AsString() << " = " << result;
 567     results_.push_back(std::make_pair(x, result));
 568   }
 569
 570  private:
 571   base::Lock lock_;
 572   std::vector<std::pair<T, bool> > results_;
 573 };
 574
 575 struct SearchVariable {
 576   SearchVariable() : base(0.0), grade(0.0) {}
 577   SearchVariable(double b, double g) : base(b), grade(g) {}
 578   SearchVariable blend(const SearchVariable& other, double factor) {
 579     CHECK_GE(factor, 0);
 580     CHECK_LE(factor, 1.0);
 581     return SearchVariable(base * (1 - factor) + other.base * factor,
 582                           grade * (1 - factor) + other.grade * factor);
 583   }
 584   double value(double x) const { return base + grade * x; }
 585   double base;
 586   double grade;
 587 };
 588
 589 struct SearchVector {
 590   SearchVector blend(const SearchVector& other, double factor) {
 591     SearchVector ret;
 592     ret.bitrate = bitrate.blend(other.bitrate, factor);
 593     ret.latency = latency.blend(other.latency, factor);
 594     ret.packet_drop = packet_drop.blend(other.packet_drop, factor);
 595     return ret;
 596   }
 597
 598   SearchVector average(const SearchVector& other) {
 599     return blend(other, 0.5);
 600   }
 601
 602   MeasuringPoint GetMeasuringPoint(double v) const {
 603     return MeasuringPoint(
 604         bitrate.value(-v), latency.value(v), packet_drop.value(v));
 605   }
 606   std::string AsString(double v) { return GetMeasuringPoint(v).AsString(); }
 607
 608   SearchVariable bitrate;
 609   SearchVariable latency;
 610   SearchVariable packet_drop;
 611 };
 612
 613 class CastBenchmark {
 614  public:
 615   bool RunOnePoint(const SearchVector& v, double multiplier) {
 616     MeasuringPoint p = v.GetMeasuringPoint(multiplier);
 617     VLOG(1) << "RUN: v = " << multiplier << " p = " << p.AsString();
 618     if (p.bitrate <= 0) {
 619       return false;
 620     }
 621     switch (cache_.Lookup(p)) {
 622       case FOUND_TRUE:
 623         return true;
 624       case FOUND_FALSE:
 625         return false;
 626       case NOT_FOUND:
 627         // Keep going
 628         break;
 629     }
 630     bool result = true;
 631     for (int tries = 0; tries < 3 && result; tries++) {
 632       RunOneBenchmark benchmark;
 633       benchmark.Run(p);
 634       result &= benchmark.SimpleGood();
 635     }
 636     cache_.Add(p, result);
 637     return result;
 638   }
 639
 640   void BinarySearch(SearchVector v, double accuracy) {
 641     double min = 0.0;
 642     double max = 1.0;
 643     while (RunOnePoint(v, max)) {
 644       min = max;
 645       max *= 2;
 646     }
 647
 648     while (max - min > accuracy) {
 649       double avg = (min + max) / 2;
 650       if (RunOnePoint(v, avg)) {
 651         min = avg;
 652       } else {
 653         max = avg;
 654       }
 655     }
 656
 657     // Print a data point to stdout.
 658     base::AutoLock key(lock_);
 659     MeasuringPoint p = v.GetMeasuringPoint(min);
 660     fprintf(stdout, "%f %f %f\n", p.bitrate, p.latency, p.percent_packet_drop);
 661     fflush(stdout);
 662   }
 663
 664   void SpanningSearch(int max,
 665                       int x,
 666                       int y,
 667                       int skip,
 668                       SearchVector a,
 669                       SearchVector b,
 670                       SearchVector c,
 671                       double accuracy,
 672                       std::vector<linked_ptr<base::Thread> >* threads) {
 673     static int thread_num = 0;
 674     if (x > max) return;
 675     if (skip > max) {
 676       if (y > x) return;
 677       SearchVector ab = a.blend(b, static_cast<double>(x) / max);
 678       SearchVector ac = a.blend(c, static_cast<double>(x) / max);
 679       SearchVector v = ab.blend(ac, x == y ? 1.0 : static_cast<double>(y) / x);
 680       thread_num++;
 681       (*threads)[thread_num % threads->size()]->message_loop()->PostTask(
 682           FROM_HERE,
 683           base::Bind(&CastBenchmark::BinarySearch,
 684                      base::Unretained(this),
 685                      v,
 686                      accuracy));
 687     } else {
 688       skip *= 2;
 689       SpanningSearch(max, x, y, skip, a, b, c, accuracy, threads);
 690       SpanningSearch(max, x + skip, y + skip, skip, a, b, c, accuracy, threads);
 691       SpanningSearch(max, x + skip, y, skip, a, b, c, accuracy, threads);
 692       SpanningSearch(max, x, y + skip, skip, a, b, c, accuracy, threads);
 693     }
 694   }
 695
 696   void Run() {
 697     // Spanning search.
 698
 699     std::vector<linked_ptr<base::Thread> > threads;
 700     for (int i = 0; i < 16; i++) {
 701       threads.push_back(make_linked_ptr(new base::Thread(
 702           base::StringPrintf("cast_bench_thread_%d", i))));
 703       threads[i]->Start();
 704     }
 705
 706     if (base::CommandLine::ForCurrentProcess()->HasSwitch("single-run")) {
 707       SearchVector a;
 708       a.bitrate.base = 100.0;
 709       a.bitrate.grade = 1.0;
 710       a.latency.grade = 1.0;
 711       a.packet_drop.grade = 1.0;
 712       threads[0]->message_loop()->PostTask(
 713           FROM_HERE,
 714           base::Bind(base::IgnoreResult(&CastBenchmark::RunOnePoint),
 715                      base::Unretained(this),
 716                      a,
 717                      1.0));
 718     } else {
 719       SearchVector a, b, c;
 720       a.bitrate.base = b.bitrate.base = c.bitrate.base = 100.0;
 721       a.bitrate.grade = 1.0;
 722       b.latency.grade = 1.0;
 723       c.packet_drop.grade = 1.0;
 724
 725       SpanningSearch(512,
 726                      0,
 727                      0,
 728                      1,
 729                      a,
 730                      b,
 731                      c,
 732                      0.01,
 733                      &threads);
 734     }
 735
 736     for (size_t i = 0; i < threads.size(); i++) {
 737       threads[i]->Stop();
 738     }
 739   }
 740
 741  private:
 742   BenchmarkCache<MeasuringPoint> cache_;
 743   base::Lock lock_;
 744 };
 745
 746 }  // namespace cast
 747 }  // namespace media
 748
 749 int main(int argc, char** argv) {
 750   base::AtExitManager at_exit;
 751   base::CommandLine::Init(argc, argv);
 752   media::cast::CastBenchmark benchmark;
 753   if (getenv("PROFILE_FILE")) {
 754     std::string profile_file(getenv("PROFILE_FILE"));
 755     base::debug::StartProfiling(profile_file);
 756     benchmark.Run();
 757     base::debug::StopProfiling();
 758   } else {
 759     benchmark.Run();
 760   }
 761 }