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

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

Index: third_party/WebKit/Source/platform/scheduler/base/queueing_time_estimator.h
diff --git a/third_party/WebKit/Source/platform/scheduler/base/queueing_time_estimator.h b/third_party/WebKit/Source/platform/scheduler/base/queueing_time_estimator.h
index 4bdd47519f24d08654b5cddf229fe1b5fefe2b35..df6a9303da9367f082a23cf2154c5e0ddda938c3 100644
--- a/third_party/WebKit/Source/platform/scheduler/base/queueing_time_estimator.h
+++ b/third_party/WebKit/Source/platform/scheduler/base/queueing_time_estimator.h
@@ -9,11 +9,13 @@
 #include "base/time/time.h"
 #include "platform/PlatformExport.h"
 
+#include <vector>
+
 namespace blink {
 namespace scheduler {
 
 // Records the expected queueing time for a high priority task occurring
-// randomly during each interval of length |window_duration|.
+// randomly during each interval of length |window_duration|

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

readd trailing .

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

Done.

 class PLATFORM_EXPORT QueueingTimeEstimator {
  public:
   class PLATFORM_EXPORT Client {
@@ -27,23 +29,66 @@ class PLATFORM_EXPORT QueueingTimeEstimator {
     DISALLOW_COPY_AND_ASSIGN(Client);
   };
 
+  class RunningAverage {
+   public:
+    RunningAverage(int size);
+    int GetSize();
+    void Add(base::TimeDelta bin_value);
+    base::TimeDelta GetAverage();
+
+   private:
+    int index_;
+    std::vector<base::TimeDelta> circular_buffer_;
+    base::TimeDelta running_sum_;
+  };
+
   class State {
    public:
+    State(int size);

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

Let's name this steps_per_window as well.

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

This is more clear, thanks!

     void OnTopLevelTaskStarted(base::TimeTicks task_start_time);
     void OnTopLevelTaskCompleted(Client* client, base::TimeTicks task_end_time);
     void OnBeginNestedMessageLoop();
 
-    base::TimeDelta current_expected_queueing_time;
+    // |slide_step_expected_queueing_time| is the expected queuing time of a smaller window of a step's width.
+    // By combining these step EQTs though running average, we can get window EQTs of a bigger window.

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

This looks longer than our 80 column limit. I would have thought our presubmit
hooks would catch this. Please wrap to 80 columns.

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

I've just installed the Clang-formatter that could help me with that, but it's
not triggered on-save but manually. Not sure why presumit hooks doesn't work
here though.

+    //
+    // ^ Instantaneous queuing time
+    // |
+    // |
+    // |   |\
+    // |   | \            |\             |\
+    // |   |  \           | \       |\   | \
+    // |   |   \    |\    |  \      | \  |  \
+    // |   |    \   | \   |   \     |  \ |   \
+    // ------------------------------------------------> Time
+    //
+    // |stepEQT|stepEQT|stepEQT|stepEQT|stepEQT|stepEQT|
+    //
+    // |------windowEQT_1------|
+    //         |------windowEQT_2------|
+    //                 |------windowEQT_3------|

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

Great diagram!

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

Acknowledged.

+    //
+    // In this case:
+    // |window_duration_step_ratio| = 3 because each window is in 3 steps' size.

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

Wording nit:

"3 because each window is in 3 steps' size." ->
"3, because each window is the length of 3 steps."

or something like that.

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

Done.

+
+    base::TimeDelta slide_step_expected_queueing_time;

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

I'd just call this "step_expected_queueing_time" or maybe
"current_step_expected_queueing_time".

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

I think "step_expected_queueing_time" would be enough, since the class State has
indicated it's a temporary state so I guess readers wouldn't confuse.

     base::TimeDelta window_duration;
+    // |window_duration_step_ratio| is the ratio of |window_duration|
+    // to the sliding window's step width.
+    base::TimeDelta window_step_width;
+    int window_duration_step_ratio;

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

Let's call this "steps_per_window". It makes it clearer which way the ratio is.
The way it is currently, it isn't clear whether this is steps per window, or
windows per step.

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

Done.

     base::TimeTicks window_start_time;
     base::TimeTicks current_task_start_time;
+    RunningAverage step_queueing_times;
 
    private:
     bool TimePastWindowEnd(base::TimeTicks task_end_time);
     bool in_nested_message_loop_ = false;
   };
 
-  QueueingTimeEstimator(Client* client, base::TimeDelta window_duration);
+  QueueingTimeEstimator(Client* client,
+                        base::TimeDelta window_duration,
+                        int window_duration_step_ratio);
   explicit QueueingTimeEstimator(const State& state);
 
   void OnTopLevelTaskStarted(base::TimeTicks task_start_time);