Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2512693002:
Implement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation). (Closed)
DescriptionImplement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation).
Theil and Sen's estimator essentially looks at the line through every pair of points and selects the median slope. This is robust to corruption of up to 29% of the data points.
Wire up new estimator to field trial experiment. Add unit and integration tests. Results are promising.
BUG=webrtc:6728
Committed: https://crrev.com/5a388368a220cb975cbada5129dd94a104a77497
Cr-Commit-Position: refs/heads/master@{#15508}
Patch Set 1 #Patch Set 2 : Simple performance fixes. About 3 times faster. #Patch Set 3 : Use PercentileFilter to find median slope #
Total comments: 34
Patch Set 4 : Review comments #
Total comments: 1
Patch Set 5 : Rebase #Patch Set 6 : Add comments. Add method to clear a PercentileFilter. #Patch Set 7 : Rename to MedianSlopeEstimator #Patch Set 8 : Comment and unit test for PecentileFilter::Clear() #
Total comments: 3
Patch Set 9 : Unit test for return value of PercentileFilter::Erase #
Total comments: 9
Patch Set 10 : Comments from magjed #Patch Set 11 : Remove PercentileFilter::Clear since no longer used. #Messages
Total messages: 50 (32 generated)
The CQ bit was checked by terelius@webrtc.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...
Stefan, FYI. It is still slow compared to the existing estimators and I will continue to look into improvements.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
The CQ bit was checked by terelius@webrtc.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...
terelius@webrtc.org changed reviewers: + brandtr@webrtc.org, stefan@webrtc.org
Rasmus and Stefan, please review this CL when you have time. It is now comparable to the TrendlineFilter in terms of computational cost.
Description was changed from ========== Implement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation). Theil and Sen's estimator essentially looks at the line through every pair of points and selects the median slope. This is robust to corruption of up to 29% of the data points. Wire up new estimator to field trial experiment. Add unit and integration tests. Results are very promising, but the estimator is computationally slow. BUG=webrtc:6728 ========== to ========== Implement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation). Theil and Sen's estimator essentially looks at the line through every pair of points and selects the median slope. This is robust to corruption of up to 29% of the data points. Wire up new estimator to field trial experiment. Add unit and integration tests. Results are promising. BUG=webrtc:6728 ==========
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
https://codereview.webrtc.org/2512693002/diff/40001/webrtc/base/analytics/per... File webrtc/base/analytics/percentile_filter.h (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/base/analytics/per... webrtc/base/analytics/percentile_filter.h:37: // the size of the container. Comment on what this returns https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/theil_sen_estimator.cc (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:49: std::pair<double, double> old_delay = delay_hist_.front(); I think auto would be fine here if you'd prefer that. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:55: if (!median_filter_.Erase(slope)) {} https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:57: "a bug, likely related to rounding."; Should this happen? Otherwise a DCHECK might make sense? https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:71: if (delay_hist_.size() == window_size_) { Feel free to remove {}
Interesting estimator that I hadn't heard about before! It's also nice to see that it has performance guarantees w.r.t. to outliers. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/delay_based_bwe.cc (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/delay_based_bwe.cc:75: bool ReadTrendlineFilterExperimentParameters(size_t* window_points, window_size? Here and in function below. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/delay_based_bwe.h (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/delay_based_bwe.h:86: const bool in_trendline_experiment_; You might want to rename this in the future, as the Theil-Sen experiment also is kind of a trendline experiment. Same goes for the class name on row 93. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/delay_based_bwe_unittest.cc (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/delay_based_bwe_unittest.cc:239: bitrate_estimator_.reset(new DelayBasedBwe(&clock_)); I think you could move this to the constructor? https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/theil_sen_estimator.cc (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:22: enum { kDeltaCounterMax = 1000 }; Can you use a constexpr size_t instead? https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:47: // First remove the oldest N-1 slopes if the window is full. This could be a computer science thing, but it's not immediately obvious to me that |N| corresponds to the number of points in the data structure. Would be nice to point this out, for SP people like me ;) Also, consider rephrasing comment as: "remove the N-1 slopes that belong to the oldest point". The idea being that just because a slope partially belongs to an old point, doesn't mean that the slope itself is old. E.g., the slope between the oldest point and the newest point is just as new as the slope between the second newest point and the newest point. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:54: (new_delay.first - old_delay.first); I see the problem here that you were discussing before. One possible solution, which would not involve changing the percentile filter interface, would be to quantize the slopes before inserting them into the filter. As long as the quantization error is larger than the numerical error in calculating the division, you should always find the right slope in the filter. And as long as the quantization error is smaller than the natural variation of delay deltas, the quantization should not impact the accuracy of the median calculation in any noteworthy way. After quantization, you could represent the slopes using integers. For millisecond samples, I guess quantizing to the nearest 1e-3 ~ 1e-6 would be enough. I don't know how large your numerical errors are though? [ I believe that the floating points are not evenly spaced along the number line. I don't know if that fact impacts my arguments here, as I have been thinking in terms of real numbers :) ] https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:63: if (now_ms - old_delay.first != 0) { I guess that if (now_ms - old_delay.first) is close to 0, you will get some unrealistic slope calculations. Would this happen on mobile networks with large buffers and channel-dependent scheduling? If not, it could be an idea to saturate the absolute value of the slopes at some high limit. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/theil_sen_estimator.h (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.h:28: // threshold instead of setting a gain. I.e., the gain would be unity when the old estimator has been removed? https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.h:39: // k < 0 -> the delay decreases, queues are being emptied Why is |k| not lower bounded by -1, when it is upper bounded by 1? https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.h:43: unsigned int num_of_deltas() const { return num_of_deltas_; } size_t?
The CQ bit was checked by terelius@webrtc.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: linux_baremetal on master.tryserver.webrtc (JOB_FAILED, http://build.chromium.org/p/tryserver.webrtc/builders/linux_baremetal/builds/...) mac_baremetal on master.tryserver.webrtc (JOB_FAILED, http://build.chromium.org/p/tryserver.webrtc/builders/mac_baremetal/builds/16799)
https://codereview.webrtc.org/2512693002/diff/40001/webrtc/base/analytics/per... File webrtc/base/analytics/percentile_filter.h (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/base/analytics/per... webrtc/base/analytics/percentile_filter.h:37: // the size of the container. On 2016/11/28 13:01:58, stefan-webrtc (holmer) wrote: > Comment on what this returns Done. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/delay_based_bwe.cc (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/delay_based_bwe.cc:75: bool ReadTrendlineFilterExperimentParameters(size_t* window_points, On 2016/11/28 16:27:19, brandtr wrote: > window_size? Here and in function below. Done. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/delay_based_bwe.h (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/delay_based_bwe.h:86: const bool in_trendline_experiment_; On 2016/11/28 16:27:19, brandtr wrote: > You might want to rename this in the future, as the Theil-Sen experiment also is > kind of a trendline experiment. Same goes for the class name on row 93. Agreed. The variable name made more sense when there was only one estimator that constructed a line through the delay. At this point I prefer to keep it to maintain consistency with the field trial names. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/delay_based_bwe_unittest.cc (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/delay_based_bwe_unittest.cc:239: bitrate_estimator_.reset(new DelayBasedBwe(&clock_)); On 2016/11/28 16:27:19, brandtr wrote: > I think you could move this to the constructor? Done. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/theil_sen_estimator.cc (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:22: enum { kDeltaCounterMax = 1000 }; On 2016/11/28 16:27:19, brandtr wrote: > Can you use a constexpr size_t instead? Done, except using unsigned int. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:47: // First remove the oldest N-1 slopes if the window is full. On 2016/11/28 16:27:19, brandtr wrote: > This could be a computer science thing, but it's not immediately obvious to me > that |N| corresponds to the number of points in the data structure. Would be > nice to point this out, for SP people like me ;) > > Also, consider rephrasing comment as: "remove the N-1 slopes that belong to the > oldest point". The idea being that just because a slope partially belongs to an > old point, doesn't mean that the slope itself is old. E.g., the slope between > the oldest point and the newest point is just as new as the slope between the > second newest point and the newest point. Done. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:49: std::pair<double, double> old_delay = delay_hist_.front(); On 2016/11/28 13:01:58, stefan-webrtc (holmer) wrote: > I think auto would be fine here if you'd prefer that. This part of the code has changed, so the comment no longer applies. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:54: (new_delay.first - old_delay.first); On 2016/11/28 16:27:19, brandtr wrote: > I see the problem here that you were discussing before. > > One possible solution, which would not involve changing the percentile filter > interface, would be to quantize the slopes before inserting them into the > filter. As long as the quantization error is larger than the numerical error in > calculating the division, you should always find the right slope in the filter. > And as long as the quantization error is smaller than the natural variation of > delay deltas, the quantization should not impact the accuracy of the median > calculation in any noteworthy way. After quantization, you could represent the > slopes using integers. > > For millisecond samples, I guess quantizing to the nearest 1e-3 ~ 1e-6 would be > enough. I don't know how large your numerical errors are though? > > [ I believe that the floating points are not evenly spaced along the number > line. I don't know if that fact impacts my arguments here, as I have been > thinking in terms of real numbers :) ] A problem with the quantization approach is that I don't a priori know the interval/distribution of the data, nor the maximum numerical error I can get from fp registers larger than 64 bits. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:55: if (!median_filter_.Erase(slope)) On 2016/11/28 13:01:58, stefan-webrtc (holmer) wrote: > {} Done. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:57: "a bug, likely related to rounding."; On 2016/11/28 13:01:58, stefan-webrtc (holmer) wrote: > Should this happen? Otherwise a DCHECK might make sense? Kept the error message but added an RTC_NOTREACHED(); https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:63: if (now_ms - old_delay.first != 0) { On 2016/11/28 16:27:19, brandtr wrote: > I guess that if (now_ms - old_delay.first) is close to 0, you will get some > unrealistic slope calculations. Would this happen on mobile networks with large > buffers and channel-dependent scheduling? If not, it could be an idea to > saturate the absolute value of the slopes at some high limit. The filter should be robust anyway, so I don't think this warrants special treatment. Also note that clipping some values wont affect the median unless the median itself is outside your limit. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:71: if (delay_hist_.size() == window_size_) { On 2016/11/28 13:01:58, stefan-webrtc (holmer) wrote: > Feel free to remove {} Done. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/theil_sen_estimator.h (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.h:28: // threshold instead of setting a gain. On 2016/11/28 16:27:19, brandtr wrote: > I.e., the gain would be unity when the old estimator has been removed? Yes, but we might want a parameter to set the initial threshold instead. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.h:39: // k < 0 -> the delay decreases, queues are being emptied On 2016/11/28 16:27:20, brandtr wrote: > Why is |k| not lower bounded by -1, when it is upper bounded by 1? It depends on whose clock we are using for the x-axis. Here we are using the receiver's clock, and from the receiver's point of view the delay can't increase faster than 1 second per second. On the other, the receiver might receive packets back-to-back which gives a slope < -1. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.h:43: unsigned int num_of_deltas() const { return num_of_deltas_; } On 2016/11/28 16:27:19, brandtr wrote: > size_t? I agree that size_t would be better, but the result is capped at 1000 so it makes no difference in practice. My reasoning for choosing unsigned int is that I want to preserve the same interface as the Kalman filter.
The CQ bit was checked by terelius@webrtc.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...
lgtm https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/delay_based_bwe.h (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/delay_based_bwe.h:86: const bool in_trendline_experiment_; On 2016/12/02 16:45:52, terelius wrote: > On 2016/11/28 16:27:19, brandtr wrote: > > You might want to rename this in the future, as the Theil-Sen experiment also > is > > kind of a trendline experiment. Same goes for the class name on row 93. > > Agreed. The variable name made more sense when there was only one estimator that > constructed a line through the delay. At this point I prefer to keep it to > maintain consistency with the field trial names. Acknowledged. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/theil_sen_estimator.cc (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:54: (new_delay.first - old_delay.first); On 2016/12/02 16:45:52, terelius wrote: > On 2016/11/28 16:27:19, brandtr wrote: > > I see the problem here that you were discussing before. > > > > One possible solution, which would not involve changing the percentile filter > > interface, would be to quantize the slopes before inserting them into the > > filter. As long as the quantization error is larger than the numerical error > in > > calculating the division, you should always find the right slope in the > filter. > > And as long as the quantization error is smaller than the natural variation of > > delay deltas, the quantization should not impact the accuracy of the median > > calculation in any noteworthy way. After quantization, you could represent the > > slopes using integers. > > > > For millisecond samples, I guess quantizing to the nearest 1e-3 ~ 1e-6 would > be > > enough. I don't know how large your numerical errors are though? > > > > [ I believe that the floating points are not evenly spaced along the number > > line. I don't know if that fact impacts my arguments here, as I have been > > thinking in terms of real numbers :) ] > > A problem with the quantization approach is that I don't a priori know the > interval/distribution of the data, nor the maximum numerical error I can get > from fp registers larger than 64 bits. Right. This comment, as well as the one on line 63, assumes that we will never encounter infinitely dynamic channels; or in other words, that we have a "bandwidth" (in the EE sense) that is bounded. But as you explained offline, this assumption doesn't hold due to how the slopes are defined. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/theil_sen_estimator.h (right): https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.h:28: // threshold instead of setting a gain. On 2016/12/02 16:45:52, terelius wrote: > On 2016/11/28 16:27:19, brandtr wrote: > > I.e., the gain would be unity when the old estimator has been removed? > > Yes, but we might want a parameter to set the initial threshold instead. Right. https://codereview.webrtc.org/2512693002/diff/40001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.h:43: unsigned int num_of_deltas() const { return num_of_deltas_; } On 2016/12/02 16:45:52, terelius wrote: > On 2016/11/28 16:27:19, brandtr wrote: > > size_t? > > I agree that size_t would be better, but the result is capped at 1000 so it > makes no difference in practice. My reasoning for choosing unsigned int is that > I want to preserve the same interface as the Kalman filter. Acknowledged. https://codereview.webrtc.org/2512693002/diff/60001/webrtc/modules/congestion... File webrtc/modules/congestion_controller/theil_sen_estimator.cc (right): https://codereview.webrtc.org/2512693002/diff/60001/webrtc/modules/congestion... webrtc/modules/congestion_controller/theil_sen_estimator.cc:53: "a bug, likely related to rounding."; Remove or update "likely related to rounding."
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
lgtm
The CQ bit was checked by terelius@webrtc.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...
The CQ bit was checked by terelius@webrtc.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...
terelius@webrtc.org changed reviewers: + magjed@webrtc.org, mflodman@webrtc.org
Rasmus, I added some comments as discussed. Could you take another look? Magnus J, could you review changes to the PercentileFilter? Magnus F, I need owner approval for base. Could you take a look?
https://codereview.webrtc.org/2512693002/diff/140001/webrtc/base/analytics/pe... File webrtc/base/analytics/percentile_filter_unittest.cc (right): https://codereview.webrtc.org/2512693002/diff/140001/webrtc/base/analytics/pe... webrtc/base/analytics/percentile_filter_unittest.cc:84: TEST(PercentileFilterTest, ClearContents) { Can you also add a short case for testing return value of Erase(...).
https://codereview.webrtc.org/2512693002/diff/140001/webrtc/base/analytics/pe... File webrtc/base/analytics/percentile_filter_unittest.cc (right): https://codereview.webrtc.org/2512693002/diff/140001/webrtc/base/analytics/pe... webrtc/base/analytics/percentile_filter_unittest.cc:84: TEST(PercentileFilterTest, ClearContents) { On 2016/12/07 16:56:56, mflodman wrote: > Can you also add a short case for testing return value of Erase(...). Added tests for return value in the two existing test cases for Erase.
LGTM for base/ https://codereview.webrtc.org/2512693002/diff/140001/webrtc/base/analytics/pe... File webrtc/base/analytics/percentile_filter_unittest.cc (right): https://codereview.webrtc.org/2512693002/diff/140001/webrtc/base/analytics/pe... webrtc/base/analytics/percentile_filter_unittest.cc:84: TEST(PercentileFilterTest, ClearContents) { On 2016/12/07 17:15:22, terelius wrote: > On 2016/12/07 16:56:56, mflodman wrote: > > Can you also add a short case for testing return value of Erase(...). > > Added tests for return value in the two existing test cases for Erase. Perfect!
still lgtm On 2016/12/07 16:52:56, terelius wrote: > Rasmus, I added some comments as discussed. Could you take another look? Good comments!
https://codereview.webrtc.org/2512693002/diff/160001/webrtc/base/analytics/pe... File webrtc/base/analytics/percentile_filter_unittest.cc (right): https://codereview.webrtc.org/2512693002/diff/160001/webrtc/base/analytics/pe... webrtc/base/analytics/percentile_filter_unittest.cc:109: EXPECT_EQ(true, success); EXPECT_TRUE https://codereview.webrtc.org/2512693002/diff/160001/webrtc/base/analytics/pe... webrtc/base/analytics/percentile_filter_unittest.cc:115: EXPECT_EQ(false, success); EXPECT_FALSE https://codereview.webrtc.org/2512693002/diff/160001/webrtc/base/analytics/pe... webrtc/base/analytics/percentile_filter_unittest.cc:119: EXPECT_EQ(false, success); EXPECT_FALSE https://codereview.webrtc.org/2512693002/diff/160001/webrtc/modules/congestio... File webrtc/modules/congestion_controller/median_slope_estimator.cc (right): https://codereview.webrtc.org/2512693002/diff/160001/webrtc/modules/congestio... webrtc/modules/congestion_controller/median_slope_estimator.cc:60: // We're erasing previously inserted elements from a multiset, which Since you don't recompute the values, I don't see why you need this. I would just simplify the logic and do: const bool success = median_filter_.Erase(slope); RTC_CHECK(success);
The CQ bit was checked by terelius@webrtc.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...
https://codereview.webrtc.org/2512693002/diff/160001/webrtc/base/analytics/pe... File webrtc/base/analytics/percentile_filter_unittest.cc (right): https://codereview.webrtc.org/2512693002/diff/160001/webrtc/base/analytics/pe... webrtc/base/analytics/percentile_filter_unittest.cc:109: EXPECT_EQ(true, success); On 2016/12/08 09:31:15, magjed_webrtc wrote: > EXPECT_TRUE Done. https://codereview.webrtc.org/2512693002/diff/160001/webrtc/base/analytics/pe... webrtc/base/analytics/percentile_filter_unittest.cc:115: EXPECT_EQ(false, success); On 2016/12/08 09:31:15, magjed_webrtc wrote: > EXPECT_FALSE Done. https://codereview.webrtc.org/2512693002/diff/160001/webrtc/base/analytics/pe... webrtc/base/analytics/percentile_filter_unittest.cc:119: EXPECT_EQ(false, success); On 2016/12/08 09:31:15, magjed_webrtc wrote: > EXPECT_FALSE Done. https://codereview.webrtc.org/2512693002/diff/160001/webrtc/modules/congestio... File webrtc/modules/congestion_controller/median_slope_estimator.cc (right): https://codereview.webrtc.org/2512693002/diff/160001/webrtc/modules/congestio... webrtc/modules/congestion_controller/median_slope_estimator.cc:60: // We're erasing previously inserted elements from a multiset, which On 2016/12/08 09:31:15, magjed_webrtc wrote: > Since you don't recompute the values, I don't see why you need this. I would > just simplify the logic and do: > const bool success = median_filter_.Erase(slope); > RTC_CHECK(success); It is basically a question of whether we prefer to crash or attempt to recover if the unexpected happens. I haven't been able to find the relevant part of the C++ standard, but since I don't expect it to ever happen, I don't have a strong opinion on how it is handled. Changed as you suggested.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
lgtm https://codereview.webrtc.org/2512693002/diff/160001/webrtc/modules/congestio... File webrtc/modules/congestion_controller/median_slope_estimator.cc (right): https://codereview.webrtc.org/2512693002/diff/160001/webrtc/modules/congestio... webrtc/modules/congestion_controller/median_slope_estimator.cc:60: // We're erasing previously inserted elements from a multiset, which On 2016/12/08 10:47:13, terelius wrote: > On 2016/12/08 09:31:15, magjed_webrtc wrote: > > Since you don't recompute the values, I don't see why you need this. I would > > just simplify the logic and do: > > const bool success = median_filter_.Erase(slope); > > RTC_CHECK(success); > > It is basically a question of whether we prefer to crash or attempt to recover > if the unexpected happens. I haven't been able to find the relevant part of the > C++ standard, but since I don't expect it to ever happen, I don't have a strong > opinion on how it is handled. Changed as you suggested. I still don't understand why precision or the C++ standard is relevant as long as you store the values and don't recompute them. The double is just bits in memory and it won't change once calculated. Am I misunderstanding something?
The CQ bit was checked by terelius@webrtc.org
The patchset sent to the CQ was uploaded after l-g-t-m from stefan@webrtc.org, brandtr@webrtc.org, mflodman@webrtc.org, magjed@webrtc.org Link to the patchset: https://codereview.webrtc.org/2512693002/#ps200001 (title: "Remove PercentileFilter::Clear since no longer used.")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...
CQ is committing da patch.
Bot data: {"patchset_id": 200001, "attempt_start_ts": 1481290069906730,
"parent_rev": "69db44a71b137b2e0b3958bded3611c70d4f7ada", "commit_rev":
"9225f5a1e4e60c15db60ca623dfe3578defc917e"}
Message was sent while issue was closed.
Description was changed from ========== Implement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation). Theil and Sen's estimator essentially looks at the line through every pair of points and selects the median slope. This is robust to corruption of up to 29% of the data points. Wire up new estimator to field trial experiment. Add unit and integration tests. Results are promising. BUG=webrtc:6728 ========== to ========== Implement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation). Theil and Sen's estimator essentially looks at the line through every pair of points and selects the median slope. This is robust to corruption of up to 29% of the data points. Wire up new estimator to field trial experiment. Add unit and integration tests. Results are promising. BUG=webrtc:6728 Review-Url: https://codereview.webrtc.org/2512693002 ==========
Message was sent while issue was closed.
Committed patchset #11 (id:200001)
Message was sent while issue was closed.
Description was changed from ========== Implement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation). Theil and Sen's estimator essentially looks at the line through every pair of points and selects the median slope. This is robust to corruption of up to 29% of the data points. Wire up new estimator to field trial experiment. Add unit and integration tests. Results are promising. BUG=webrtc:6728 Review-Url: https://codereview.webrtc.org/2512693002 ========== to ========== Implement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation). Theil and Sen's estimator essentially looks at the line through every pair of points and selects the median slope. This is robust to corruption of up to 29% of the data points. Wire up new estimator to field trial experiment. Add unit and integration tests. Results are promising. BUG=webrtc:6728 Committed: https://crrev.com/5a388368a220cb975cbada5129dd94a104a77497 Cr-Commit-Position: refs/heads/master@{#15508} ==========
Message was sent while issue was closed.
Patchset 11 (id:??) landed as https://crrev.com/5a388368a220cb975cbada5129dd94a104a77497 Cr-Commit-Position: refs/heads/master@{#15508} |
