Reland of VCMCodecTimer: Change filter from max to 95th percentile (patchset #1 id:1 of https://codereview.webrtc.org/1808693002/ )

This CL is expected to lower goog_max_decode_ms and total_delay_incl_network/receiver_time for screenshare.

Reason for revert:
This CL did not cause the unexpected goog_encode_usage_percent and goog_avg_encode_ms perf changes.

Original issue's description:
> Revert of VCMCodecTimer: Change filter from max to 95th percentile (patchset #5 id:180001 of https://codereview.webrtc.org/1742323002/ )
>
> Reason for revert:
> Caused unexpected perf stats changes, see http://crbug/594575.
>
> Original issue's description:
> > VCMCodecTimer: Change filter from max to 95th percentile
> >
> > The purpose with this change is to make the filter more robust against anomalies. googMaxDecodeMs is expected to drop a litte by this.
> >
> > BUG=b/27306053
> >
> > Committed: https://crrev.com/4bf0c717740d1834e810ea5f32b3c4306c64235f
> > Cr-Commit-Position: refs/heads/master@{#11952}
>
> TBR=stefan@webrtc.org,philipel@webrtc.org
> # Not skipping CQ checks because original CL landed more than 1 days ago.
> BUG=594575,b/27306053
>
> Committed: https://crrev.com/c4a74e95b545f4752d4e72961ac03c1380d4bc1f
> Cr-Commit-Position: refs/heads/master@{#12018}

TBR=stefan@webrtc.org,philipel@webrtc.org
# Not skipping CQ checks because original CL landed more than 1 days ago.
BUG=594575,b/27306053

Review URL: https://codereview.webrtc.org/1824763003

Cr-Original-Commit-Position: refs/heads/master@{#12087}
Cr-Mirrored-From: https://chromium.googlesource.com/external/webrtc
Cr-Mirrored-Commit: 2943f015b6f7b88a765264f76c19cd56e174cd00
diff --git a/modules/modules.gyp b/modules/modules.gyp
index 25a9b29..5fc87fe 100644
--- a/modules/modules.gyp
+++ b/modules/modules.gyp
@@ -369,6 +369,7 @@
             'video_coding/jitter_estimator_tests.cc',
             'video_coding/media_optimization_unittest.cc',
             'video_coding/nack_module_unittest.cc',
+            'video_coding/percentile_filter_unittest.cc',
             'video_coding/receiver_unittest.cc',
             'video_coding/session_info_unittest.cc',
             'video_coding/sequence_number_util_unittest.cc',
diff --git a/modules/video_coding/BUILD.gn b/modules/video_coding/BUILD.gn
index d95d2bc..37a0d2c 100644
--- a/modules/video_coding/BUILD.gn
+++ b/modules/video_coding/BUILD.gn
@@ -50,6 +50,8 @@
     "nack_module.h",
     "packet.cc",
     "packet.h",
+    "percentile_filter.cc",
+    "percentile_filter.h",
     "qm_select.cc",
     "qm_select.h",
     "qm_select_data.h",
diff --git a/modules/video_coding/codec_timer.cc b/modules/video_coding/codec_timer.cc
index 60add8f..0fdf1a6 100644
--- a/modules/video_coding/codec_timer.cc
+++ b/modules/video_coding/codec_timer.cc
@@ -10,87 +10,47 @@
 
 #include "webrtc/modules/video_coding/codec_timer.h"
 
-#include <assert.h>
-
 namespace webrtc {
 
+namespace {
+
 // The first kIgnoredSampleCount samples will be ignored.
-static const int32_t kIgnoredSampleCount = 5;
+const int kIgnoredSampleCount = 5;
+// Return the |kPercentile| value in RequiredDecodeTimeMs().
+const float kPercentile = 0.95f;
+// The window size in ms.
+const int64_t kTimeLimitMs = 10000;
+
+}  // anonymous namespace
 
 VCMCodecTimer::VCMCodecTimer()
-    : _filteredMax(0), _ignoredSampleCount(0), _shortMax(0), _history() {
-  Reset();
-}
+    : ignored_sample_count_(0), filter_(kPercentile) {}
 
-void VCMCodecTimer::Reset() {
-  _filteredMax = 0;
-  _ignoredSampleCount = 0;
-  _shortMax = 0;
-  for (int i = 0; i < MAX_HISTORY_SIZE; i++) {
-    _history[i].shortMax = 0;
-    _history[i].timeMs = -1;
-  }
-}
-
-// Update the max-value filter
-void VCMCodecTimer::MaxFilter(int32_t decodeTime, int64_t nowMs) {
-  if (_ignoredSampleCount >= kIgnoredSampleCount) {
-    UpdateMaxHistory(decodeTime, nowMs);
-    ProcessHistory(nowMs);
-  } else {
-    _ignoredSampleCount++;
-  }
-}
-
-void VCMCodecTimer::UpdateMaxHistory(int32_t decodeTime, int64_t now) {
-  if (_history[0].timeMs >= 0 && now - _history[0].timeMs < SHORT_FILTER_MS) {
-    if (decodeTime > _shortMax) {
-      _shortMax = decodeTime;
-    }
-  } else {
-    // Only add a new value to the history once a second
-    if (_history[0].timeMs == -1) {
-      // First, no shift
-      _shortMax = decodeTime;
-    } else {
-      // Shift
-      for (int i = (MAX_HISTORY_SIZE - 2); i >= 0; i--) {
-        _history[i + 1].shortMax = _history[i].shortMax;
-        _history[i + 1].timeMs = _history[i].timeMs;
-      }
-    }
-    if (_shortMax == 0) {
-      _shortMax = decodeTime;
-    }
-
-    _history[0].shortMax = _shortMax;
-    _history[0].timeMs = now;
-    _shortMax = 0;
-  }
-}
-
-void VCMCodecTimer::ProcessHistory(int64_t nowMs) {
-  _filteredMax = _shortMax;
-  if (_history[0].timeMs == -1) {
+void VCMCodecTimer::AddTiming(int64_t decode_time_ms, int64_t now_ms) {
+  // Ignore the first |kIgnoredSampleCount| samples.
+  if (ignored_sample_count_ < kIgnoredSampleCount) {
+    ++ignored_sample_count_;
     return;
   }
-  for (int i = 0; i < MAX_HISTORY_SIZE; i++) {
-    if (_history[i].timeMs == -1) {
-      break;
-    }
-    if (nowMs - _history[i].timeMs > MAX_HISTORY_SIZE * SHORT_FILTER_MS) {
-      // This sample (and all samples after this) is too old
-      break;
-    }
-    if (_history[i].shortMax > _filteredMax) {
-      // This sample is the largest one this far into the history
-      _filteredMax = _history[i].shortMax;
-    }
+
+  // Insert new decode time value.
+  filter_.Insert(decode_time_ms);
+  history_.emplace(decode_time_ms, now_ms);
+
+  // Pop old decode time values.
+  while (!history_.empty() &&
+         now_ms - history_.front().sample_time_ms > kTimeLimitMs) {
+    filter_.Erase(history_.front().decode_time_ms);
+    history_.pop();
   }
 }
 
-// Get the maximum observed time within a time window
-int32_t VCMCodecTimer::RequiredDecodeTimeMs(FrameType /*frameType*/) const {
-  return _filteredMax;
+// Get the 95th percentile observed decode time within a time window.
+int64_t VCMCodecTimer::RequiredDecodeTimeMs() const {
+  return filter_.GetPercentileValue();
 }
+
+VCMCodecTimer::Sample::Sample(int64_t decode_time_ms, int64_t sample_time_ms)
+    : decode_time_ms(decode_time_ms), sample_time_ms(sample_time_ms) {}
+
 }  // namespace webrtc
diff --git a/modules/video_coding/codec_timer.h b/modules/video_coding/codec_timer.h
index 8ebd82a..90ef6bb 100644
--- a/modules/video_coding/codec_timer.h
+++ b/modules/video_coding/codec_timer.h
@@ -11,45 +11,39 @@
 #ifndef WEBRTC_MODULES_VIDEO_CODING_CODEC_TIMER_H_
 #define WEBRTC_MODULES_VIDEO_CODING_CODEC_TIMER_H_
 
+#include <queue>
+
 #include "webrtc/modules/include/module_common_types.h"
+#include "webrtc/modules/video_coding/percentile_filter.h"
 #include "webrtc/typedefs.h"
 
 namespace webrtc {
 
-// MAX_HISTORY_SIZE * SHORT_FILTER_MS defines the window size in milliseconds
-#define MAX_HISTORY_SIZE 10
-#define SHORT_FILTER_MS 1000
-
-class VCMShortMaxSample {
- public:
-  VCMShortMaxSample() : shortMax(0), timeMs(-1) {}
-
-  int32_t shortMax;
-  int64_t timeMs;
-};
-
 class VCMCodecTimer {
  public:
   VCMCodecTimer();
 
-  // Updates the max filtered decode time.
-  void MaxFilter(int32_t newDecodeTimeMs, int64_t nowMs);
+  // Add a new decode time to the filter.
+  void AddTiming(int64_t new_decode_time_ms, int64_t now_ms);
 
-  // Empty the list of timers.
-  void Reset();
-
-  // Get the required decode time in ms.
-  int32_t RequiredDecodeTimeMs(FrameType frameType) const;
+  // Get the required decode time in ms. It is the 95th percentile observed
+  // decode time within a time window.
+  int64_t RequiredDecodeTimeMs() const;
 
  private:
-  void UpdateMaxHistory(int32_t decodeTime, int64_t now);
-  void ProcessHistory(int64_t nowMs);
+  struct Sample {
+    Sample(int64_t decode_time_ms, int64_t sample_time_ms);
+    int64_t decode_time_ms;
+    int64_t sample_time_ms;
+  };
 
-  int32_t _filteredMax;
   // The number of samples ignored so far.
-  int32_t _ignoredSampleCount;
-  int32_t _shortMax;
-  VCMShortMaxSample _history[MAX_HISTORY_SIZE];
+  int ignored_sample_count_;
+  // Queue with history of latest decode time values.
+  std::queue<Sample> history_;
+  // |filter_| contains the same values as |history_|, but in a data structure
+  // that allows efficient retrieval of the percentile value.
+  PercentileFilter filter_;
 };
 
 }  // namespace webrtc
diff --git a/modules/video_coding/percentile_filter.cc b/modules/video_coding/percentile_filter.cc
new file mode 100644
index 0000000..6495567
--- /dev/null
+++ b/modules/video_coding/percentile_filter.cc
@@ -0,0 +1,70 @@
+/*
+ *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "webrtc/modules/video_coding/percentile_filter.h"
+
+#include <iterator>
+
+#include "webrtc/base/checks.h"
+
+namespace webrtc {
+
+PercentileFilter::PercentileFilter(float percentile)
+    : percentile_(percentile),
+      percentile_it_(set_.begin()),
+      percentile_index_(0) {
+  RTC_CHECK_GE(percentile, 0.0f);
+  RTC_CHECK_LE(percentile, 1.0f);
+}
+
+void PercentileFilter::Insert(const int64_t& value) {
+  // Insert element at the upper bound.
+  set_.insert(value);
+  if (set_.size() == 1u) {
+    // First element inserted - initialize percentile iterator and index.
+    percentile_it_ = set_.begin();
+    percentile_index_ = 0;
+  } else if (value < *percentile_it_) {
+    // If new element is before us, increment |percentile_index_|.
+    ++percentile_index_;
+  }
+  UpdatePercentileIterator();
+}
+
+void PercentileFilter::Erase(const int64_t& value) {
+  std::multiset<int64_t>::const_iterator it = set_.lower_bound(value);
+  // Ignore erase operation if the element is not present in the current set.
+  if (it == set_.end() || *it != value)
+    return;
+  if (it == percentile_it_) {
+    // If same iterator, update to the following element. Index is not affected.
+    percentile_it_ = set_.erase(it);
+  } else {
+    set_.erase(it);
+    // If erased element was before us, decrement |percentile_index_|.
+    if (value <= *percentile_it_)
+      --percentile_index_;
+  }
+  UpdatePercentileIterator();
+}
+
+void PercentileFilter::UpdatePercentileIterator() {
+  if (set_.empty())
+    return;
+  const int64_t index = static_cast<int64_t>(percentile_ * (set_.size() - 1));
+  std::advance(percentile_it_, index - percentile_index_);
+  percentile_index_ = index;
+}
+
+int64_t PercentileFilter::GetPercentileValue() const {
+  return set_.empty() ? 0 : *percentile_it_;
+}
+
+}  // namespace webrtc
diff --git a/modules/video_coding/percentile_filter.h b/modules/video_coding/percentile_filter.h
new file mode 100644
index 0000000..125a244
--- /dev/null
+++ b/modules/video_coding/percentile_filter.h
@@ -0,0 +1,50 @@
+/*
+ *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef WEBRTC_MODULES_VIDEO_CODING_PERCENTILE_FILTER_H_
+#define WEBRTC_MODULES_VIDEO_CODING_PERCENTILE_FILTER_H_
+
+#include <stdint.h>
+
+#include <set>
+
+namespace webrtc {
+
+// Class to efficiently get the percentile value from a group of observations.
+// The percentile is the value below which a given percentage of the
+// observations fall.
+class PercentileFilter {
+ public:
+  // Construct filter. |percentile| should be between 0 and 1.
+  explicit PercentileFilter(float percentile);
+
+  // Insert one observation. The complexity of this operation is logarithmic in
+  // the size of the container.
+  void Insert(const int64_t& value);
+  // Remove one observation. The complexity of this operation is logarithmic in
+  // the size of the container.
+  void Erase(const int64_t& value);
+  // Get the percentile value. The complexity of this operation is constant.
+  int64_t GetPercentileValue() const;
+
+ private:
+  // Update iterator and index to point at target percentile value.
+  void UpdatePercentileIterator();
+
+  const float percentile_;
+  std::multiset<int64_t> set_;
+  // Maintain iterator and index of current target percentile value.
+  std::multiset<int64_t>::iterator percentile_it_;
+  int64_t percentile_index_;
+};
+
+}  // namespace webrtc
+
+#endif  // WEBRTC_MODULES_VIDEO_CODING_PERCENTILE_FILTER_H_
diff --git a/modules/video_coding/percentile_filter_unittest.cc b/modules/video_coding/percentile_filter_unittest.cc
new file mode 100644
index 0000000..8029bdb
--- /dev/null
+++ b/modules/video_coding/percentile_filter_unittest.cc
@@ -0,0 +1,104 @@
+/*
+ *  Copyright 2016 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include <algorithm>
+
+#include "testing/gtest/include/gtest/gtest.h"
+#include "webrtc/base/constructormagic.h"
+#include "webrtc/modules/video_coding/percentile_filter.h"
+
+namespace webrtc {
+
+class PercentileFilterTest : public ::testing::TestWithParam<float> {
+ public:
+  PercentileFilterTest() : filter_(GetParam()) {
+    // Make sure the tests are deterministic by seeding with a constant.
+    srand(42);
+  }
+
+ protected:
+  PercentileFilter filter_;
+
+ private:
+  RTC_DISALLOW_COPY_AND_ASSIGN(PercentileFilterTest);
+};
+
+INSTANTIATE_TEST_CASE_P(PercentileFilterTests,
+                        PercentileFilterTest,
+                        ::testing::Values(0.0f, 0.1f, 0.5f, 0.9f, 1.0f));
+
+TEST(PercentileFilterTest, MinFilter) {
+  PercentileFilter filter(0.0f);
+  filter.Insert(4);
+  EXPECT_EQ(4, filter.GetPercentileValue());
+  filter.Insert(3);
+  EXPECT_EQ(3, filter.GetPercentileValue());
+}
+
+TEST(PercentileFilterTest, MaxFilter) {
+  PercentileFilter filter(1.0f);
+  filter.Insert(3);
+  EXPECT_EQ(3, filter.GetPercentileValue());
+  filter.Insert(4);
+  EXPECT_EQ(4, filter.GetPercentileValue());
+}
+
+TEST_P(PercentileFilterTest, EmptyFilter) {
+  EXPECT_EQ(0, filter_.GetPercentileValue());
+  filter_.Insert(3);
+  filter_.Erase(3);
+  EXPECT_EQ(0, filter_.GetPercentileValue());
+}
+
+TEST_P(PercentileFilterTest, EraseNonExistingElement) {
+  filter_.Erase(3);
+  EXPECT_EQ(0, filter_.GetPercentileValue());
+  filter_.Insert(4);
+  filter_.Erase(3);
+  EXPECT_EQ(4, filter_.GetPercentileValue());
+}
+
+TEST_P(PercentileFilterTest, DuplicateElements) {
+  filter_.Insert(3);
+  filter_.Insert(3);
+  filter_.Erase(3);
+  EXPECT_EQ(3, filter_.GetPercentileValue());
+}
+
+TEST_P(PercentileFilterTest, InsertAndEraseTenValuesInRandomOrder) {
+  int64_t zero_to_nine[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+  // The percentile value of the ten values above.
+  const int64_t expected_value = static_cast<int64_t>(GetParam() * 9);
+
+  // Insert two sets of |zero_to_nine| in random order.
+  for (int i = 0; i < 2; ++i) {
+    std::random_shuffle(zero_to_nine, zero_to_nine + 10);
+    for (int64_t value : zero_to_nine)
+      filter_.Insert(value);
+    // After inserting a full set of |zero_to_nine|, the percentile should
+    // stay constant.
+    EXPECT_EQ(expected_value, filter_.GetPercentileValue());
+  }
+
+  // Insert and erase sets of |zero_to_nine| in random order a few times.
+  for (int i = 0; i < 3; ++i) {
+    std::random_shuffle(zero_to_nine, zero_to_nine + 10);
+    for (int64_t value : zero_to_nine)
+      filter_.Erase(value);
+    EXPECT_EQ(expected_value, filter_.GetPercentileValue());
+
+    std::random_shuffle(zero_to_nine, zero_to_nine + 10);
+    for (int64_t value : zero_to_nine)
+      filter_.Insert(value);
+    EXPECT_EQ(expected_value, filter_.GetPercentileValue());
+  }
+}
+
+}  // namespace webrtc
diff --git a/modules/video_coding/timing.cc b/modules/video_coding/timing.cc
index 680860a..91f5f84 100644
--- a/modules/video_coding/timing.cc
+++ b/modules/video_coding/timing.cc
@@ -25,7 +25,7 @@
       clock_(clock),
       master_(false),
       ts_extrapolator_(),
-      codec_timer_(),
+      codec_timer_(new VCMCodecTimer()),
       render_delay_ms_(kDefaultRenderDelayMs),
       min_playout_delay_ms_(0),
       jitter_delay_ms_(0),
@@ -78,7 +78,7 @@
 void VCMTiming::Reset() {
   CriticalSectionScoped cs(crit_sect_);
   ts_extrapolator_->Reset(clock_->TimeInMilliseconds());
-  codec_timer_.Reset();
+  codec_timer_.reset(new VCMCodecTimer());
   render_delay_ms_ = kDefaultRenderDelayMs;
   min_playout_delay_ms_ = 0;
   jitter_delay_ms_ = 0;
@@ -88,7 +88,7 @@
 
 void VCMTiming::ResetDecodeTime() {
   CriticalSectionScoped lock(crit_sect_);
-  codec_timer_.Reset();
+  codec_timer_.reset(new VCMCodecTimer());
 }
 
 void VCMTiming::set_render_delay(uint32_t render_delay_ms) {
@@ -156,8 +156,9 @@
                                    int64_t actual_decode_time_ms) {
   CriticalSectionScoped cs(crit_sect_);
   uint32_t target_delay_ms = TargetDelayInternal();
-  int64_t delayed_ms = actual_decode_time_ms -
-                       (render_time_ms - MaxDecodeTimeMs() - render_delay_ms_);
+  int64_t delayed_ms =
+      actual_decode_time_ms -
+      (render_time_ms - RequiredDecodeTimeMs() - render_delay_ms_);
   if (delayed_ms < 0) {
     return;
   }
@@ -173,7 +174,7 @@
                                    int64_t now_ms,
                                    int64_t render_time_ms) {
   CriticalSectionScoped cs(crit_sect_);
-  codec_timer_.MaxFilter(decode_time_ms, now_ms);
+  codec_timer_->AddTiming(decode_time_ms, now_ms);
   assert(decode_time_ms >= 0);
   last_decode_ms_ = decode_time_ms;
 
@@ -216,9 +217,8 @@
 }
 
 // Must be called from inside a critical section.
-int32_t VCMTiming::MaxDecodeTimeMs(
-    FrameType frame_type /*= kVideoFrameDelta*/) const {
-  const int32_t decode_time_ms = codec_timer_.RequiredDecodeTimeMs(frame_type);
+int64_t VCMTiming::RequiredDecodeTimeMs() const {
+  const int64_t decode_time_ms = codec_timer_->RequiredDecodeTimeMs();
   assert(decode_time_ms >= 0);
   return decode_time_ms;
 }
@@ -228,7 +228,7 @@
   CriticalSectionScoped cs(crit_sect_);
 
   const int64_t max_wait_time_ms =
-      render_time_ms - now_ms - MaxDecodeTimeMs() - render_delay_ms_;
+      render_time_ms - now_ms - RequiredDecodeTimeMs() - render_delay_ms_;
 
   if (max_wait_time_ms < 0) {
     return 0;
@@ -239,18 +239,18 @@
 bool VCMTiming::EnoughTimeToDecode(
     uint32_t available_processing_time_ms) const {
   CriticalSectionScoped cs(crit_sect_);
-  int32_t max_decode_time_ms = MaxDecodeTimeMs();
-  if (max_decode_time_ms < 0) {
+  int64_t required_decode_time_ms = RequiredDecodeTimeMs();
+  if (required_decode_time_ms < 0) {
     // Haven't decoded any frames yet, try decoding one to get an estimate
     // of the decode time.
     return true;
-  } else if (max_decode_time_ms == 0) {
+  } else if (required_decode_time_ms == 0) {
     // Decode time is less than 1, set to 1 for now since
     // we don't have any better precision. Count ticks later?
-    max_decode_time_ms = 1;
+    required_decode_time_ms = 1;
   }
-  return static_cast<int32_t>(available_processing_time_ms) -
-             max_decode_time_ms >
+  return static_cast<int64_t>(available_processing_time_ms) -
+             required_decode_time_ms >
          0;
 }
 
@@ -261,7 +261,9 @@
 
 uint32_t VCMTiming::TargetDelayInternal() const {
   return std::max(min_playout_delay_ms_,
-                  jitter_delay_ms_ + MaxDecodeTimeMs() + render_delay_ms_);
+                  jitter_delay_ms_ +
+                      static_cast<uint32_t>(RequiredDecodeTimeMs()) +
+                      render_delay_ms_);
 }
 
 void VCMTiming::GetTimings(int* decode_ms,
@@ -273,7 +275,7 @@
                            int* render_delay_ms) const {
   CriticalSectionScoped cs(crit_sect_);
   *decode_ms = last_decode_ms_;
-  *max_decode_ms = MaxDecodeTimeMs();
+  *max_decode_ms = static_cast<int>(RequiredDecodeTimeMs());
   *current_delay_ms = current_delay_ms_;
   *target_delay_ms = TargetDelayInternal();
   *jitter_buffer_ms = jitter_delay_ms_;
diff --git a/modules/video_coding/timing.h b/modules/video_coding/timing.h
index a4d0cf4..a45eee3 100644
--- a/modules/video_coding/timing.h
+++ b/modules/video_coding/timing.h
@@ -11,6 +11,8 @@
 #ifndef WEBRTC_MODULES_VIDEO_CODING_TIMING_H_
 #define WEBRTC_MODULES_VIDEO_CODING_TIMING_H_
 
+#include <memory>
+
 #include "webrtc/base/thread_annotations.h"
 #include "webrtc/modules/video_coding/codec_timer.h"
 #include "webrtc/system_wrappers/include/critical_section_wrapper.h"
@@ -94,7 +96,7 @@
   enum { kDelayMaxChangeMsPerS = 100 };
 
  protected:
-  int32_t MaxDecodeTimeMs(FrameType frame_type = kVideoFrameDelta) const
+  int64_t RequiredDecodeTimeMs() const
       EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);
   int64_t RenderTimeMsInternal(uint32_t frame_timestamp, int64_t now_ms) const
       EXCLUSIVE_LOCKS_REQUIRED(crit_sect_);
@@ -107,7 +109,7 @@
   Clock* const clock_;
   bool master_ GUARDED_BY(crit_sect_);
   TimestampExtrapolator* ts_extrapolator_ GUARDED_BY(crit_sect_);
-  VCMCodecTimer codec_timer_ GUARDED_BY(crit_sect_);
+  std::unique_ptr<VCMCodecTimer> codec_timer_ GUARDED_BY(crit_sect_);
   uint32_t render_delay_ms_ GUARDED_BY(crit_sect_);
   uint32_t min_playout_delay_ms_ GUARDED_BY(crit_sect_);
   uint32_t jitter_delay_ms_ GUARDED_BY(crit_sect_);
diff --git a/modules/video_coding/timing_unittest.cc b/modules/video_coding/timing_unittest.cc
index 2e8df83..51ef354 100644
--- a/modules/video_coding/timing_unittest.cc
+++ b/modules/video_coding/timing_unittest.cc
@@ -29,7 +29,7 @@
   VCMTiming timing(&clock);
   uint32_t waitTime = 0;
   uint32_t jitterDelayMs = 0;
-  uint32_t maxDecodeTimeMs = 0;
+  uint32_t requiredDecodeTimeMs = 0;
   uint32_t timeStamp = 0;
 
   timing.Reset();
@@ -94,7 +94,7 @@
     clock.AdvanceTimeMilliseconds(1000 / 25 - 10);
     timing.IncomingTimestamp(timeStamp, clock.TimeInMilliseconds());
   }
-  maxDecodeTimeMs = 10;
+  requiredDecodeTimeMs = 10;
   timing.SetJitterDelay(jitterDelayMs);
   clock.AdvanceTimeMilliseconds(1000);
   timeStamp += 90000;
@@ -116,7 +116,7 @@
       clock.TimeInMilliseconds());
   // We should at least have minTotalDelayMs - decodeTime (10) - renderTime
   // (10) to wait.
-  EXPECT_EQ(waitTime, minTotalDelayMs - maxDecodeTimeMs - kRenderDelayMs);
+  EXPECT_EQ(waitTime, minTotalDelayMs - requiredDecodeTimeMs - kRenderDelayMs);
   // The total video delay should be equal to the min total delay.
   EXPECT_EQ(minTotalDelayMs, timing.TargetVideoDelay());
 
diff --git a/modules/video_coding/video_coding.gypi b/modules/video_coding/video_coding.gypi
index 02c9c6b..82c2726 100644
--- a/modules/video_coding/video_coding.gypi
+++ b/modules/video_coding/video_coding.gypi
@@ -47,6 +47,7 @@
         'nack_fec_tables.h',
         'nack_module.h',
         'packet.h',
+        'percentile_filter.h',
         'qm_select_data.h',
         'qm_select.h',
         'receiver.h',
@@ -74,6 +75,7 @@
         'media_optimization.cc',
         'nack_module.cc',
         'packet.cc',
+        'percentile_filter.cc',
         'qm_select.cc',
         'receiver.cc',
         'rtt_filter.cc',