NetEq/ACM: Refactor how packet waiting times are calculated

webrtc/modules/audio_coding/neteq/statistics_calculator.cc

Index: webrtc/modules/audio_coding/neteq/statistics_calculator.cc
diff --git a/webrtc/modules/audio_coding/neteq/statistics_calculator.cc b/webrtc/modules/audio_coding/neteq/statistics_calculator.cc
index ce800dd065d0b291b2b5cdfea08c360393f21ef9..b44bfc34f7327a14fef2425c73ba3753dd9033b0 100644
--- a/webrtc/modules/audio_coding/neteq/statistics_calculator.cc
+++ b/webrtc/modules/audio_coding/neteq/statistics_calculator.cc
@@ -12,12 +12,17 @@
 
 #include <assert.h>
 #include <string.h>  // memset
+#include <iterator>
 
+#include "webrtc/base/checks.h"
 #include "webrtc/modules/audio_coding/neteq/decision_logic.h"
 #include "webrtc/modules/audio_coding/neteq/delay_manager.h"
 
 namespace webrtc {
 
+// Allocating the static const so that it can be passed by reference to DCHECK.
+const size_t StatisticsCalculator::kLenWaitingTimes;
+
 StatisticsCalculator::StatisticsCalculator()
     : preemptive_samples_(0),
       accelerate_samples_(0),
@@ -27,12 +32,11 @@ StatisticsCalculator::StatisticsCalculator()
       discarded_packets_(0),
       lost_timestamps_(0),
       timestamps_since_last_report_(0),
-      len_waiting_times_(0),
-      next_waiting_time_index_(0),
       secondary_decoded_samples_(0) {
-  memset(waiting_times_, 0, kLenWaitingTimes * sizeof(waiting_times_[0]));
 }
 
+StatisticsCalculator::~StatisticsCalculator() = default;
+
 void StatisticsCalculator::Reset() {
   preemptive_samples_ = 0;
   accelerate_samples_ = 0;
@@ -40,6 +44,7 @@ void StatisticsCalculator::Reset() {
   expanded_speech_samples_ = 0;
   expanded_noise_samples_ = 0;
   secondary_decoded_samples_ = 0;
+  waiting_times_.clear();
 }
 
 void StatisticsCalculator::ResetMcu() {
@@ -48,12 +53,6 @@ void StatisticsCalculator::ResetMcu() {
   timestamps_since_last_report_ = 0;
 }
 
-void StatisticsCalculator::ResetWaitingTimeStatistics() {
-  memset(waiting_times_, 0, kLenWaitingTimes * sizeof(waiting_times_[0]));
-  len_waiting_times_ = 0;
-  next_waiting_time_index_ = 0;
-}
-
 void StatisticsCalculator::ExpandedVoiceSamples(int num_samples) {
   expanded_speech_samples_ += num_samples;
 }
@@ -97,15 +96,12 @@ void StatisticsCalculator::SecondaryDecodedSamples(int num_samples) {
 }
 
 void StatisticsCalculator::StoreWaitingTime(int waiting_time_ms) {
-  assert(next_waiting_time_index_ < kLenWaitingTimes);
-  waiting_times_[next_waiting_time_index_] = waiting_time_ms;
-  next_waiting_time_index_++;
-  if (next_waiting_time_index_ >= kLenWaitingTimes) {
-    next_waiting_time_index_ = 0;
-  }
-  if (len_waiting_times_ < kLenWaitingTimes) {
-    len_waiting_times_++;
+  DCHECK_LE(waiting_times_.size(), kLenWaitingTimes);
+  while (waiting_times_.size() >= kLenWaitingTimes) {
+    // Erase first value.
+    waiting_times_.pop_front();

[minyue-webrtc, 2015/08/19 11:21:52]

Ok, I see the deletion according to age here.

   }
+  waiting_times_.push_back(waiting_time_ms);
 }
 
 void StatisticsCalculator::GetNetworkStatistics(
@@ -155,19 +151,37 @@ void StatisticsCalculator::GetNetworkStatistics(
       CalculateQ14Ratio(secondary_decoded_samples_,
                         timestamps_since_last_report_);
 
+  if (waiting_times_.size() == 0) {
+    stats->mean_waiting_time_ms = -1;
+    stats->median_waiting_time_ms = -1;
+    stats->min_waiting_time_ms = -1;
+    stats->max_waiting_time_ms = -1;
+  } else {
+    waiting_times_.sort();

[minyue-webrtc, 2015/08/18 12:55:34]

std::vector may be faster than std::list in sorting small data types.

I prefer to use std::lower_bound to find a position when we add new value, so
that it is already sorted here, to make the computation de-centralized.

[hlundin-webrtc, 2015/08/19 08:28:39]

That won't work. The list is sorted in time order, so that old data can be
deleted when new is inserted. It can only be sorted when the stats are averaged,
since the list is cleared after that.

[minyue-webrtc, 2015/08/19 11:21:52]

Acknowledged.

+    // Find mid-point elements. If the size is odd, the two iterators
+    // |middle_left| and |middle_right| will both point to the middle element
+    // after these operations; if the size is even, they will point to the two
+    // neighboring elements at the middle of the list.
+    auto middle_left = waiting_times_.begin();
+    std::advance(middle_left, (waiting_times_.size() - 1) / 2);
+    auto middle_right = waiting_times_.rbegin();
+    std::advance(middle_right, (waiting_times_.size() - 1) / 2);
+    // Calculate the average of the two. (Works also for odd sizes.)
+    stats->median_waiting_time_ms = (*middle_left + *middle_right) / 2;
+    stats->min_waiting_time_ms = waiting_times_.front();
+    stats->max_waiting_time_ms = waiting_times_.back();
+    double sum = 0;
+    for (auto time : waiting_times_) {
+      sum += time;

[minyue-webrtc, 2015/08/18 12:55:34]

can also sum when adding.

[hlundin-webrtc, 2015/08/19 08:28:39]

I'm worried about numerical stability. We would have to add when new values go
in, and subtract again as they become too old and are purged. Doing this in
floating-point is likely going to cause drift.

[minyue-webrtc, 2015/08/19 11:21:52]

Acknowledged.

+    }
+    stats->mean_waiting_time_ms = static_cast<int>(sum / waiting_times_.size());
+  }
+
   // Reset counters.
   ResetMcu();
   Reset();
 }
 
-void StatisticsCalculator::WaitingTimes(std::vector<int>* waiting_times) {
-  if (!waiting_times) {
-    return;
-  }
-  waiting_times->assign(waiting_times_, waiting_times_ + len_waiting_times_);
-  ResetWaitingTimeStatistics();
-}
-
 uint16_t StatisticsCalculator::CalculateQ14Ratio(uint32_t numerator,
                                                  uint32_t denominator) {
   if (numerator == 0) {