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