Report expected task queueing time via UMA

components/scheduler/base/queueing_time_estimator.cc

Index: components/scheduler/base/queueing_time_estimator.cc
diff --git a/components/scheduler/base/queueing_time_estimator.cc b/components/scheduler/base/queueing_time_estimator.cc
new file mode 100644
index 0000000000000000000000000000000000000000..86c2b1cdcf5873b554cbad1dfe3fe08ca20d4498
--- /dev/null
+++ b/components/scheduler/base/queueing_time_estimator.cc
@@ -0,0 +1,82 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "components/scheduler/base/queueing_time_estimator.h"
+
+#include "base/time/default_tick_clock.h"
+
+namespace scheduler {
+
+namespace {
+
+base::TimeDelta ExpectedQueueingTimeFromTask(base::TimeTicks task_start,

[alex clarke (OOO till 29th), 2016/07/05 13:47:45]

Please add a comment explaining the maths behind how the estimator works.

[tdresser, 2016/07/05 14:30:13]

Done.

+                                             base::TimeTicks task_end,
+                                             base::TimeTicks window_start,
+                                             base::TimeTicks window_end) {
+  DCHECK(task_start <= task_end);
+  DCHECK(task_start <= window_end);
+  DCHECK(window_start < window_end);
+  DCHECK(task_end >= window_start);
+  base::TimeTicks task_in_window_start_time =
+      std::max(task_start, window_start);
+  base::TimeTicks task_in_window_end_time =
+      std::min(task_end, window_end);
+  DCHECK(task_in_window_end_time <= task_in_window_end_time);
+
+  double probability_of_this_task =
+      static_cast<double>((task_in_window_end_time - task_in_window_start_time)
+                              .InMicroseconds()) /
+      (window_end - window_start).InMicroseconds();
+
+  base::TimeDelta expected_queueing_duration_within_task =
+      ((task_end - task_in_window_start_time) +
+       (task_end - task_in_window_end_time)) /
+      2;
+
+  return base::TimeDelta::FromMillisecondsD(
+      probability_of_this_task *
+      expected_queueing_duration_within_task.InMillisecondsF());
+}
+
+}  // namespace
+
+QueueingTimeEstimator::QueueingTimeEstimator(
+    QueueingTimeEstimator::Client* client,
+    base::TimeDelta window_duration)
+    : client_(client),
+      window_duration_(window_duration),
+      window_start_time_() {}
+
+void QueueingTimeEstimator::OnToplevelTaskCompleted(
+    base::TimeTicks task_start_time,
+    base::TimeTicks task_end_time) {
+  if (window_start_time_.is_null())
+    window_start_time_ = task_start_time;
+
+  bool start_past_window =
+      task_start_time > window_start_time_ + window_duration_;
+  bool end_past_window = task_end_time > window_start_time_ + window_duration_;

[alex clarke (OOO till 29th), 2016/07/05 13:47:45]

Maybe make end_past_window a private helper function and move start_past_window
into the loop since it's only used there.

[tdresser, 2016/07/05 14:30:13]

Used helper method for both.

+
+  while (end_past_window) {

[alex clarke (OOO till 29th), 2016/07/05 13:47:45]

I hope this is unlikely (given |window_duration_| looks like it's 1s based on
components/scheduler/base/task_time_tracker.cc) but what if it ended up being
far past the window?  Can we make this O(1)? 

[tdresser, 2016/07/05 14:30:13]

We can't make this O(1), because we want to report the expected queueing time
via UMA for every window, even if it's empty. We might be able to amortize this
if we were so inclined, but this should be cheap enough that it isn't an issue.

The easy fix here would be to not report empty windows, and just accept that we
won't get data for empty windows. This might be fairly reasonable, though it
would make the data a bit harder to interpret.

I'm much more worried about the case where there's a massive gap between main
thread tasks than I am about the case where there's a massively long main thread
task.

+    if (!start_past_window) {
+      // Include the current task in this window.
+      current_expected_queueing_time_ += ExpectedQueueingTimeFromTask(
+          task_start_time, task_end_time, window_start_time_,
+          window_start_time_ + window_duration_);
+    }
+    client_->OnQueueingTimeForWindowEstimated(current_expected_queueing_time_);
+    window_start_time_ += window_duration_;
+    current_expected_queueing_time_ = base::TimeDelta();

[alex clarke (OOO till 29th), 2016/07/05 13:47:45]

Seems like we're loosing data here. Does this cause significant discontinuities
in the estimated queuing time?

[tdresser, 2016/07/05 14:30:13]

Sorry, what data are we losing? We just reported on the current window, so the
known queueing time for the next window is 0.

+
+    start_past_window =
+        task_start_time > window_start_time_ + window_duration_;
+    end_past_window = task_end_time > window_start_time_ + window_duration_;
+  }
+
+  current_expected_queueing_time_ += ExpectedQueueingTimeFromTask(
+      task_start_time, task_end_time, window_start_time_,
+      window_start_time_ + window_duration_);
+}
+
+}  // namespace scheduler