src/third_party/webrtc/video_engine/overuse_frame_detector.cc

   1 /*
   2  *  Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license
   5  *  that can be found in the LICENSE file in the root of the source
   6  *  tree. An additional intellectual property rights grant can be found
   7  *  in the file PATENTS.  All contributing project authors may
   8  *  be found in the AUTHORS file in the root of the source tree.
   9  */
  10
  11 #include "webrtc/video_engine/overuse_frame_detector.h"
  12
  13 #include <assert.h>
  14 #include <math.h>
  15
  16 #include <algorithm>
  17 #include <list>
  18 #include <map>
  19
  20 #include "webrtc/base/exp_filter.h"
  21 #include "webrtc/system_wrappers/interface/clock.h"
  22 #include "webrtc/system_wrappers/interface/critical_section_wrapper.h"
  23 #include "webrtc/system_wrappers/interface/logging.h"
  24
  25 namespace webrtc {
  26
  27 // TODO(mflodman) Test different values for all of these to trigger correctly,
  28 // avoid fluctuations etc.
  29 namespace {
  30 const int64_t kProcessIntervalMs = 5000;
  31
  32 // Weight factor to apply to the standard deviation.
  33 const float kWeightFactor = 0.997f;
  34 // Weight factor to apply to the average.
  35 const float kWeightFactorMean = 0.98f;
  36
  37 // Delay between consecutive rampups. (Used for quick recovery.)
  38 const int kQuickRampUpDelayMs = 10 * 1000;
  39 // Delay between rampup attempts. Initially uses standard, scales up to max.
  40 const int kStandardRampUpDelayMs = 40 * 1000;
  41 const int kMaxRampUpDelayMs = 240 * 1000;
  42 // Expontential back-off factor, to prevent annoying up-down behaviour.
  43 const double kRampUpBackoffFactor = 2.0;
  44
  45 // Max number of overuses detected before always applying the rampup delay.
  46 const int kMaxOverusesBeforeApplyRampupDelay = 4;
  47
  48 // The maximum exponent to use in VCMExpFilter.
  49 const float kSampleDiffMs = 33.0f;
  50 const float kMaxExp = 7.0f;
  51
  52 }  // namespace
  53
  54 Statistics::Statistics() :
  55     sum_(0.0),
  56     count_(0),
  57     filtered_samples_(new rtc::ExpFilter(kWeightFactorMean)),
  58     filtered_variance_(new rtc::ExpFilter(kWeightFactor)) {
  59   Reset();
  60 }
  61
  62 void Statistics::SetOptions(const CpuOveruseOptions& options) {
  63   options_ = options;
  64 }
  65
  66 void Statistics::Reset() {
  67   sum_ =  0.0;
  68   count_ = 0;
  69   filtered_variance_->Reset(kWeightFactor);
  70   filtered_variance_->Apply(1.0f, InitialVariance());
  71 }
  72
  73 void Statistics::AddSample(float sample_ms) {
  74   sum_ += sample_ms;
  75   ++count_;
  76
  77   if (count_ < static_cast<uint32_t>(options_.min_frame_samples)) {
  78     // Initialize filtered samples.
  79     filtered_samples_->Reset(kWeightFactorMean);
  80     filtered_samples_->Apply(1.0f, InitialMean());
  81     return;
  82   }
  83
  84   float exp = sample_ms / kSampleDiffMs;
  85   exp = std::min(exp, kMaxExp);
  86   filtered_samples_->Apply(exp, sample_ms);
  87   filtered_variance_->Apply(exp, (sample_ms - filtered_samples_->filtered()) *
  88                                  (sample_ms - filtered_samples_->filtered()));
  89 }
  90
  91 float Statistics::InitialMean() const {
  92   if (count_ == 0)
  93     return 0.0;
  94   return sum_ / count_;
  95 }
  96
  97 float Statistics::InitialVariance() const {
  98   // Start in between the underuse and overuse threshold.
  99   float average_stddev = (options_.low_capture_jitter_threshold_ms +
 100                           options_.high_capture_jitter_threshold_ms) / 2.0f;
 101   return average_stddev * average_stddev;
 102 }
 103
 104 float Statistics::Mean() const { return filtered_samples_->filtered(); }
 105
 106 float Statistics::StdDev() const {
 107   return sqrt(std::max(filtered_variance_->filtered(), 0.0f));
 108 }
 109
 110 uint64_t Statistics::Count() const { return count_; }
 111
 112
 113 // Class for calculating the average encode time.
 114 class OveruseFrameDetector::EncodeTimeAvg {
 115  public:
 116   EncodeTimeAvg()
 117       : kWeightFactor(0.5f),
 118         kInitialAvgEncodeTimeMs(5.0f),
 119         filtered_encode_time_ms_(new rtc::ExpFilter(kWeightFactor)) {
 120     filtered_encode_time_ms_->Apply(1.0f, kInitialAvgEncodeTimeMs);
 121   }
 122   ~EncodeTimeAvg() {}
 123
 124   void AddEncodeSample(float encode_time_ms, int64_t diff_last_sample_ms) {
 125     float exp =  diff_last_sample_ms / kSampleDiffMs;
 126     exp = std::min(exp, kMaxExp);
 127     filtered_encode_time_ms_->Apply(exp, encode_time_ms);
 128   }
 129
 130   int Value() const {
 131     return static_cast<int>(filtered_encode_time_ms_->filtered() + 0.5);
 132   }
 133
 134  private:
 135   const float kWeightFactor;
 136   const float kInitialAvgEncodeTimeMs;
 137   scoped_ptr<rtc::ExpFilter> filtered_encode_time_ms_;
 138 };
 139
 140 // Class for calculating the encode usage.
 141 class OveruseFrameDetector::EncodeUsage {
 142  public:
 143   EncodeUsage()
 144       : kWeightFactorFrameDiff(0.998f),
 145         kWeightFactorEncodeTime(0.995f),
 146         kInitialSampleDiffMs(40.0f),
 147         kMaxSampleDiffMs(45.0f),
 148         count_(0),
 149         filtered_encode_time_ms_(new rtc::ExpFilter(kWeightFactorEncodeTime)),
 150         filtered_frame_diff_ms_(new rtc::ExpFilter(kWeightFactorFrameDiff)) {
 151     Reset();
 152   }
 153   ~EncodeUsage() {}
 154
 155   void SetOptions(const CpuOveruseOptions& options) {
 156     options_ = options;
 157   }
 158
 159   void Reset() {
 160     count_ = 0;
 161     filtered_frame_diff_ms_->Reset(kWeightFactorFrameDiff);
 162     filtered_frame_diff_ms_->Apply(1.0f, kInitialSampleDiffMs);
 163     filtered_encode_time_ms_->Reset(kWeightFactorEncodeTime);
 164     filtered_encode_time_ms_->Apply(1.0f, InitialEncodeTimeMs());
 165   }
 166
 167   void AddSample(float sample_ms) {
 168     float exp = sample_ms / kSampleDiffMs;
 169     exp = std::min(exp, kMaxExp);
 170     filtered_frame_diff_ms_->Apply(exp, sample_ms);
 171   }
 172
 173   void AddEncodeSample(float encode_time_ms, int64_t diff_last_sample_ms) {
 174     ++count_;
 175     float exp = diff_last_sample_ms / kSampleDiffMs;
 176     exp = std::min(exp, kMaxExp);
 177     filtered_encode_time_ms_->Apply(exp, encode_time_ms);
 178   }
 179
 180   int Value() const {
 181     if (count_ < static_cast<uint32_t>(options_.min_frame_samples)) {
 182       return static_cast<int>(InitialUsageInPercent() + 0.5f);
 183     }
 184     float frame_diff_ms = std::max(filtered_frame_diff_ms_->filtered(), 1.0f);
 185     frame_diff_ms = std::min(frame_diff_ms, kMaxSampleDiffMs);
 186     float encode_usage_percent =
 187         100.0f * filtered_encode_time_ms_->filtered() / frame_diff_ms;
 188     return static_cast<int>(encode_usage_percent + 0.5);
 189   }
 190
 191  private:
 192   float InitialUsageInPercent() const {
 193     // Start in between the underuse and overuse threshold.
 194     return (options_.low_encode_usage_threshold_percent +
 195             options_.high_encode_usage_threshold_percent) / 2.0f;
 196   }
 197
 198   float InitialEncodeTimeMs() const {
 199     return InitialUsageInPercent() * kInitialSampleDiffMs / 100;
 200   }
 201
 202   const float kWeightFactorFrameDiff;
 203   const float kWeightFactorEncodeTime;
 204   const float kInitialSampleDiffMs;
 205   const float kMaxSampleDiffMs;
 206   uint64_t count_;
 207   CpuOveruseOptions options_;
 208   scoped_ptr<rtc::ExpFilter> filtered_encode_time_ms_;
 209   scoped_ptr<rtc::ExpFilter> filtered_frame_diff_ms_;
 210 };
 211
 212 // Class for calculating the relative standard deviation of encode times.
 213 class OveruseFrameDetector::EncodeTimeRsd {
 214  public:
 215   EncodeTimeRsd(Clock* clock)
 216       : kWeightFactor(0.6f),
 217         count_(0),
 218         filtered_rsd_(new rtc::ExpFilter(kWeightFactor)),
 219         hist_samples_(0),
 220         hist_sum_(0.0f),
 221         last_process_time_ms_(clock->TimeInMilliseconds()) {
 222     Reset();
 223   }
 224   ~EncodeTimeRsd() {}
 225
 226   void SetOptions(const CpuOveruseOptions& options) {
 227     options_ = options;
 228   }
 229
 230   void Reset() {
 231     count_ = 0;
 232     filtered_rsd_->Reset(kWeightFactor);
 233     filtered_rsd_->Apply(1.0f, InitialValue());
 234     hist_.clear();
 235     hist_samples_ = 0;
 236     hist_sum_ = 0.0f;
 237   }
 238
 239   void AddEncodeSample(float encode_time_ms) {
 240     int bin = static_cast<int>(encode_time_ms + 0.5f);
 241     if (bin <= 0) {
 242       // The frame was probably not encoded, skip possible dropped frame.
 243       return;
 244     }
 245     ++count_;
 246     ++hist_[bin];
 247     ++hist_samples_;
 248     hist_sum_ += bin;
 249   }
 250
 251   void Process(int64_t now) {
 252     if (count_ < static_cast<uint32_t>(options_.min_frame_samples)) {
 253       // Have not received min number of frames since last reset.
 254       return;
 255     }
 256     const int kMinHistSamples = 20;
 257     if (hist_samples_ < kMinHistSamples) {
 258       return;
 259     }
 260     const int64_t kMinDiffSinceLastProcessMs = 1000;
 261     int64_t diff_last_process_ms = now - last_process_time_ms_;
 262     if (now - last_process_time_ms_ <= kMinDiffSinceLastProcessMs) {
 263       return;
 264     }
 265     last_process_time_ms_ = now;
 266
 267     // Calculate variance (using samples above the mean).
 268     // Checks for a larger encode time of some frames while there is a small
 269     // increase in the average time.
 270     int mean = hist_sum_ / hist_samples_;
 271     float variance = 0.0f;
 272     int total_count = 0;
 273     for (std::map<int,int>::iterator it = hist_.begin();
 274          it != hist_.end(); ++it) {
 275       int time = it->first;
 276       int count = it->second;
 277       if (time > mean) {
 278         total_count += count;
 279         for (int i = 0; i < count; ++i) {
 280           variance += ((time - mean) * (time - mean));
 281         }
 282       }
 283     }
 284     variance /= std::max(total_count, 1);
 285     float cov = sqrt(variance) / mean;
 286
 287     hist_.clear();
 288     hist_samples_ = 0;
 289     hist_sum_ = 0.0f;
 290
 291     float exp = static_cast<float>(diff_last_process_ms) / kProcessIntervalMs;
 292     exp = std::min(exp, kMaxExp);
 293     filtered_rsd_->Apply(exp, 100.0f * cov);
 294   }
 295
 296   int Value() const {
 297     return static_cast<int>(filtered_rsd_->filtered() + 0.5);
 298   }
 299
 300  private:
 301   float InitialValue() const {
 302     // Start in between the underuse and overuse threshold.
 303     return std::max(((options_.low_encode_time_rsd_threshold +
 304                       options_.high_encode_time_rsd_threshold) / 2.0f), 0.0f);
 305   }
 306
 307   const float kWeightFactor;
 308   uint32_t count_;  // Number of encode samples since last reset.
 309   CpuOveruseOptions options_;
 310   scoped_ptr<rtc::ExpFilter> filtered_rsd_;
 311   int hist_samples_;
 312   float hist_sum_;
 313   std::map<int,int> hist_;  // Histogram of encode time of frames.
 314   int64_t last_process_time_ms_;
 315 };
 316
 317 // Class for calculating the capture queue delay change.
 318 class OveruseFrameDetector::CaptureQueueDelay {
 319  public:
 320   CaptureQueueDelay()
 321       : kWeightFactor(0.5f),
 322         delay_ms_(0),
 323         filtered_delay_ms_per_s_(new rtc::ExpFilter(kWeightFactor)) {
 324     filtered_delay_ms_per_s_->Apply(1.0f, 0.0f);
 325   }
 326   ~CaptureQueueDelay() {}
 327
 328   void FrameCaptured(int64_t now) {
 329     const size_t kMaxSize = 200;
 330     if (frames_.size() > kMaxSize) {
 331       frames_.pop_front();
 332     }
 333     frames_.push_back(now);
 334   }
 335
 336   void FrameProcessingStarted(int64_t now) {
 337     if (frames_.empty()) {
 338       return;
 339     }
 340     delay_ms_ = now - frames_.front();
 341     frames_.pop_front();
 342   }
 343
 344   void CalculateDelayChange(int64_t diff_last_sample_ms) {
 345     if (diff_last_sample_ms <= 0) {
 346       return;
 347     }
 348     float exp = static_cast<float>(diff_last_sample_ms) / kProcessIntervalMs;
 349     exp = std::min(exp, kMaxExp);
 350     filtered_delay_ms_per_s_->Apply(exp,
 351                                     delay_ms_ * 1000.0f / diff_last_sample_ms);
 352     ClearFrames();
 353   }
 354
 355   void ClearFrames() {
 356     frames_.clear();
 357   }
 358
 359   int delay_ms() const {
 360     return delay_ms_;
 361   }
 362
 363   int Value() const {
 364     return static_cast<int>(filtered_delay_ms_per_s_->filtered() + 0.5);
 365   }
 366
 367  private:
 368   const float kWeightFactor;
 369   std::list<int64_t> frames_;
 370   int delay_ms_;
 371   scoped_ptr<rtc::ExpFilter> filtered_delay_ms_per_s_;
 372 };
 373
 374 OveruseFrameDetector::OveruseFrameDetector(Clock* clock)
 375     : crit_(CriticalSectionWrapper::CreateCriticalSection()),
 376       observer_(NULL),
 377       clock_(clock),
 378       next_process_time_(clock_->TimeInMilliseconds()),
 379       num_process_times_(0),
 380       last_capture_time_(0),
 381       last_overuse_time_(0),
 382       checks_above_threshold_(0),
 383       num_overuse_detections_(0),
 384       last_rampup_time_(0),
 385       in_quick_rampup_(false),
 386       current_rampup_delay_ms_(kStandardRampUpDelayMs),
 387       num_pixels_(0),
 388       last_encode_sample_ms_(0),
 389       encode_time_(new EncodeTimeAvg()),
 390       encode_rsd_(new EncodeTimeRsd(clock)),
 391       encode_usage_(new EncodeUsage()),
 392       capture_queue_delay_(new CaptureQueueDelay()) {
 393 }
 394
 395 OveruseFrameDetector::~OveruseFrameDetector() {
 396 }
 397
 398 void OveruseFrameDetector::SetObserver(CpuOveruseObserver* observer) {
 399   CriticalSectionScoped cs(crit_.get());
 400   observer_ = observer;
 401 }
 402
 403 void OveruseFrameDetector::SetOptions(const CpuOveruseOptions& options) {
 404   assert(options.min_frame_samples > 0);
 405   CriticalSectionScoped cs(crit_.get());
 406   if (options_.Equals(options)) {
 407     return;
 408   }
 409   options_ = options;
 410   capture_deltas_.SetOptions(options);
 411   encode_usage_->SetOptions(options);
 412   encode_rsd_->SetOptions(options);
 413   ResetAll(num_pixels_);
 414 }
 415
 416 int OveruseFrameDetector::CaptureQueueDelayMsPerS() const {
 417   CriticalSectionScoped cs(crit_.get());
 418   return capture_queue_delay_->delay_ms();
 419 }
 420
 421 void OveruseFrameDetector::GetCpuOveruseMetrics(
 422     CpuOveruseMetrics* metrics) const {
 423   CriticalSectionScoped cs(crit_.get());
 424   metrics->capture_jitter_ms = static_cast<int>(capture_deltas_.StdDev() + 0.5);
 425   metrics->avg_encode_time_ms = encode_time_->Value();
 426   metrics->encode_rsd = encode_rsd_->Value();
 427   metrics->encode_usage_percent = encode_usage_->Value();
 428   metrics->capture_queue_delay_ms_per_s = capture_queue_delay_->Value();
 429 }
 430
 431 int32_t OveruseFrameDetector::TimeUntilNextProcess() {
 432   CriticalSectionScoped cs(crit_.get());
 433   return next_process_time_ - clock_->TimeInMilliseconds();
 434 }
 435
 436 bool OveruseFrameDetector::FrameSizeChanged(int num_pixels) const {
 437   if (num_pixels != num_pixels_) {
 438     return true;
 439   }
 440   return false;
 441 }
 442
 443 bool OveruseFrameDetector::FrameTimeoutDetected(int64_t now) const {
 444   if (last_capture_time_ == 0) {
 445     return false;
 446   }
 447   return (now - last_capture_time_) > options_.frame_timeout_interval_ms;
 448 }
 449
 450 void OveruseFrameDetector::ResetAll(int num_pixels) {
 451   num_pixels_ = num_pixels;
 452   capture_deltas_.Reset();
 453   encode_usage_->Reset();
 454   encode_rsd_->Reset();
 455   capture_queue_delay_->ClearFrames();
 456   last_capture_time_ = 0;
 457   num_process_times_ = 0;
 458 }
 459
 460 void OveruseFrameDetector::FrameCaptured(int width, int height) {
 461   CriticalSectionScoped cs(crit_.get());
 462
 463   int64_t now = clock_->TimeInMilliseconds();
 464   if (FrameSizeChanged(width * height) || FrameTimeoutDetected(now)) {
 465     ResetAll(width * height);
 466   }
 467
 468   if (last_capture_time_ != 0) {
 469     capture_deltas_.AddSample(now - last_capture_time_);
 470     encode_usage_->AddSample(now - last_capture_time_);
 471   }
 472   last_capture_time_ = now;
 473
 474   capture_queue_delay_->FrameCaptured(now);
 475 }
 476
 477 void OveruseFrameDetector::FrameProcessingStarted() {
 478   CriticalSectionScoped cs(crit_.get());
 479   capture_queue_delay_->FrameProcessingStarted(clock_->TimeInMilliseconds());
 480 }
 481
 482 void OveruseFrameDetector::FrameEncoded(int encode_time_ms) {
 483   CriticalSectionScoped cs(crit_.get());
 484   int64_t time = clock_->TimeInMilliseconds();
 485   if (last_encode_sample_ms_ != 0) {
 486     int64_t diff_ms = time - last_encode_sample_ms_;
 487     encode_time_->AddEncodeSample(encode_time_ms, diff_ms);
 488     encode_usage_->AddEncodeSample(encode_time_ms, diff_ms);
 489     encode_rsd_->AddEncodeSample(encode_time_ms);
 490   }
 491   last_encode_sample_ms_ = time;
 492 }
 493
 494 int32_t OveruseFrameDetector::Process() {
 495   CriticalSectionScoped cs(crit_.get());
 496
 497   int64_t now = clock_->TimeInMilliseconds();
 498
 499   // Used to protect against Process() being called too often.
 500   if (now < next_process_time_)
 501     return 0;
 502
 503   int64_t diff_ms = now - next_process_time_ + kProcessIntervalMs;
 504   next_process_time_ = now + kProcessIntervalMs;
 505   ++num_process_times_;
 506
 507   encode_rsd_->Process(now);
 508   capture_queue_delay_->CalculateDelayChange(diff_ms);
 509
 510   if (num_process_times_ <= options_.min_process_count) {
 511     return 0;
 512   }
 513
 514   if (IsOverusing()) {
 515     // If the last thing we did was going up, and now have to back down, we need
 516     // to check if this peak was short. If so we should back off to avoid going
 517     // back and forth between this load, the system doesn't seem to handle it.
 518     bool check_for_backoff = last_rampup_time_ > last_overuse_time_;
 519     if (check_for_backoff) {
 520       if (now - last_rampup_time_ < kStandardRampUpDelayMs ||
 521           num_overuse_detections_ > kMaxOverusesBeforeApplyRampupDelay) {
 522         // Going up was not ok for very long, back off.
 523         current_rampup_delay_ms_ *= kRampUpBackoffFactor;
 524         if (current_rampup_delay_ms_ > kMaxRampUpDelayMs)
 525           current_rampup_delay_ms_ = kMaxRampUpDelayMs;
 526       } else {
 527         // Not currently backing off, reset rampup delay.
 528         current_rampup_delay_ms_ = kStandardRampUpDelayMs;
 529       }
 530     }
 531
 532     last_overuse_time_ = now;
 533     in_quick_rampup_ = false;
 534     checks_above_threshold_ = 0;
 535     ++num_overuse_detections_;
 536
 537     if (observer_ != NULL)
 538       observer_->OveruseDetected();
 539   } else if (IsUnderusing(now)) {
 540     last_rampup_time_ = now;
 541     in_quick_rampup_ = true;
 542
 543     if (observer_ != NULL)
 544       observer_->NormalUsage();
 545   }
 546
 547   int rampup_delay =
 548       in_quick_rampup_ ? kQuickRampUpDelayMs : current_rampup_delay_ms_;
 549   LOG(LS_VERBOSE) << " Frame stats: capture avg: " << capture_deltas_.Mean()
 550                   << " capture stddev " << capture_deltas_.StdDev()
 551                   << " encode usage " << encode_usage_->Value()
 552                   << " encode rsd " << encode_rsd_->Value()
 553                   << " overuse detections " << num_overuse_detections_
 554                   << " rampup delay " << rampup_delay;
 555   return 0;
 556 }
 557
 558 bool OveruseFrameDetector::IsOverusing() {
 559   bool overusing = false;
 560   if (options_.enable_capture_jitter_method) {
 561     overusing = capture_deltas_.StdDev() >=
 562         options_.high_capture_jitter_threshold_ms;
 563   } else if (options_.enable_encode_usage_method) {
 564     bool encode_usage_overuse =
 565         encode_usage_->Value() >= options_.high_encode_usage_threshold_percent;
 566     bool encode_rsd_overuse = false;
 567     if (options_.high_encode_time_rsd_threshold > 0) {
 568       encode_rsd_overuse =
 569           (encode_rsd_->Value() >= options_.high_encode_time_rsd_threshold);
 570     }
 571     overusing = encode_usage_overuse || encode_rsd_overuse;
 572   }
 573
 574   if (overusing) {
 575     ++checks_above_threshold_;
 576   } else {
 577     checks_above_threshold_ = 0;
 578   }
 579   return checks_above_threshold_ >= options_.high_threshold_consecutive_count;
 580 }
 581
 582 bool OveruseFrameDetector::IsUnderusing(int64_t time_now) {
 583   int delay = in_quick_rampup_ ? kQuickRampUpDelayMs : current_rampup_delay_ms_;
 584   if (time_now < last_rampup_time_ + delay)
 585     return false;
 586
 587   bool underusing = false;
 588   if (options_.enable_capture_jitter_method) {
 589     underusing = capture_deltas_.StdDev() <
 590         options_.low_capture_jitter_threshold_ms;
 591   } else if (options_.enable_encode_usage_method) {
 592     bool encode_usage_underuse =
 593         encode_usage_->Value() < options_.low_encode_usage_threshold_percent;
 594     bool encode_rsd_underuse = true;
 595     if (options_.low_encode_time_rsd_threshold > 0) {
 596       encode_rsd_underuse =
 597           (encode_rsd_->Value() < options_.low_encode_time_rsd_threshold);
 598     }
 599     underusing = encode_usage_underuse && encode_rsd_underuse;
 600   }
 601   return underusing;
 602 }
 603 }  // namespace webrtc