NetEq/ACM: Refactor how packet waiting times are calculated

webrtc/modules/audio_coding/neteq/statistics_calculator.cc

 /*
  *  Copyright (c) 2013 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_coding/neteq/statistics_calculator.h"
 
 #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),
       added_zero_samples_(0),
       expanded_speech_samples_(0),
       expanded_noise_samples_(0),
       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;
   added_zero_samples_ = 0;
   expanded_speech_samples_ = 0;
   expanded_noise_samples_ = 0;
   secondary_decoded_samples_ = 0;
+  waiting_times_.clear();
 }
 
 void StatisticsCalculator::ResetMcu() {
   discarded_packets_ = 0;
   lost_timestamps_ = 0;
   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;
 }
 
 void StatisticsCalculator::ExpandedNoiseSamples(int num_samples) {
   expanded_noise_samples_ += num_samples;
 }
 
 void StatisticsCalculator::PreemptiveExpandedSamples(int num_samples) {
   preemptive_samples_ += num_samples;
@@ skipping 23 matching lines @@
     timestamps_since_last_report_ = 0;
     discarded_packets_ = 0;
   }
 }
 
 void StatisticsCalculator::SecondaryDecodedSamples(int num_samples) {
   secondary_decoded_samples_ += 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;
+  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.

   }
-  if (len_waiting_times_ < kLenWaitingTimes) {
-    len_waiting_times_++;
-  }
+  waiting_times_.push_back(waiting_time_ms);
 }
 
 void StatisticsCalculator::GetNetworkStatistics(
     int fs_hz,
     int num_samples_in_buffers,
     int samples_per_packet,
     const DelayManager& delay_manager,
     const DecisionLogic& decision_logic,
     NetEqNetworkStatistics *stats) {
   if (fs_hz <= 0 || !stats) {
@@ skipping 29 matching lines @@
                         timestamps_since_last_report_);
 
   stats->speech_expand_rate =
       CalculateQ14Ratio(expanded_speech_samples_,
                         timestamps_since_last_report_);
 
   stats->secondary_decoded_rate =
       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) {
     return 0;
   } else if (numerator < denominator) {
     // Ratio must be smaller than 1 in Q14.
     assert((numerator << 14) / denominator < (1 << 14));
     return static_cast<uint16_t>((numerator << 14) / denominator);
   } else {
     // Will not produce a ratio larger than 1, since this is probably an error.
     return 1 << 14;
   }
 }
 
 }  // namespace webrtc