Report max interframe delay over window insdead of interframe delay sum

webrtc/rtc_base/moving_max_counter.h

+/*
+ *  Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.

[ilnik, 2017/08/18 13:31:17]

changed to 2017. Will upload in the next patch set.

+ *
+ *  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|. |time_ms| in consecutive calls to Add and MovingMax should never
+// decrease as if it's a current time.
+// Not thread-safe.
+template <class T>
+class MovingMaxCounter {
+ public:
+  explicit MovingMaxCounter(int window_length_ms);

[sprang_webrtc, 2017/08/21 14:41:09]

For consistency, maybe use int64_t for times

[ilnik, 2017/08/21 14:59:27]

Done.

+  // Adds new sample at a given current time.
+  void Add(const T& sample, int64_t time_ms);
+  // Returns max sample in window ending at a given current time.
+  rtc::Optional<T> MovingMax(int64_t time_ms) const;

[sprang_webrtc, 2017/08/21 14:41:09]

Remove Moving from name

[ilnik, 2017/08/21 14:59:27]

Done.

+  void Reset();
+
+ private:
+  // Throws out obsolete samples. Is |const| because it is always safe to throw
+  // out old elements as long as |time_ms| parameters to public methods are
+  // always increasing.
+  void RollWindow(int64_t time_ms) const;
+  int window_length_ms_;

[sprang_webrtc, 2017/08/21 14:41:09]

const

[ilnik, 2017/08/21 14:59:27]

Done.

+  // 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.
+  // Is |mutable| because |MovingMax()| may be called on const instances yet it
+  // will remove obsolete samples to speed up consecutive calls.
+  mutable std::deque<std::pair<int64_t, T>> samples_;
+  mutable int64_t last_call_time_ms_;
+
+  RTC_DISALLOW_COPY_AND_ASSIGN(MovingMaxCounter);
+};
+
+template <class T>
+MovingMaxCounter<T>::MovingMaxCounter(int window_length_ms)
+    : window_length_ms_(window_length_ms),
+      last_call_time_ms_(std::numeric_limits<int64_t>::min()) {}
+
+template <class T>
+void MovingMaxCounter<T>::Add(const T& sample, int64_t time_ms) {
+  RTC_DCHECK_GE(time_ms, last_call_time_ms_);
+  last_call_time_ms_ = time_ms;
+  RollWindow(time_ms);
+  // Remove samples what will never be maximum in any window: newly added sample
+  // 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();
+  }
+  samples_.emplace_back(std::make_pair(time_ms, sample));

[sprang_webrtc, 2017/08/21 14:41:09]

if samples_[time_ms] exists, you can just update the value if the new one is
larger

[ilnik, 2017/08/21 14:59:27]

Seems like an unneeded optimization to me. If the new value is larger, the old
one will be thrown out automatically, If the new value is less, it will be
thrown out together with the old one once both of them are expired. We might
save some memory space if there are several samples per millisecond, but at the
expense of more checks.

[sprang_webrtc, 2017/08/22 08:44:50]

Agree that it should not matter for the use case in this cl, but if we put it
here eventually someone is going to use it for a case where multiple insertions
per millisecond is common, so I'd argue that covering that with an extra check
would be worth it. It's just an extra line. Also makes it conceptually easier to
reason about correctness if there's only a single entry per time.

auto it = samples_.emplace_back(std::make_pair(time_ms, sample));
if (!it.second) it.first = std::max<T>(it.first, sample);

[ilnik, 2017/08/22 09:06:39]

Fair enough. I am adding the checks now.

+}
+
+template <class T>
+rtc::Optional<T> MovingMaxCounter<T>::MovingMax(int64_t time_ms) const {
+  RTC_DCHECK_GE(time_ms, last_call_time_ms_);
+  last_call_time_ms_ = time_ms;
+  RollWindow(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 time_ms) const {
+  int64_t window_begin_ms = time_ms - window_length_ms_;
+  while (!samples_.empty() && samples_.front().first < window_begin_ms) {
+    samples_.pop_front();
+  }
+}
+
+}  // namespace rtc
+
+#endif  // WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_