FeedbackSignalAccumulator utility class for averaging feedback signals

content/browser/media/capture/time_weighted_average.cc

+// Copyright (c) 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "content/browser/media/capture/time_weighted_average.h"
+
+#include <cmath>
+
+namespace content {
+
+TimeWeightedAverage::TimeWeightedAverage(base::TimeDelta half_life)
+    : half_life_(half_life) {
+  DCHECK(half_life_ > base::TimeDelta());
+}
+
+void TimeWeightedAverage::Reset(double starting_value,
+                                base::TimeTicks timestamp) {
+  DCHECK(!timestamp.is_null());
+  last_reset_time_ = timestamp;
+  average_ = starting_value;
+  most_recent_value_ = starting_value;
+  most_recent_count_ = 1;
+  most_recent_timestamp_ = timestamp;
+  second_most_recent_timestamp_ = timestamp;
+}
+
+bool TimeWeightedAverage::Update(double value, base::TimeTicks timestamp) {
+  DCHECK(!last_reset_time_.is_null());
+
+  // Edge case: Multiple updates at reset timestamp.
+  if (timestamp == last_reset_time_) {
+    MergeWithMostRecentDataPoint(value);
+    average_ = most_recent_value_;
+    return true;
+  }
+
+  if (timestamp <= second_most_recent_timestamp_)
+    return false;  // Timestamp is too far out-of-order, or before last reset.
+
+  if (timestamp <= most_recent_timestamp_) {
+    // |timestamp| is one step out-of-order: Undo the most recent computation
+    // and then apply the updates in-order.
+    Undo(most_recent_value_,

[hubbe, 2015/05/06 17:54:49]

May I suggest that it might be easier to keep the internal state in a struct and
then have a "previous_state_" that you can revert to.

Even easier: Ignore out-of-order timestamps completely.

I think the behavior of this class is a little weird, because the amount of
allowed out-of-order-ness depends on the data I've given it recently. It seems
like the behavior would be more well defined if the amount of allowed
out-of-order-ness was purely time based, or if it wasn't allowed at all.

If I'm reading this code right, it also means that

   Update(5, t=1.0);
   Update(10, t=1.0+eps);

behave very differently from

   Update(10, t=1.0);
   Update(5, t=1.0+eps);

which seems odd.

[miu, 2015/05/09 22:08:21]

As discussed face-to-face, I removed all the out-of-order foo.

+         most_recent_timestamp_ - second_most_recent_timestamp_);
+
+    if (timestamp < most_recent_timestamp_) {
+      Apply(value, timestamp - second_most_recent_timestamp_);
+      second_most_recent_timestamp_ = timestamp;
+    } else /* if (timestamp == most_recent_timestamp_) */ {
+      MergeWithMostRecentDataPoint(value);
+    }
+  } else {
+    // Typical case: |timestamp| is in-order, so the most-recent data point is
+    // set to the current update value and timestamp.
+    second_most_recent_timestamp_ = most_recent_timestamp_;
+    most_recent_value_ = value;
+    most_recent_count_ = 1;
+    most_recent_timestamp_ = timestamp;
+  }
+
+  // Apply the update with the latest timestamp.
+  Apply(most_recent_value_,
+        most_recent_timestamp_ - second_most_recent_timestamp_);
+
+  return true;
+}
+
+void TimeWeightedAverage::Undo(double last_value, base::TimeDelta elapsed) {
+  const double elapsed_us = static_cast<double>(elapsed.InMicroseconds());
+  const double weight = elapsed_us / (elapsed_us + half_life_.InMicroseconds());
+  DCHECK_GE(weight, 0.0);
+  DCHECK_LT(weight, 1.0);
+  average_ -= weight * last_value;
+  average_ /= 1.0 - weight;
+  DCHECK(std::isfinite(average_));
+}
+
+void TimeWeightedAverage::Apply(double next_value, base::TimeDelta elapsed) {
+  const double elapsed_us = static_cast<double>(elapsed.InMicroseconds());
+  const double weight = elapsed_us / (elapsed_us + half_life_.InMicroseconds());
+  average_ = weight * next_value + (1.0 - weight) * average_;
+  DCHECK(std::isfinite(average_));
+}
+
+void TimeWeightedAverage::MergeWithMostRecentDataPoint(double value) {
+  most_recent_value_ = (most_recent_count_ * most_recent_value_ + value) /
+      (most_recent_count_ + 1);
+  ++most_recent_count_;
+}
+
+}  // namespace content