Efficient MetricRecorder

webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc

Index: webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc
diff --git a/webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc b/webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc
index 25e8989f5c5b8bd90012520d731195b3c4745f2a..eb068e5657bff848e2c0754e8e6dbf42ea3f8fa8 100644
--- a/webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc
+++ b/webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc
@@ -17,73 +17,14 @@ namespace testing {
 namespace bwe {
 
 namespace {
-
-template <typename T>
-T Sum(const std::vector<T>& input) {
-  T total = 0;
-  for (T val : input) {
-    total += val;
-  }
-  return total;
-}
-
-template <typename T>
-double Average(const std::vector<T>& array, size_t size) {
-  return static_cast<double>(Sum(array)) / size;
-}
-
-template <typename T>
-std::vector<T> Abs(const std::vector<T>& input) {
-  std::vector<T> output(input);
-  for (T val : output) {
-    val = std::abs(val);
-  }
-  return output;
-}
-
-template <typename T>
-std::vector<double> Pow(const std::vector<T>& input, double p) {
-  std::vector<double> output;
-  for (T val : input) {
-    output.push_back(pow(static_cast<double>(val), p));
-  }
-  return output;
-}
-
-template <typename T>
-double StandardDeviation(const std::vector<T>& array, size_t size) {
-  double mean = Average(array, size);
-  std::vector<double> square_values = Pow(array, 2.0);
-  double var = Average(square_values, size) - mean * mean;
-  return sqrt(var);
-}
-
 // Holder mean, Manhattan distance for p=1, EuclidianNorm/sqrt(n) for p=2.
 template <typename T>
-double NormLp(const std::vector<T>& array, size_t size, double p) {
-  std::vector<T> abs_values = Abs(array);
-  std::vector<double> pow_values = Pow(abs_values, p);
-  return pow(Sum(pow_values) / size, 1.0 / p);
+double NormLp(T sum, size_t size, double p) {
+  return pow(sum / size, 1.0 / p);
 }
-
-template <typename T>
-std::vector<T> PositiveFilter(const std::vector<T>& input) {
-  std::vector<T> output(input);
-  for (T val : output) {
-    val = val > 0 ? val : 0;
-  }
-  return output;
 }
 
-template <typename T>
-std::vector<T> NegativeFilter(const std::vector<T>& input) {
-  std::vector<T> output(input);
-  for (T val : output) {
-    val = val < 0 ? -val : 0;
-  }
-  return output;
-}
-}  // namespace
+const double kP = 1.0;  // Used for Norm Lp.
 
 LinkShare::LinkShare(ChokeFilter* choke_filter)
     : choke_filter_(choke_filter), running_flows_(choke_filter->flow_ids()) {
@@ -119,14 +60,17 @@ MetricRecorder::MetricRecorder(const std::string algorithm_name,
       packet_sender_(packet_sender),
       link_share_(link_share),
       now_ms_(0),
-      delays_ms_(),
-      throughput_bytes_(),
-      weighted_estimate_error_(),
+      sum_delays_ms_(0),
+      delay_histogram_ms_(),
+      sum_delays_square_ms2_(0),
+      sum_throughput_bytes_(0),
       last_unweighted_estimate_error_(0),
       optimal_throughput_bits_(0),
       last_available_bitrate_per_flow_kbps_(0),
       start_computing_metrics_ms_(0),
-      started_computing_metrics_(false) {
+      started_computing_metrics_(false),
+      num_packets_received_(0) {
+  std::fill_n(sum_lp_weighted_estimate_error_, 2, 0);
 }
 
 void MetricRecorder::SetPlotInformation(
@@ -224,27 +168,48 @@ void MetricRecorder::UpdateObjective() {
 }
 
 uint32_t MetricRecorder::GetTotalAvailableKbps() {
+  if (link_share_ == nullptr)
+    return 0;
   return link_share_->TotalAvailableKbps();
 }
 
 uint32_t MetricRecorder::GetAvailablePerFlowKbps() {
+  if (link_share_ == nullptr)
+    return 0;
   return link_share_->AvailablePerFlowKbps(flow_id_);
 }
 
 uint32_t MetricRecorder::GetSendingEstimateKbps() {
+  if (packet_sender_ == nullptr)
+    return 0;
   return packet_sender_->TargetBitrateKbps();
 }
 
 void MetricRecorder::PushDelayMs(int64_t delay_ms, int64_t arrival_time_ms) {
   if (ShouldRecord(arrival_time_ms)) {
-    delays_ms_.push_back(delay_ms);
+    sum_delays_ms_ += delay_ms;
+    sum_delays_square_ms2_ += delay_ms * delay_ms;
+    if (delay_histogram_ms_.find(delay_ms) == delay_histogram_ms_.end()) {
+      delay_histogram_ms_[delay_ms] = 0;
+    }
+    ++delay_histogram_ms_[delay_ms];
+  }
+}
+
+void MetricRecorder::UpdateEstimateError(int64_t new_value) {
+  int64_t lp_value = pow(static_cast<double>(std::abs(new_value)), kP);
+  if (new_value < 0) {
+    sum_lp_weighted_estimate_error_[0] += lp_value;
+  } else {
+    sum_lp_weighted_estimate_error_[1] += lp_value;
   }
 }
 
 void MetricRecorder::PushThroughputBytes(size_t payload_size,
                                          int64_t arrival_time_ms) {
   if (ShouldRecord(arrival_time_ms)) {
-    throughput_bytes_.push_back(payload_size);
+    ++num_packets_received_;
+    sum_throughput_bytes_ += payload_size;
 
     int64_t current_available_per_flow_kbps =
         static_cast<int64_t>(GetAvailablePerFlowKbps());
@@ -253,10 +218,12 @@ void MetricRecorder::PushThroughputBytes(size_t payload_size,
         static_cast<int64_t>(GetSendingEstimateKbps()) -
         current_available_per_flow_kbps;
 
-    weighted_estimate_error_.push_back(
-        ((current_bitrate_diff_kbps + last_unweighted_estimate_error_) *
-         (arrival_time_ms - plot_information_[kThroughput].time_ms)) /
-        2);
+    int64_t weighted_estimate_error =
+        (((current_bitrate_diff_kbps + last_unweighted_estimate_error_) *
+          (arrival_time_ms - plot_information_[kThroughput].time_ms)) /
+         2);
+
+    UpdateEstimateError(weighted_estimate_error);
 
     optimal_throughput_bits_ +=
         ((current_available_per_flow_kbps +
@@ -281,56 +248,21 @@ bool MetricRecorder::ShouldRecord(int64_t arrival_time_ms) {
   }
 }
 
-// The weighted_estimate_error_ was weighted based on time windows.
-// This function scales back the result before plotting.
-double MetricRecorder::Renormalize(double x) {
-  size_t num_packets_received = delays_ms_.size();
-  return (x * num_packets_received) / now_ms_;
-}
+void MetricRecorder::PlotThroughputHistogram(
+    const std::string& title,
+    const std::string& bwe_name,
+    size_t num_flows,
+    int64_t extra_offset_ms,
+    const std::string optimum_id) const {
+  double optimal_bitrate_per_flow_kbps = static_cast<double>(
+      optimal_throughput_bits_ / RunDurationMs(extra_offset_ms));
 
-inline double U(int64_t x, double alpha) {
-  if (alpha == 1.0) {
-    return log(static_cast<double>(x));
-  }
-  return pow(static_cast<double>(x), 1.0 - alpha) / (1.0 - alpha);
-}
-
-inline double U(size_t x, double alpha) {
-  return U(static_cast<int64_t>(x), alpha);
-}
+  double neg_error = Renormalize(
+      NormLp(sum_lp_weighted_estimate_error_[0], num_packets_received_, kP));
+  double pos_error = Renormalize(
+      NormLp(sum_lp_weighted_estimate_error_[1], num_packets_received_, kP));
 
-// TODO(magalhaesc): Update ObjectiveFunction.
-double MetricRecorder::ObjectiveFunction() {
-  const double kDelta = 0.15;  // Delay penalty factor.
-  const double kAlpha = 1.0;
-  const double kBeta = 1.0;
-
-  double throughput_metric = U(Sum(throughput_bytes_), kAlpha);
-  double delay_penalty = kDelta * U(Sum(delays_ms_), kBeta);
-
-  return throughput_metric - delay_penalty;
-}
-
-void MetricRecorder::PlotThroughputHistogram(const std::string& title,
-                                             const std::string& bwe_name,
-                                             size_t num_flows,
-                                             int64_t extra_offset_ms,
-                                             const std::string optimum_id) {
-  size_t num_packets_received = delays_ms_.size();
-
-  int64_t duration_ms = now_ms_ - start_computing_metrics_ms_ - extra_offset_ms;
-
-  double average_bitrate_kbps =
-      static_cast<double>(8 * Sum(throughput_bytes_) / duration_ms);
-
-  double optimal_bitrate_per_flow_kbps =
-      static_cast<double>(optimal_throughput_bits_ / duration_ms);
-
-  std::vector<int64_t> positive = PositiveFilter(weighted_estimate_error_);
-  std::vector<int64_t> negative = NegativeFilter(weighted_estimate_error_);
-
-  double p_error = Renormalize(NormLp(positive, num_packets_received, 1.0));
-  double n_error = Renormalize(NormLp(negative, num_packets_received, 1.0));
+  double average_bitrate_kbps = AverageBitrateKbps(extra_offset_ms);
 
   // Prevent the error to be too close to zero (plotting issue).
   double extra_error = average_bitrate_kbps / 500;
@@ -341,8 +273,8 @@ void MetricRecorder::PlotThroughputHistogram(const std::string& title,
   BWE_TEST_LOGGING_LABEL(4, title, "average_bitrate_(kbps)", num_flows);
   BWE_TEST_LOGGING_LIMITERRORBAR(
       4, bwe_name, average_bitrate_kbps,
-      average_bitrate_kbps - n_error - extra_error,
-      average_bitrate_kbps + p_error + extra_error, "estimate_error",
+      average_bitrate_kbps - neg_error - extra_error,
+      average_bitrate_kbps + pos_error + extra_error, "estimate_error",
       optimal_bitrate_per_flow_kbps, optimum_title, flow_id_);
 
   BWE_TEST_LOGGING_LOG1("RESULTS >>> " + bwe_name + " Channel utilization : ",
@@ -350,8 +282,8 @@ void MetricRecorder::PlotThroughputHistogram(const std::string& title,
                         100.0 * static_cast<double>(average_bitrate_kbps) /
                             optimal_bitrate_per_flow_kbps);
 
-  RTC_UNUSED(p_error);
-  RTC_UNUSED(n_error);
+  RTC_UNUSED(pos_error);
+  RTC_UNUSED(neg_error);
   RTC_UNUSED(extra_error);
   RTC_UNUSED(optimal_bitrate_per_flow_kbps);
 }
@@ -359,32 +291,22 @@ void MetricRecorder::PlotThroughputHistogram(const std::string& title,
 void MetricRecorder::PlotThroughputHistogram(const std::string& title,
                                              const std::string& bwe_name,
                                              size_t num_flows,
-                                             int64_t extra_offset_ms) {
+                                             int64_t extra_offset_ms) const {
   PlotThroughputHistogram(title, bwe_name, num_flows, extra_offset_ms, "");
 }
 
 void MetricRecorder::PlotDelayHistogram(const std::string& title,
                                         const std::string& bwe_name,
                                         size_t num_flows,
-                                        int64_t one_way_path_delay_ms) {
-  size_t num_packets_received = delays_ms_.size();
-  double average_delay_ms = Average(delays_ms_, num_packets_received);
+                                        int64_t one_way_path_delay_ms) const {
+  double average_delay_ms =
+      static_cast<double>(sum_delays_ms_) / num_packets_received_;
 
   // Prevent the error to be too close to zero (plotting issue).
   double extra_error = average_delay_ms / 500;
-
-  double tenth_sigma_ms =
-      StandardDeviation(delays_ms_, num_packets_received) / 10.0 + extra_error;
-
-  size_t per_5_index = (num_packets_received - 1) / 20;
-  std::nth_element(delays_ms_.begin(), delays_ms_.begin() + per_5_index,
-                   delays_ms_.end());
-  int64_t percentile_5_ms = delays_ms_[per_5_index];
-
-  size_t per_95_index = num_packets_received - 1 - per_5_index;
-  std::nth_element(delays_ms_.begin(), delays_ms_.begin() + per_95_index,
-                   delays_ms_.end());
-  int64_t percentile_95_ms = delays_ms_[per_95_index];
+  double tenth_sigma_ms = DelayStdDev() / 10.0 + extra_error;
+  int64_t percentile_5_ms = NthDelayPercentile(5);
+  int64_t percentile_95_ms = NthDelayPercentile(95);
 
   BWE_TEST_LOGGING_LABEL(5, title, "average_delay_(ms)", num_flows)
   BWE_TEST_LOGGING_ERRORBAR(5, bwe_name, average_delay_ms, percentile_5_ms,
@@ -407,7 +329,7 @@ void MetricRecorder::PlotDelayHistogram(const std::string& title,
 void MetricRecorder::PlotLossHistogram(const std::string& title,
                                        const std::string& bwe_name,
                                        size_t num_flows,
-                                       float global_loss_ratio) {
+                                       float global_loss_ratio) const {
   BWE_TEST_LOGGING_LABEL(6, title, "packet_loss_ratio_(%)", num_flows)
   BWE_TEST_LOGGING_BAR(6, bwe_name, 100.0f * global_loss_ratio, flow_id_);
 
@@ -417,7 +339,7 @@ void MetricRecorder::PlotLossHistogram(const std::string& title,
 
 void MetricRecorder::PlotObjectiveHistogram(const std::string& title,
                                             const std::string& bwe_name,
-                                            size_t num_flows) {
+                                            size_t num_flows) const {
   BWE_TEST_LOGGING_LABEL(7, title, "objective_function", num_flows)
   BWE_TEST_LOGGING_BAR(7, bwe_name, ObjectiveFunction(), flow_id_);
 }
@@ -444,6 +366,73 @@ void MetricRecorder::ResumeFlow(int64_t paused_time_ms) {
   link_share_->ResumeFlow(flow_id_);
 }
 
+double MetricRecorder::AverageBitrateKbps(int64_t extra_offset_ms) const {
+  int64_t duration_ms = RunDurationMs(extra_offset_ms);
+  if (duration_ms == 0)
+    return 0.0;
+  return static_cast<double>(8 * sum_throughput_bytes_ / duration_ms);
+}
+
+int64_t MetricRecorder::RunDurationMs(int64_t extra_offset_ms) const {
+  return now_ms_ - start_computing_metrics_ms_ - extra_offset_ms;
+}
+
+double MetricRecorder::DelayStdDev() const {
+  if (num_packets_received_ == 0) {
+    return 0.0;
+  }
+  double mean = static_cast<double>(sum_delays_ms_) / num_packets_received_;
+  double mean2 =
+      static_cast<double>(sum_delays_square_ms2_) / num_packets_received_;
+  return sqrt(mean2 - pow(mean, 2.0));
+}
+
+// Since delay values are bounded in a subset of [0, 5000] ms,
+// this function's execution time is O(1), independend of num_packets_received_.
+int64_t MetricRecorder::NthDelayPercentile(int n) const {
+  if (num_packets_received_ == 0) {
+    return 0;
+  }
+  size_t num_packets_remaining = (n * num_packets_received_) / 100;
+  for (auto hist : delay_histogram_ms_) {
+    if (num_packets_remaining <= hist.second)
+      return static_cast<int64_t>(hist.first);
+    num_packets_remaining -= hist.second;
+  }
+
+  assert(false);
+  return -1;
+}
+
+// The weighted_estimate_error_ was weighted based on time windows.
+// This function scales back the result before plotting.
+double MetricRecorder::Renormalize(double x) const {
+  return (x * num_packets_received_) / now_ms_;
+}
+
+inline double U(int64_t x, double alpha) {
+  if (alpha == 1.0) {
+    return log(static_cast<double>(x));
+  }
+  return pow(static_cast<double>(x), 1.0 - alpha) / (1.0 - alpha);
+}
+
+inline double U(size_t x, double alpha) {
+  return U(static_cast<int64_t>(x), alpha);
+}
+
+// TODO(magalhaesc): Update ObjectiveFunction.
+double MetricRecorder::ObjectiveFunction() const {
+  const double kDelta = 0.15;  // Delay penalty factor.
+  const double kAlpha = 1.0;
+  const double kBeta = 1.0;
+
+  double throughput_metric = U(sum_throughput_bytes_, kAlpha);
+  double delay_penalty = kDelta * U(sum_delays_ms_, kBeta);
+
+  return throughput_metric - delay_penalty;
+}
+
 }  // namespace bwe
 }  // namespace testing
 }  // namespace webrtc