Report max interframe delay over window insdead of interframe delay sum

webrtc/rtc_base/moving_max_counter.h

Index: webrtc/rtc_base/moving_max_counter.h
diff --git a/webrtc/rtc_base/moving_max_counter.h b/webrtc/rtc_base/moving_max_counter.h
new file mode 100644
index 0000000000000000000000000000000000000000..296d264af6b690c38615805aea028b5d1bc9c153
--- /dev/null
+++ b/webrtc/rtc_base/moving_max_counter.h
@@ -0,0 +1,113 @@
+/*
+ *  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|. |time_ms| in consecutive calls to Add and MovingMax should never

[kwiberg-webrtc, 2017/08/22 11:13:30]

consecutive -> successive

[ilnik, 2017/08/22 12:03:56]

Done.

+// decrease as if it's a current time.
+// Not thread-safe.

[kwiberg-webrtc, 2017/08/22 11:13:30]

Specifically, "Not thread-safe even if you only call const methods."

[ilnik, 2017/08/22 12:03:56]

Done.

+template <class T>
+class MovingMaxCounter {
+ public:
+  explicit MovingMaxCounter(int64_t window_length_ms);
+  // Adds new sample at a given current time.
+  void Add(const T& sample, int64_t time_ms);

[kwiberg-webrtc, 2017/08/22 11:13:30]

"Advances the current time, and adds a new sample. The new current time must  be
at least as large as the old current time."

Probably also rename time_ms -> current_time_ms.

[ilnik, 2017/08/22 12:03:56]

Advancing a current time is internal logic, not important to users. I don't
think this should be mentioned here.

Renaming is fine, done it.

[kwiberg-webrtc, 2017/08/22 12:35:37]

The reason I suggested mentioning it here, or even having a separate method to
advance the time, is that this internal state is visible to callers (by way of
the restriction that two successive calls must specify non-decreasing
timestamps), so we need to tell them *somehow*. This was simply the most
pedagogical way I could think of.

[ilnik, 2017/08/22 13:04:38]

Ok, I agree, This has to be mentioned here.

+  // Returns max sample in window ending at a given current time.
+  rtc::Optional<T> Max(int64_t time_ms) const;

[kwiberg-webrtc, 2017/08/22 11:13:29]

"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."

Probably also rename time_ms -> current_time_ms.

[ilnik, 2017/08/22 12:03:56]

Ditto.

+  void Reset();
+

[kwiberg-webrtc, 2017/08/22 11:13:30]

Hmm. It's slightly difficult to document Add() and Max() well, since they each
do two things: advance the time and adding or finding the max. It might be
easier to use this class if you had this set of public methods instead:

  void Add(const T& sample);  // add new sample at the current time
  rtc::Optional<T> Max() const;  // return max for the current time
  void AdvanceTime(int64_t current_time_ms);  // advance the current time

[ilnik, 2017/08/22 12:03:56]

The time advancement is an internal thing only. The public documentation is
easy: one adds sample at a given time, the other gives maximum in the window
with a fixed end time. Implementation specific restriction is that time should
never decrease.

Additionally, Add() can skip advancement of a time, it will just increase the
memory usage.

[kwiberg-webrtc, 2017/08/22 12:35:38]

Well, you can say that it's "internal" and "implementation specific", but that
doesn't change the fact that callers need to be aware of how it works in order
to avoid making illegal calls; so it must be documented. I found the
documentation on this point confusing until I'd read the implementation two or
three times, since it tries to pretend that the current time isn't part of the
state of the MovingMaxCounter.
Hmm, I don't quite get what you mean here. That you can call Add() several times
with the same timestamp?

[ilnik, 2017/08/22 13:04:38]

Callers need to be aware only of one condition: time should always increase in
all calls. More comments on that should be enough I think. Splitting Max and
AdvanceTime
Will not be clear to the user since AdvanceTime will have to be const too, as it
will be called from the same GetStats function. 
I mean, that RollWindow call can be skipped in Add(). 

[kwiberg-webrtc, 2017/08/22 13:28:40]

OK, so no separate AdvanceTime() method---that's fine. But I really don't like
the idea of Max() both being const and modifying externally visible state---it
violates the convention of what "const" is supposed to mean in C++, and makes
the behavior highly nonintuitive.

How bad would it be to not call RollWindow() in Max()? I'm guessing the net
performance effect would be that we'd pay the cost of a RollWindow() call every
time we call Max()? How bad would that be?
Oh. Well, that's purely an implementation detail---even if you do that, Add()
will still update the object's idea of the current time, by adding a new sample
with a new timestamp. No one outside the class would be able to tell the
difference.

[ilnik, 2017/08/22 14:11:34]

It may be quite bad. I don't like that It completely destroys all performance
guarantees we may give. Currently, this class works in constant time on average
for every Add() and Max() call. And it's pretty smooth if samples are spaced
regularly.  It's because each sample will be removed only once. If instead we
are skipping samples in Max(), we will skip each sample as many times as Max()
will be called before the next Add(). And it may be arbitrary bad.

Also, removing that RollWindow() in Max() somewhat makes |const| more justified,
but doesn't remove restrictions that we can't call Max() from the past. I don't
see any perfect solutions here:

1) We can leave it as it is. Ugly thing is const Max() which kind-of changes
internal state. But if invariant on current_time_ms is respected by the user, it
doesn't matter how many or in that order calls are made.

2) Remove current_time_ms parameters and get local time inside Add and Max. Less
flexible, works slower. Good that no invariant have to be respected by user. At
current load we are observing (<50 samples per second, 1 Max() per second) it
doesn't matter, but if this class will be used in other places it may be an
issue.

3) Remove RollWindow() in Max(). |const| is somewhat justified, but invariant
still needs to be partially preserved by the user in sense that Max() can't be
called with time less than the last Add() call had. Also there are workflows
where this class works no better than a naive implementation using vector and
storing all the samples. Not the problem for the current use in this CL, but
this class will be unusable in general case.


I personally, like the 1st solution the most. If we document the invariant more
clear it will be fine, I hope.

[kwiberg-webrtc, 2017/08/22 21:40:46]

Hmm. None of the options are particularly appealing.

Why does Max() have to be const, exactly? Would it be possible to change things
so that it can be non-const?

[ilnik, 2017/08/23 07:46:50]

Yes, I'll try to make it non const. Instead, as in your suggestion,
MovingMaxCounter instance will be mutable.

+ 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;

[kwiberg-webrtc, 2017/08/22 11:13:30]

I don't really like that this is const---conceptually, it does change the object
(by updating its idea of the current time). Would it be terribly inconvenient if
it weren't const?

[ilnik, 2017/08/22 12:03:56]

The problem is that Max() is assumed to be const in existing code (and from the
external point of view it should be. No sequence of Max() calls will ever change
the result of any subsequent Add() or Max() operation). 

But Max() must call RollWindow(). So it can only be const too.

[kwiberg-webrtc, 2017/08/22 12:35:37]

This is not true. Consider

  c.Add(1, 1);
  Foo(&c);  // void Foo(const MovingMaxCounter*);
  c.Add(2, 2);

This sequence of calls is supposed to be unconditionally safe, since Foo()
shouldn't be modifying c. But if Foo() calls c->Max(3), this sequence of calls
is in fact illegal.

Like it or not, as this is currently implemented, MovingMaxCounter de facto
keeps track of the most recent timestamp passed to it by an Add() or Max() call,
and that state is not invisible to callers. So Max() shouldn't be const.
If it needs to be const, it shouldn't update visible state.

[ilnik, 2017/08/22 13:04:38]

Yes, it's hard to reflect the realtime-clock properties of time_ms parameter.
If, as documented something like realtime clock is used as a parameters for
calls, then your mentioned sequence of calls is impossible.

There's a way to fix all interface problems at the expense of efficiency and
flexibility: just remove time_ms parameters and get realtime from system clock
inside the functions. This way users physically can't make illegal call. I don't
like this solution, since time functions are not very fast and it's impossible
to test.

Also, currently, if there's incorrect calls, there'll be failed assert, which
will be easy to understand.

[kwiberg-webrtc, 2017/08/22 13:28:41]

I agree.
It's not impossible to test---tests can replace the global clock with a fake. I
do agree that there might potentially be unnecessary calls to the clock in
production code, though.
Yes. But they'll fail at run-time, which isn't as good as at compile-time.

+  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.
+  // 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_;

[kwiberg-webrtc, 2017/08/22 11:13:30]

Is last_call_time_ms_ necessary? Couldn't you just use samples_.back().first, if
it exists? (last_call_time_ms_ *is* necessary if you take my advice about the
AdvanceTime() method.)

[ilnik, 2017/08/22 12:03:56]

It's necessary. We also need Max() to be called in correct temporal order.
Otherwise we can't throw out any samples in Max(), and can never implement it
efficiently. Even if no samples were added in between two Max calls: there may
be samples added window_len_ms milliseconds ago.

[kwiberg-webrtc, 2017/08/22 12:35:38]

If Max() is in fact called in the correct temporal order, you don't need this
member; you can just trust that the timestamp argument is correct. But having
the last call time saved here does enable you to DCHECK that the caller is doing
the right thing, so I agree that it's useful to have it here.

As an optimization, consider letting this member exist only if RTC_DCHECK_IS_ON.

[ilnik, 2017/08/22 13:04:38]

Done.

+
+  RTC_DISALLOW_COPY_AND_ASSIGN(MovingMaxCounter);

[kwiberg-webrtc, 2017/08/22 11:13:30]

Why? Copying a MovingMaxCounter should not be problematic.

[ilnik, 2017/08/22 12:03:56]

It doesn't introduce any problems, only if the realtime clock is used to get
time_ms. If, however, some fake clock is used, it will have to be copied
together with the counter. Also, it doesn't make any sense to copy a counter to
me. If you insist, I can remove this line, but other statistics counters are not
copyable too (e.g. webrtc/video/stats_counter.h)

[kwiberg-webrtc, 2017/08/22 12:35:37]

OK. Keep this as-is for now.

+};
+
+template <class T>
+MovingMaxCounter<T>::MovingMaxCounter(int64_t 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();
+  }
+  // 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 < time_ms) {
+    samples_.emplace_back(std::make_pair(time_ms, sample));
+  }
+}
+
+template <class T>
+rtc::Optional<T> MovingMaxCounter<T>::Max(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_;

[kwiberg-webrtc, 2017/08/22 11:13:30]

const

[ilnik, 2017/08/22 12:03:56]

Done.

+  while (!samples_.empty() && samples_.front().first < window_begin_ms) {
+    samples_.pop_front();
+  }

[kwiberg-webrtc, 2017/08/22 11:13:30]

I'm guessing it'll be faster (but not by a huge margin) to first find an
iterator that points to the first element you want to keep, and then make one
call to std::deque::erase().

[ilnik, 2017/08/22 12:03:56]

Done.

+}
+
+}  // namespace rtc
+
+#endif  // WEBRTC_RTC_BASE_MOVING_MAX_COUNTER_H_