VCMCodecTimer: Change filter from max to 95th percentile

webrtc/modules/video_coding/codec_timer.h

 /*
  *  Copyright (c) 2011 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_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_;

[stefan-webrtc, 2016/03/08 16:07:48]

I haven't looked at the details of PercentileFilter, but do we really need both
a history_ here and the set in PercentileFilter? Maybe it would be simpler to
have the PercentileFilter remove elements from itself when it has too many?

[magjed_webrtc, 2016/03/10 09:14:09]

Yes, we need both the queue and the multiset in PercentileFilter, if we want it
to be fast. The queue is for fast retrieval of the oldest element, and the
multiset is for fast retrieval of the percentile value. The logic in
VCMCodecTimer adds/removes elements to PercentileFilter to maintain a sliding
time window of observations, and then fetches the percentile value in
RequiredDecodeTimeMs().

If you think this approach is overengineering, a simpler but less efficient
approach is to just have a std::deque with the history, and in
RequiredDecodeTimeMs() copy the history to a std::vector, sort it, and return
the percentile value. I think we can have many hundreds of observations in the
history, so I don't like this inefficient approach. Also, I have already
implemented the efficient approach with tests and everything now...

WDYT?

+  // |filter_| contains the same values as |history_|, but in a data structure
+  // that allows efficient retrieval of the percentile value.
+  PercentileFilter filter_;
 };
 
 }  // namespace webrtc
 
 #endif  // WEBRTC_MODULES_VIDEO_CODING_CODEC_TIMER_H_