Efficient MetricRecorder

Efficient Metric Recorder

Computing all metrics using constant extra memory.
PlotHistogram methods are executed in constant time.
-- Previously throughput and delay were using O(num_packets) extra memory and their associated PlotHistograms took linear time complexity.

Added MetricRecorder unittests

R=stefan@webrtc.org

Committed: https://chromium.googlesource.com/external/webrtc/+/e2cb1f12c3d1c5500de1b733dfc8bbfea504d89f

[magalhaesc, 2015-07-26 00:24:38]

magalhaesc@google.com changed reviewers:
+ stefan@webrtc.org

[magalhaesc, 2015-07-26 00:31:03]

Added a comment

[magalhaesc, 2015-07-26 01:08:02]

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
File webrtc/modules/remote_bitrate_estimator/test/metric_recorder.h (right):

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
webrtc/modules/remote_bitrate_estimator/test/metric_recorder.h:162: int64_t
sum_delays_square_ms2_;  // Used to compute standar deviation.
standard

[magalhaesc, 2015-07-26 01:10:22]

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
File webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc (right):

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc:346: for (auto
rit = delay_histogram_ms_.rbegin();
This slight optimization for n>50 can be removed if you think it adds complexity
to the code's readability.

[magalhaesc, 2015-07-27 05:14:14]

Thanks for the suggestion, MetricRecorder is now much more efficient.

[stefan-webrtc, 2015-07-27 07:55:22]

lgtm, but please remove the n>50 code, since as you said, it adds unnecessary
complexity.

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
File webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc (right):

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc:186: if
(delay_histogram_ms_.find(delay_ms) == delay_histogram_ms_.end()) {
This means that we don't have any limits on the number of bins. May not be
needed since we usually don't have more than 1000 ms delay.

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc:337: for (auto
it = delay_histogram_ms_.begin(); it != delay_histogram_ms_.end();
for (auto it : delay_histogram_ms_)

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc:346: for (auto
rit = delay_histogram_ms_.rbegin();
On 2015/07/26 01:10:21, magalhaesc wrote:
> This slight optimization for n>50 can be removed if you think it adds
complexity
> to the code's readability.

Yeah, I don't think it's worth optimizing this code since it runs only twice. :)

[magalhaesc, 2015-07-29 18:04:37]

Comments addressed

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
File webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc (right):

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc:186: if
(delay_histogram_ms_.find(delay_ms) == delay_histogram_ms_.end()) {
On 2015/07/27 07:55:22, stefan-webrtc (holmer) wrote:
> This means that we don't have any limits on the number of bins. May not be
> needed since we usually don't have more than 1000 ms delay.

True. We can use an array with e.g. 1000 elements. On one hand, element access
will be faster. On the other, we will probably end up allocating unnecessary
memory and go through unfilled elements (at least all those below
kOneWayPathDelay) when searching for the percentiles.

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc:337: for (auto
it = delay_histogram_ms_.begin(); it != delay_histogram_ms_.end();
On 2015/07/27 07:55:22, stefan-webrtc (holmer) wrote:
> for (auto it : delay_histogram_ms_)

Done.

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc:346: for (auto
rit = delay_histogram_ms_.rbegin();
On 2015/07/27 07:55:22, stefan-webrtc (holmer) wrote:
> On 2015/07/26 01:10:21, magalhaesc wrote:
> > This slight optimization for n>50 can be removed if you think it adds
> complexity
> > to the code's readability.
> 
> Yeah, I don't think it's worth optimizing this code since it runs only twice.
:)

Done.

[magalhaesc, 2015-07-29 18:38:49]

Added MetricRecorder unittests

[magalhaesc, 2015-07-29 18:39:21]

Patchset #3 (id:40001) has been deleted

[magalhaesc, 2015-07-30 08:33:42]

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
File webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc (right):

https://codereview.webrtc.org/1257683006/diff/20001/webrtc/modules/remote_bit...
webrtc/modules/remote_bitrate_estimator/test/metric_recorder.cc:186: if
(delay_histogram_ms_.find(delay_ms) == delay_histogram_ms_.end()) {
On 2015/07/29 18:04:37, magalhaesc wrote:
> On 2015/07/27 07:55:22, stefan-webrtc (holmer) wrote:
> > This means that we don't have any limits on the number of bins. May not be
> > needed since we usually don't have more than 1000 ms delay.
> 
> True. We can use an array with e.g. 1000 elements. On one hand, element access
> will be faster. On the other, we will probably end up allocating unnecessary
> memory and go through unfilled elements (at least all those below
> kOneWayPathDelay) when searching for the percentiles. 

Which one do you prefer?

[magalhaesc, 2015-07-30 08:35:53]

Added MetricRecorder unittests

[magalhaesc, 2015-07-30 09:22:00]

Rebased on master

[magalhaesc, 2015-07-30 09:22:19]

Committed patchset #4 (id:80001) manually as
e2cb1f12c3d1c5500de1b733dfc8bbfea504d89f (presubmit successful).