TaskScheduler [9] Delayed Task Manager

base/task_scheduler/delayed_task_manager.cc

Index: base/task_scheduler/delayed_task_manager.cc
diff --git a/base/task_scheduler/delayed_task_manager.cc b/base/task_scheduler/delayed_task_manager.cc
new file mode 100644
index 0000000000000000000000000000000000000000..9dd34c3527705c7eab50451427b15d21efda581d
--- /dev/null
+++ b/base/task_scheduler/delayed_task_manager.cc
@@ -0,0 +1,144 @@
+// 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 "base/task_scheduler/delayed_task_manager.h"
+
+#include <utility>
+#include <vector>
+
+#include "base/logging.h"
+
+namespace base {
+namespace internal {
+
+struct DelayedTaskManager::DelayedTask {
+  DelayedTask() = default;
+  DelayedTask(std::unique_ptr<Task> task,
+              const PostTaskCallback& post_task_callback,
+              size_t index);
+  DelayedTask(DelayedTask&& other);
+  DelayedTask& operator=(DelayedTask&& other);

[gab, 2016/04/07 21:32:08]

Should we explicitly delete the copy constructors? Are they needed for the STL?
If they are how do they cope with the unique_ptr?

[danakj, 2016/04/07 21:39:29]

They are not. You can DISALLOW_COPY_AND_ASSIGN and add move
constructor/operator. These will work fine in STL containers.

[fdoray, 2016/04/08 17:24:51]

Done.

+
+  ~DelayedTask() = default;

[gab, 2016/04/07 21:32:08]

Can't inline destructor when class has non-POD types.

[fdoray, 2016/04/08 17:24:51]

Done. But does it matter given that we are in the .cc file?

[gab, 2016/04/08 18:03:55]

Ah true, I guess it matters less, it basically makes inlining possible at the
destruction sites in the .cc file which is probably okay. I've definitely often
favored inlining the entire definition of classes declared in the .cc file for
simplicity. But here you already had methods not inline so it felt right to also
not inline that one (i.e. either inline everything when reasonable or follow
default header/impl split style).

+
+  std::unique_ptr<Task> task;
+  PostTaskCallback post_task_callback;
+
+  // Ensures that tasks that have the same |delayed_run_time| are sorted
+  // according to the order in which they were created.
+  size_t index;
+};

[gab, 2016/04/07 21:32:08]

I'd expect the definitions of DelayedTaskManager::DelayedTask's methods to
follow right after this (which I guess is out of order with the header, is it
here to make the templates compile? feels out of place..)

[fdoray, 2016/04/08 17:24:51]

DelayedTaskManager::DelayedTask's definition needs to be before any use of
|delayed_tasks_|. Can I keep the method's definition at the bottom of the file
to stay in the same order as the header?

[gab, 2016/04/08 18:03:55]

Maybe it's fine to just define the entire class inline at the top then?

IMO keeping a component together takes precedence over following order of the
header.

[fdoray, 2016/04/11 13:30:54]

Done. Defined the entire class inline at the top.

+
+DelayedTaskManager::DelayedTaskManager(const Closure& delayed_run_time_changed)
+    : delayed_run_time_changed_(delayed_run_time_changed) {
+  DCHECK(!delayed_run_time_changed_.is_null());
+}
+
+DelayedTaskManager::~DelayedTaskManager() = default;
+
+void DelayedTaskManager::AddDelayedTask(
+    std::unique_ptr<Task> task,
+    const PostTaskCallback& post_task_callback) {
+  DCHECK(task);
+  DCHECK(!post_task_callback.is_null());
+
+  const TimeTicks new_task_delayed_run_time = task->delayed_run_time;
+  TimeTicks previous_delayed_run_time;
+
+  {
+    AutoSchedulerLock auto_lock(lock_);
+
+    if (!delayed_tasks_.empty())
+      previous_delayed_run_time = delayed_tasks_.top().task->delayed_run_time;
+
+    delayed_tasks_.emplace(std::move(task), post_task_callback,
+                           next_delayed_task_index_++);
+  }
+
+  if (previous_delayed_run_time.is_null() ||
+      new_task_delayed_run_time < previous_delayed_run_time) {
+    delayed_run_time_changed_.Run();
+  }
+}
+
+void DelayedTaskManager::PostReadyTasks() {
+  const TimeTicks now = Now();
+
+  // Move delayed tasks that are ready for execution into |ready_tasks|. Don't
+  // post them right away to avoid imposing an unecessary lock dependency on
+  // callbacks.
+  std::vector<DelayedTask> ready_tasks;
+
+  {
+    AutoSchedulerLock auto_lock(lock_);
+    while (!delayed_tasks_.empty() &&
+           delayed_tasks_.top().task->delayed_run_time <= now) {
+      // The const_cast for std::move is almost okay since we're immediately
+      // moving it to |ready_tasks|. See DelayedTaskComparator::operator() for
+      // why it's almost.
+      ready_tasks.emplace_back(
+          std::move(const_cast<DelayedTask&>(delayed_tasks_.top())));
+      delayed_tasks_.pop();
+    }
+  }
+
+  // Post delayed tasks that are ready for execution.
+  for (auto& delayed_task : ready_tasks)
+    delayed_task.post_task_callback.Run(std::move(delayed_task.task));
+}
+
+TimeTicks DelayedTaskManager::GetNextDelayedRunTime() const {
+  AutoSchedulerLock auto_lock(lock_);
+
+  if (delayed_tasks_.empty())
+    return TimeTicks();
+
+  return delayed_tasks_.top().task->delayed_run_time;
+}
+
+DelayedTaskManager::DelayedTask::DelayedTask(
+    std::unique_ptr<Task> task,
+    const PostTaskCallback& post_task_callback,
+    size_t index)
+    : task(std::move(task)),
+      post_task_callback(post_task_callback),
+      index(index) {}
+
+DelayedTaskManager::DelayedTask::DelayedTask(DelayedTask&& other)
+    : task(std::move(other.task)),
+      post_task_callback(other.post_task_callback),
+      index(other.index) {}
+
+DelayedTaskManager::DelayedTask& DelayedTaskManager::DelayedTask::operator=(
+    DelayedTask&& other) {
+  task = std::move(other.task);
+  post_task_callback = other.post_task_callback;
+  index = other.index;
+  return *this;
+}
+
+bool DelayedTaskManager::DelayedTaskComparator::operator()(

[gab, 2016/04/07 21:32:08]

Add a comment explaining what this does in the context of std::priority_queue
(i.e. that std::priority_queue bubbles the "largest" element on top and expects
the comparator to behave like std::less(left, right)).

[fdoray, 2016/04/08 17:24:51]

Done.

+    const DelayedTask& left,
+    const DelayedTask& right) const {
+  // Due to STL consistency checks in Windows and const_cast'ing right before
+  // popping the DelayedTask, we might actually have null tasks.

[gab, 2016/04/07 21:32:08]

s/we might actually have null tasks/null tasks can be passed to this comparator
in Debug builds/

+  // To keep the order of the data structure the same, we consider null tasks

[gab, 2016/04/07 21:32:08]

s/To keep the order of the data structure the same/To satisfy these consistency
checks/

[fdoray, 2016/04/08 17:24:51]

Done.

+  // to be the smallest possible |delayed_run_time|.

[gab, 2016/04/07 21:32:08]

"smallest possible |delayed_run_time|" is confusing because that actually means
"largest".

How about: s/we consider null tasks to be the smallest possible
|delayed_run_time|/this comparator considers null tasks to be the larger than
anything/.

[fdoray, 2016/04/08 17:24:51]

Done.

+  if (!left.task)

[gab, 2016/04/07 21:32:08]

Add:
// Since null tasks is a special case of the const_cast+move on pop, no two
tasks should ever be null at the same time.
DCHECK(left.task || right.task);
?

[fdoray, 2016/04/08 17:24:51]

Done.

+    return false;
+  if (!right.task)
+    return true;

[gab, 2016/04/07 21:32:08]

Would it make sense to:

#ifndef NDEBUG
  DCHECK(left.task || right.task);
  if (!left.task)
    return false;
  if (!right.task)
    return true;
#else
  DCHECK(left.task && right.task);
#endif

(+comments obviously)

?

[fdoray, 2016/04/08 17:24:51]

Done.

+  if (left.task->delayed_run_time > right.task->delayed_run_time)
+    return true;
+  if (left.task->delayed_run_time < right.task->delayed_run_time)
+    return false;
+  return left.index > right.index;
+}
+
+TimeTicks DelayedTaskManager::Now() const {
+  return TimeTicks::Now();
+}
+
+}  // namespace internal
+}  // namespace base