Added a new echo likelihood stat that reports the maximum value from a previous time period.

webrtc/modules/audio_processing/echo_detector/likelihood_aggregator.cc

+/*
+ *  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.
+ */
+
+#include "webrtc/modules/audio_processing/echo_detector/likelihood_aggregator.h"
+
+#include <algorithm>
+
+#include "webrtc/base/checks.h"
+
+namespace webrtc {
+
+LikelihoodAggregator::LikelihoodAggregator(size_t window_size_frames)
+    : recent_values_(window_size_frames) {

[peah-webrtc, 2017/01/13 12:49:02]

I think that if you initialize the maximum_candidates_ to window_size_frames,
that would ensure that there is no reallocation in the deque, right?

[ivoc, 2017/01/13 13:24:23]

I don't think that's entirely true. The values in the deque can drift from their
starting position in memory. If you consider the case where the likelihood
values are a decreasing sequence, the new values will constantly be pushed to
the back of the deque, while the old values will get removed from the front.
This effect can cause allocation of new blocks to be necessary.

[peah-webrtc, 2017/01/13 13:37:34]

Good point! I did not know that.

+  RTC_DCHECK_GT(window_size_frames, 0);
+}
+
+LikelihoodAggregator::~LikelihoodAggregator() {}
+
+void LikelihoodAggregator::Update(float value) {
+  // If the new value is larger than any of the candidates, those candidates can
+  // be removed because they are older and have a smaller value, so they can
+  // never become the maximum in the future.
+  while (!maximum_candidates_.empty() &&

[peah-webrtc, 2017/01/13 12:49:02]

In it's current use in the residual echo detector,  window_size_frames is 1000,
right? 

Afaics, the worst case performance of this loop is that it can consist of
looping through window_size_frames values, so even though this way of finding
the maximum is more efficient on average data, it can be quite complex as this
happens for each frame, right?

Would it be possible to do this in a more efficient way? Considering the above,
as the Max() operation is called less frequently, wouldn't it be better to do a
linear search each time Max() is called?

An alternative is to have a leaking maximum statistics implementation such as 

if (value > max_value_) {
 max_value_ = value;
 counter = 0;
}

if (counter_ > 1000) {
 max_value_ *= 0.99f;
}
else {
 ++counter;
}

That solution is supercheap, and even though approximate, it is probably still
accurate enough as the value it measures is as well averaged over a long data
segment.

WDYT?

[ivoc, 2017/01/13 13:24:23]

You're right that when considering a single call to this function, it can loop
through all elements (O(N)), which is indeed pretty slow (this can only happen
once every N calls though). This function is pretty fast on average, but
sometimes it can be slow. 

Your solution looks like a better idea, thanks for the suggestion, I'll rework
the class to use this implementation.

[peah-webrtc, 2017/01/13 13:37:34]

Acknowledged.

+         value >= recent_values_[maximum_candidates_.back()]) {
+    maximum_candidates_.pop_back();
+  }
+  // If the front (and oldest) candidate is too old, remove it.
+  if (!maximum_candidates_.empty() &&
+      maximum_candidates_.front() == insertion_index_) {
+    maximum_candidates_.pop_front();
+  }
+  maximum_candidates_.push_back(insertion_index_);

[peah-webrtc, 2017/01/13 12:49:02]

This is potentially an expensive operation as it may cause a reallocation. Would
it be possible to do it in a way that ensures that no reallocation is performed?

[ivoc, 2017/01/13 13:24:23]

In a deque it should not cause reallocation (so nothing has to be moved to a new
memory location), but it can cause allocation of a new block (a deque is stored
in multiple array-like blocks in memory). It may be possible to store
maximum_candidates_ in a ring-buffer as well, which would avoid any memory
operations.

[peah-webrtc, 2017/01/13 13:37:34]

Ah, I did not know that the deque was stored like that. Yes, using a ring-buffer
for that sounds like a good suggestion.

+  recent_values_[insertion_index_] = value;
+  insertion_index_++;
+  insertion_index_ %= recent_values_.size();
+}
+
+float LikelihoodAggregator::Max() const {

[hlundin-webrtc, 2017/01/13 13:38:32]

Now it is very cheap again, so max() would be ok. Up to you...

[ivoc, 2017/01/13 14:40:36]

I lowercased it again :-)

+  if (!maximum_candidates_.empty()) {
+    return recent_values_[maximum_candidates_.front()];
+  } else {
+    return 0.f;
+  }
+}
+
+void LikelihoodAggregator::Clear() {
+  std::fill(recent_values_.begin(), recent_values_.end(), 0.f);
+  maximum_candidates_.clear();
+}
+
+}  // namespace webrtc