EQT: Change Expected Queuing Time from per-second to sliding window

third_party/WebKit/Source/platform/scheduler/base/queueing_time_estimator.cc

Index: third_party/WebKit/Source/platform/scheduler/base/queueing_time_estimator.cc
diff --git a/third_party/WebKit/Source/platform/scheduler/base/queueing_time_estimator.cc b/third_party/WebKit/Source/platform/scheduler/base/queueing_time_estimator.cc
index 4ec835b55cf85d874b5db7d07b76c75c70d3c207..bc5731401691d6eb2e5916feb14670574a8863b0 100644
--- a/third_party/WebKit/Source/platform/scheduler/base/queueing_time_estimator.cc
+++ b/third_party/WebKit/Source/platform/scheduler/base/queueing_time_estimator.cc
@@ -57,11 +57,17 @@ base::TimeDelta ExpectedQueueingTimeFromTask(base::TimeTicks task_start,
 
 }  // namespace
 
+// |window_duration| is the size of the sliding window. |window_duration_step_ratio| is the ratio of |window_duration|
+// to the sliding window's step width. This ratio is used for deciding the sliding
+// window's step width, and the number of bins of the circular buffer.

[tdresser, 2017/05/08 17:58:14]

Wrap to 80 cols.

[Liquan (Max) Gu, 2017/05/10 15:08:26]

Done.

 QueueingTimeEstimator::QueueingTimeEstimator(
     QueueingTimeEstimator::Client* client,
-    base::TimeDelta window_duration)
-    : client_(client) {
+    base::TimeDelta window_duration,
+    int window_duration_step_ratio)
+    : client_(client), state_(window_duration_step_ratio) {
+  DCHECK(window_duration_step_ratio >= 1);
   state_.window_duration = window_duration;
+  state_.window_step_width = window_duration / window_duration_step_ratio;

[tdresser, 2017/05/08 17:58:14]

Getting rid of this (as you proposed) sounds good to me.

[Liquan (Max) Gu, 2017/05/10 15:08:26]

It's weird that it always fails once I substitute "window_step_width" with
"(window_duration / steps_per_window)" or "(base::TimeDelta)(window_duration /
steps_per_window)" or a temporary variable of base::TimeDelta type, so I just
keep using window_step_width here.

[tdresser, 2017/05/10 18:54:31]

That's suspicious. I'd consider it worth taking a couple minutes to try to
figure out why.

 }
 
 QueueingTimeEstimator::QueueingTimeEstimator(const State& state)
@@ -81,6 +87,8 @@ void QueueingTimeEstimator::OnBeginNestedMessageLoop() {
   state_.OnBeginNestedMessageLoop();
 }
 
+QueueingTimeEstimator::State::State(int size): step_queueing_times(size){}
+
 void QueueingTimeEstimator::State::OnTopLevelTaskStarted(
     base::TimeTicks task_start_time) {
   current_task_start_time = task_start_time;
@@ -94,10 +102,17 @@ void QueueingTimeEstimator::State::OnTopLevelTaskCompleted(
     current_task_start_time = base::TimeTicks();
     return;
   }
-
-  if (window_start_time.is_null())
+  if (window_start_time.is_null()) {
     window_start_time = current_task_start_time;
-
+    for (int i = 0; i < step_queueing_times.GetSize() - 1; i++) {

[tdresser, 2017/05/08 17:58:14]

Nittiest nit:
For partially historical reasons around the cost of incrementing iterators
(http://stackoverflow.com/questions/1303899/performance-difference-between-ite...),
we always preincrement iterators. 

i++ -> ++i

[Liquan (Max) Gu, 2017/05/10 15:08:26]

Done.

+      slide_step_expected_queueing_time += ExpectedQueueingTimeFromTask(
+          current_task_start_time, task_end_time, window_start_time,
+          window_start_time + window_step_width);
+      step_queueing_times.Add(slide_step_expected_queueing_time);
+      window_start_time += window_step_width;
+      slide_step_expected_queueing_time = base::TimeDelta();
+    }

[tdresser, 2017/05/08 17:58:14]

I'm having a hard time following what's happening here.

It looks like this can only process one task per step? and
current_task_start_time isn't getting update here, so doesn't this add a the
same task a bunch of times?

[Liquan (Max) Gu, 2017/05/10 15:08:26]

Sorry this is a bug. The intent was to fill up all the bins at the beginning
stage.

+  }
   if (task_end_time - current_task_start_time > kInvalidTaskThreshold) {
     // This task took too long, so we'll pretend it never happened. This could
     // be because the user's machine went to sleep during a task.
@@ -108,18 +123,20 @@ void QueueingTimeEstimator::State::OnTopLevelTaskCompleted(
   while (TimePastWindowEnd(task_end_time)) {
     if (!TimePastWindowEnd(current_task_start_time)) {
       // Include the current task in this window.
-      current_expected_queueing_time += ExpectedQueueingTimeFromTask(
+      slide_step_expected_queueing_time += ExpectedQueueingTimeFromTask(
           current_task_start_time, task_end_time, window_start_time,
-          window_start_time + window_duration);
+          window_start_time + window_step_width);
     }
-    client->OnQueueingTimeForWindowEstimated(current_expected_queueing_time);
-    window_start_time += window_duration;
-    current_expected_queueing_time = base::TimeDelta();
+    step_queueing_times.Add(slide_step_expected_queueing_time);
+    client->OnQueueingTimeForWindowEstimated(
+        step_queueing_times.GetAverage());
+    window_start_time += window_step_width;
+    slide_step_expected_queueing_time = base::TimeDelta();
   }
 
-  current_expected_queueing_time += ExpectedQueueingTimeFromTask(
+  slide_step_expected_queueing_time += ExpectedQueueingTimeFromTask(
       current_task_start_time, task_end_time, window_start_time,
-      window_start_time + window_duration);
+      window_start_time + window_step_width);
 
   current_task_start_time = base::TimeTicks();
 }
@@ -129,7 +146,29 @@ void QueueingTimeEstimator::State::OnBeginNestedMessageLoop() {
 }
 
 bool QueueingTimeEstimator::State::TimePastWindowEnd(base::TimeTicks time) {
-  return time > window_start_time + window_duration;
+  return time > window_start_time + window_step_width;
+}
+
+QueueingTimeEstimator::RunningAverage::RunningAverage(int size) {
+  circular_buffer_.resize(size);
+  index_ = 0;
+  running_sum_ = base::TimeDelta();
+}
+
+int QueueingTimeEstimator::RunningAverage::GetSize() {
+  return circular_buffer_.size();
+}
+
+void QueueingTimeEstimator::RunningAverage::Add(
+    base::TimeDelta bin_value) {
+  running_sum_ -= circular_buffer_[index_];
+  circular_buffer_[index_] = bin_value;
+  running_sum_ += bin_value;
+  index_ = (index_ + 1) % circular_buffer_.size();
+}
+
+base::TimeDelta QueueingTimeEstimator::RunningAverage::GetAverage() {
+  return running_sum_ / circular_buffer_.size();
 }
 
 // Keeps track of the queueing time.
@@ -169,9 +208,9 @@ base::TimeDelta QueueingTimeEstimator::EstimateQueueingTimeIncludingCurrentTask(
 
   // Report the max of the queueing time for the last full window, or the
   // current partial window.
-  return std::max(
-      record_queueing_time_client.queueing_time(),
-      temporary_queueing_time_estimator_state.current_expected_queueing_time);
+  return std::max(record_queueing_time_client.queueing_time(),
+                  temporary_queueing_time_estimator_state
+                      .slide_step_expected_queueing_time);
 }
 
 }  // namespace scheduler