Report max interframe delay over window insdead of interframe delay sum

webrtc/rtc_base/moving_max_counter.h

+/*
+ *  Copyright (c) 2017 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_RTC_BASE_MOVING_MAX_COUNTER_H_
+#define WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_
+
+#include <stdint.h>
+
+#include <deque>
+#include <limits>
+#include <utility>
+
+#include "webrtc/rtc_base/checks.h"
+#include "webrtc/rtc_base/constructormagic.h"
+#include "webrtc/rtc_base/optional.h"
+
+namespace rtc {
+
+// Implements moving max: can add samples to it and calculate maximum over some
+// fixed moving window.
+//
+// Window size is configured at constructor.
+// Samples can be added with |Add()| and max over current window is returned by
+// |MovingMax|. |current_time_ms| in successive calls to Add and MovingMax
+// should never decrease as if it's a wallclock time.
+// Not thread-safe.

[kwiberg-webrtc, 2017/08/23 09:32:14]

Now that the mutable members are gone and you don't have const methods, there's
nothing special about this class thread-safety-wise, so the note on line 33
isn't needed.

[ilnik, 2017/08/23 09:57:56]

Done.

+template <class T>
+class MovingMaxCounter {
+ public:
+  explicit MovingMaxCounter(int64_t window_length_ms);
+  // Advances the current time, and adds a new sample. The new current time must
+  // be at least as large as the old current time.
+  void Add(const T& sample, int64_t current_time_ms);
+  // Advances the current time, and returns the maximum sample in the time
+  // window ending at the current time. The new current time must be at least as
+  // large as the old current time.
+  rtc::Optional<T> Max(int64_t current_time_ms);
+  void Reset();
+
+ private:
+  // Throws out obsolete samples.
+  void RollWindow(int64_t new_time_ms);
+  const int64_t window_length_ms_;
+  // Samples in the window are stored as pairs <time, sample> in this deque in
+  // chronological order. Samples what can't be maximum in any window are
+  // thrown out - deque always contains non-increasing sequence of samples.

[kwiberg-webrtc, 2017/08/23 09:32:14]

I made an attempt to rephrase this:

"This deque stores (timestamp, sample) pairs in chronological order; new pairs
are only ever added at the end. However, because they can't affect the Max()
calculation, pairs older than window_length_ms_ are discarded, and if an older
pair has a sample that's smaller than that of a younger pair, the older pair is
discarded. As a result, the sequence of timestamps is non-decreasing, and the
sequence of samples is non-increasing."

You can use that text, or keep the text you have now (if you replace "what
can't" with "that can't")---your choice.

[ilnik, 2017/08/23 09:57:56]

Done.

+  std::deque<std::pair<int64_t, T>> samples_;
+#if RTC_DCHECK_IS_ON
+  int64_t last_call_time_ms_ = std::numeric_limits<int64_t>::min();
+#endif
+  RTC_DISALLOW_COPY_AND_ASSIGN(MovingMaxCounter);
+};
+
+template <class T>
+MovingMaxCounter<T>::MovingMaxCounter(int64_t window_length_ms)
+    : window_length_ms_(window_length_ms) {}
+
+template <class T>
+void MovingMaxCounter<T>::Add(const T& sample, int64_t current_time_ms) {
+#if RTC_DCHECK_IS_ON
+  RTC_DCHECK_GE(current_time_ms, last_call_time_ms_);
+  last_call_time_ms_ = current_time_ms;
+#endif
+  RollWindow(current_time_ms);

[kwiberg-webrtc, 2017/08/23 09:32:14]

Hmm. You repeat lines 67-71 exactly below in the Max() method. How about moving
lines 67-70 into RollWindow()?

[ilnik, 2017/08/23 09:57:56]

Done.

+  // Remove samples what will never be maximum in any window: newly added sample

[kwiberg-webrtc, 2017/08/23 09:32:14]

samples that will never

[ilnik, 2017/08/23 09:57:56]

Done.

+  // will always be in all windows the previous samples are. Thus, smaller
+  // samples could be removed. This will maintain the invariant - deque contains
+  // non-increasing sequence of values.
+  while (!samples_.empty() && samples_.back().second < sample) {
+    samples_.pop_back();
+  }

[kwiberg-webrtc, 2017/08/23 09:32:13]

Hmm. Why not

  samples_.back().second <= sample

so that the sequence of values becomes strictly decreasing? That would eliminate
the case where the deque contains (time, sample) pairs such as (0, 17), (1, 17),
(2, 17), ..., (99, 17), and let it contain just (99, 17) instead.

[ilnik, 2017/08/23 09:57:56]

You are right. It doesn't affect the results, but will reduce the memory usage.
Changed that.

+  // Add the new sample but only if there's no existing sample at the same time.
+  // Due to checks above, already existing element will be larger and new sample
+  // will never be a maximum in any window.
+  if (samples_.empty() || samples_.back().first < current_time_ms) {
+    samples_.emplace_back(std::make_pair(current_time_ms, sample));
+  }
+}
+
+template <class T>
+rtc::Optional<T> MovingMaxCounter<T>::Max(int64_t current_time_ms) {
+#if RTC_DCHECK_IS_ON
+  RTC_DCHECK_GE(current_time_ms, last_call_time_ms_);
+  last_call_time_ms_ = current_time_ms;
+#endif
+  RollWindow(current_time_ms);
+  rtc::Optional<T> res;
+  if (!samples_.empty()) {
+    res.emplace(samples_.front().second);
+  }
+  return res;
+}
+
+template <class T>
+void MovingMaxCounter<T>::Reset() {
+  samples_.clear();
+}
+
+template <class T>
+void MovingMaxCounter<T>::RollWindow(int64_t new_time_ms) {
+  const int64_t window_begin_ms = new_time_ms - window_length_ms_;
+  auto it = samples_.begin();
+  while (it != samples_.end() && it->first < window_begin_ms) {
+    ++it;
+  }
+  samples_.erase(samples_.begin(), it);
+}
+
+}  // namespace rtc
+
+#endif  // WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_