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..479c93c61d6ffa9f2c18b87a2aa1d5fe001a321d 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
@@ -59,9 +59,12 @@ base::TimeDelta ExpectedQueueingTimeFromTask(base::TimeTicks task_start,
 
 QueueingTimeEstimator::QueueingTimeEstimator(
     QueueingTimeEstimator::Client* client,
-    base::TimeDelta window_duration)
-    : client_(client) {
+    base::TimeDelta window_duration,
+    int steps_per_window)
+    : client_(client), state_(steps_per_window) {
+  DCHECK(steps_per_window >= 1);
   state_.window_duration = window_duration;
+  state_.window_step_width = window_duration / steps_per_window;
 }
 
 QueueingTimeEstimator::QueueingTimeEstimator(const State& state)
@@ -81,6 +84,9 @@ void QueueingTimeEstimator::OnBeginNestedMessageLoop() {
   state_.OnBeginNestedMessageLoop();
 }
 
+QueueingTimeEstimator::State::State(int steps_per_window)
+    : step_queueing_times(steps_per_window) {}
+
 void QueueingTimeEstimator::State::OnTopLevelTaskStarted(
     base::TimeTicks task_start_time) {
   current_task_start_time = task_start_time;
@@ -94,10 +100,10 @@ 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;
-
+    step_queueing_times.ClearBuffer();
+  }
   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 +114,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(
+      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(step_expected_queueing_time);
+    client->OnQueueingTimeForWindowEstimated(step_queueing_times.GetAverage(),
+                                             window_start_time);
+    window_start_time += window_step_width;
+    step_expected_queueing_time = base::TimeDelta();
   }
 
-  current_expected_queueing_time += ExpectedQueueingTimeFromTask(
+  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 +137,35 @@ 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);
+  ClearBuffer();
+}
+
+int QueueingTimeEstimator::RunningAverage::GetStepsPerWindow() {
+  return circular_buffer_.size();
+}
+
+void QueueingTimeEstimator::RunningAverage::ClearBuffer() {
+  for (uint i = 0; i < circular_buffer_.size(); i++) {

[tdresser, 2017/05/11 13:52:44]

uint -> size_t
https://chromium.googlesource.com/chromium/src/+/master/styleguide/c++/c++.md...

If you want to be fancy, you could do:

for (size_t& bin : circular_buffer)
  bin = base::TimeDelta();

I don't think we actually need this method though. Everything but index_ is an
object that will be default constructed, and we'll never need to clear this once
we've gotten started.

I think we can get away with just initializing index_ in the constructor.

[Liquan (Max) Gu, 2017/05/11 15:14:13]

Fixed

Nice. Didn't realize C++ has this feature too, but shouldn't 'size_t' be
'base::TimeDelta'?

for (base::TimeDelta& bin : circular_buffer)
   bin = base::TimeDelta();

[tdresser, 2017/05/11 15:55:10]

Whoops, you're right.

+    circular_buffer_[i] = base::TimeDelta();
+  }
+  index_ = 0;
+  running_sum_ = base::TimeDelta();
+}
+
+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.
@@ -137,7 +173,8 @@ class RecordQueueingTimeClient : public QueueingTimeEstimator::Client {
  public:
   // QueueingTimeEstimator::Client implementation:
   void OnQueueingTimeForWindowEstimated(
-      base::TimeDelta queueing_time) override {
+      base::TimeDelta queueing_time,
+      base::TimeTicks window_start_time) override {
     queueing_time_ = queueing_time;
   }
 
@@ -167,11 +204,26 @@ base::TimeDelta QueueingTimeEstimator::EstimateQueueingTimeIncludingCurrentTask(
   temporary_queueing_time_estimator_state.OnTopLevelTaskCompleted(
       &record_queueing_time_client, now);
 
-  // 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);
+  // Report the max of the queueing time for the last window, or the on-going
+  // window (tmp window in chart) which includes the current task.
+  //
+  //                                Estimate
+  //                                  |
+  //                                  v
+  // Actual Task     |-------------------------...
+  // Assumed Task    |----------------|
+  // Time       |---o---o---o---o---o---o-------->
+  //            0   1   2   3   4   5   6
+  //            | s | s | s | s | s | s |
+  //            |----last window----|
+  //                |----tmp window-----|
+  RunningAverage& temporary_step_queueing_times =
+      temporary_queueing_time_estimator_state.step_queueing_times;
+  temporary_step_queueing_times.Add(
+      temporary_queueing_time_estimator_state.step_expected_queueing_time);
+
+  return std::max(record_queueing_time_client.queueing_time(),
+                  temporary_step_queueing_times.GetAverage());
 }
 
 }  // namespace scheduler