Experimental: Chrome side of killing the blink timer heap

content/renderer/scheduler/task_queue_manager.cc

 // Copyright 2014 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 "content/renderer/scheduler/task_queue_manager.h"
 
 #include <queue>
+#include <set>
 
 #include "base/bind.h"
 #include "base/trace_event/trace_event.h"
 #include "base/trace_event/trace_event_argument.h"
 #include "cc/test/test_now_source.h"
 #include "content/renderer/scheduler/task_queue_selector.h"
 
 namespace {
 const int64_t kMaxTimeTicks = std::numeric_limits<int64>::max();
 }
@@ skipping 42 matching lines @@
     NON_NESTABLE,
   };
 
   ~TaskQueue() override;
 
   bool PostDelayedTaskImpl(const tracked_objects::Location& from_here,
                            const base::Closure& task,
                            base::TimeDelta delay,
                            TaskType task_type);
 
+  // Delayed task posted to the chromium run loop, which calls
+  // ScheduleDelayedWorkLocked to enqueue any delayed timers which should be run
+  // now.
+  void KickDelayedTasks();
+
+  // Enqueues any delayed timers which should be run now, and (maybe) posts
+  // KickDelayedTasks if there isn't already a timer posted on the chromium
+  // runloop for the next task's scheduled run time.
+  bool ScheduleDelayedWorkLocked(base::TimeTicks now);
+
   // Adds a task at the end of the incoming task queue and schedules a call to
   // TaskQueueManager::DoWork() if the incoming queue was empty and automatic
   // pumping is enabled. Can be called on an arbitrary thread.
   void EnqueueTask(const base::PendingTask& pending_task);
 
   void PumpQueueLocked();
   bool ShouldAutoPumpQueueLocked(
       TaskQueueManager::WorkQueueUpdateEventType event_type);
   void EnqueueTaskLocked(const base::PendingTask& pending_task);
 
   void TraceQueueSize(bool is_locked) const;
   static const char* PumpPolicyToString(
       TaskQueueManager::PumpPolicy pump_policy);
   static void QueueAsValueInto(const base::TaskQueue& queue,
                                base::trace_event::TracedValue* state);
   static void TaskAsValueInto(const base::PendingTask& task,
                               base::trace_event::TracedValue* state);
 
   // This lock protects all members except the work queue.
   mutable base::Lock lock_;
   TaskQueueManager* task_queue_manager_;
   base::TaskQueue incoming_queue_;
   TaskQueueManager::PumpPolicy pump_policy_;
   const char* name_;
-  std::priority_queue<base::TimeTicks,
-                      std::vector<base::TimeTicks>,
-                      std::greater<base::TimeTicks>> delayed_task_run_times_;
+  base::DelayedTaskQueue delayed_task_queue_;
+  std::set<base::TimeTicks> in_flight_kick_delayed_tasks_;
 
   base::TaskQueue work_queue_;
 
   DISALLOW_COPY_AND_ASSIGN(TaskQueue);
 };
 
 TaskQueue::TaskQueue(TaskQueueManager* task_queue_manager)
     : task_queue_manager_(task_queue_manager),
       pump_policy_(TaskQueueManager::PumpPolicy::AUTO),
       name_(nullptr) {
 }
 
 TaskQueue::~TaskQueue() {
 }
 
 void TaskQueue::WillDeleteTaskQueueManager() {
   base::AutoLock lock(lock_);
   task_queue_manager_ = nullptr;
+
+  // Clear all delayed tasks because we need them to be deleted before the blink
+  // heap goes away.
+  while (!delayed_task_queue_.empty())

[Sami, 2015/02/27 18:22:33]

Is there a clear() or reset() that does this in one go?

[alex clarke (OOO till 29th), 2015/03/03 10:11:15]

Irritatingly no :(  

http://en.cppreference.com/w/cpp/container/priority_queue

[rmcilroy, 2015/03/03 10:22:21]

One option would be to just make it a scoped_ptr<base::DelayedTaskQueue> and
reset the scoped_ptr - not sure it's worth the bother in this case though?

+    delayed_task_queue_.pop();
 }
 
 bool TaskQueue::RunsTasksOnCurrentThread() const {
   base::AutoLock lock(lock_);
   if (!task_queue_manager_)
     return false;
   return task_queue_manager_->RunsTasksOnCurrentThread();
 }
 
 bool TaskQueue::PostDelayedTaskImpl(const tracked_objects::Location& from_here,
                                     const base::Closure& task,
                                     base::TimeDelta delay,
                                     TaskType task_type) {
   base::AutoLock lock(lock_);
   if (!task_queue_manager_)
     return false;
 
   base::PendingTask pending_task(from_here, task, base::TimeTicks(),
                                  task_type != TaskType::NON_NESTABLE);
   task_queue_manager_->DidQueueTask(&pending_task);
 
   if (delay > base::TimeDelta()) {
-    pending_task.delayed_run_time = task_queue_manager_->Now() + delay;
-    delayed_task_run_times_.push(pending_task.delayed_run_time);
-    return task_queue_manager_->PostDelayedTask(
-        FROM_HERE, Bind(&TaskQueue::EnqueueTask, this, pending_task), delay);
+    base::TimeTicks now = task_queue_manager_->Now();
+    pending_task.delayed_run_time = now + delay;
+    delayed_task_queue_.push(pending_task);
+    // If we changed the topmost task, then it is time to reschedule.
+    if (delayed_task_queue_.top().task.Equals(pending_task.task))
+      return ScheduleDelayedWorkLocked(now);
+    return true;

[rmcilroy, 2015/03/02 13:53:57]

drive-by comment: I'm wondering if it be simpler just to simply post a wrapper
task which does the following:

void TaskQueue::EnqueueNextPendingTask() {
  base::AutoLock lock(lock_);
  if (!task_queue_manager_)
    return;

  if (delayed_task_queue_.empty())
    return;

  EnqueueTaskLocked(delayed_task_queue_.pop());
}

And simply always post this for delayed task. This would be much more similar to
the previous approach except the wrapper task now doesn't point to the task
itself, allowing us to delete the pending taskson shutdown.  While I like the
idea of trying to merge multiple pending tasks into a single pending task
wrapper on the message loop, I'm not sure there will be enough pending tasks
with exactly the same delayed_runtime to justify the extra complexity (but I
don't know the DOMTimer code well so I may be wrong here).  WDYT?

[alex clarke (OOO till 29th), 2015/03/02 16:08:10]

That's a really interesting idea.  I quite like the simplicity of it but on the
other hand (based on the verge and some other popular heavy sites such as
sports.yahoo.com and latimes):

1. While the page loads it's not uncommon to have several hundred delayed tasks
in flight
2. It's quite common for 10+ of these delays to "expire" simultaneously (I've
seen a couple of times when it reached 20+)
3. Typically we'd only have single digit number of KickDelayedTasks's posted on
the chromium run loop.

This suggests that the more complicated approach taken by this patch has some
merit.

[Sami, 2015/03/02 16:38:33]

As one more data point, this comment here suggests that having lots of delayed
tasks that expire simultaneously is a thing that happens:

https://code.google.com/p/chromium/codesearch#chromium/src/base/message_loop/...

[rmcilroy, 2015/03/03 10:22:21]

As discussed offline, the message_loop goes to a fair amount of work to keep
task posting low-overhead when a lot of work is posted together.  I'm not
against doing the more complex approach here but would prefer if we could
justify that it actually makes a performance difference compared to the simple
approach using the optimizations in the message loop before adding the
complexity.

[alex clarke (OOO till 29th), 2015/03/03 16:40:26]

Circling back on this.  I tried it:  https://codereview.chromium.org/972473004

Based on some (admittedly rather contrived) micro benchmarks it seems that there
is a ~30% performance overhead with Ross's approach.

   }
   EnqueueTaskLocked(pending_task);
   return true;
 }
 
+bool TaskQueue::ScheduleDelayedWorkLocked(base::TimeTicks now) {
+  lock_.AssertAcquired();
+
+  // Enqueue all delayed tasks that should be running now.

[Sami, 2015/03/02 16:38:33]

base::MessageLoop always interleaves delayed and non-delayed work, whereas here
we're adding all expired delayed tasks as a monolithic block (which we can still
schedule of course). I wonder if that might have some bad consequences though by
starving other things on the default queue?

Of course if we are moving those tasks off of the default task runner, then
we're kind of relying the scheduler to handle the interleaving for us. Maybe
overall that is the better way to do things anyway.

[alex clarke (OOO till 29th), 2015/03/03 16:40:26]

I think that adding a TimerQueue should help a lot here, since the interleaving
should occur naturally.

+  while (!delayed_task_queue_.empty() &&
+         delayed_task_queue_.top().delayed_run_time <= now) {
+    in_flight_kick_delayed_tasks_.erase(
+        delayed_task_queue_.top().delayed_run_time);
+    EnqueueTaskLocked(delayed_task_queue_.top());
+    delayed_task_queue_.pop();
+  }
+  // Any remaining tasks are in the future, so queue a task to kick them.
+  if (!delayed_task_queue_.empty()) {
+    base::TimeTicks next_run_time = delayed_task_queue_.top().delayed_run_time;
+    // Make sure we don't have more than one KickDelayedTasks posted for a
+    // particular scheduled run time (note it's fine to have multiple ones in
+    // flight for distinct run times).
+    if (in_flight_kick_delayed_tasks_.find(next_run_time) ==
+        in_flight_kick_delayed_tasks_.end()) {
+      in_flight_kick_delayed_tasks_.insert(next_run_time);
+      base::TimeDelta delay = next_run_time - now;
+      return task_queue_manager_->PostDelayedTask(
+          FROM_HERE, Bind(&TaskQueue::KickDelayedTasks, this), delay);
+    }
+  }
+  return true;
+}
+
+void TaskQueue::KickDelayedTasks() {
+  base::AutoLock lock(lock_);
+  ScheduleDelayedWorkLocked(task_queue_manager_->Now());
+}
+
 bool TaskQueue::IsQueueEmpty() const {
   if (!work_queue_.empty())
     return false;
 
   {
     base::AutoLock lock(lock_);
     return incoming_queue_.empty();
   }
 }
 
@@ skipping 11 matching lines @@
 }
 
 bool TaskQueue::UpdateWorkQueue(
     base::TimeTicks* next_pending_delayed_task,
     TaskQueueManager::WorkQueueUpdateEventType event_type) {
   if (!work_queue_.empty())
     return true;
 
   {
     base::AutoLock lock(lock_);
-    if (!delayed_task_run_times_.empty()) {
+    if (!delayed_task_queue_.empty()) {
       *next_pending_delayed_task =
-          std::min(*next_pending_delayed_task, delayed_task_run_times_.top());
+          std::min(*next_pending_delayed_task,
+                   delayed_task_queue_.top().delayed_run_time);
     }
     if (!ShouldAutoPumpQueueLocked(event_type))
       return false;
     work_queue_.Swap(&incoming_queue_);
     TraceQueueSize(true);
     return true;
   }
 }
 
 base::PendingTask TaskQueue::TakeTaskFromWorkQueue() {
@@ skipping 27 matching lines @@
 void TaskQueue::EnqueueTaskLocked(const base::PendingTask& pending_task) {
   lock_.AssertAcquired();
   if (!task_queue_manager_)
     return;
   if (pump_policy_ == TaskQueueManager::PumpPolicy::AUTO &&
       incoming_queue_.empty())
     task_queue_manager_->MaybePostDoWorkOnMainRunner();
   incoming_queue_.push(pending_task);
 
   if (!pending_task.delayed_run_time.is_null()) {
-    // Update the time of the next pending delayed task.
-    while (!delayed_task_run_times_.empty() &&
-           delayed_task_run_times_.top() <= pending_task.delayed_run_time) {
-      delayed_task_run_times_.pop();
-    }
     // Clear the delayed run time because we've already applied the delay
     // before getting here.
     incoming_queue_.back().delayed_run_time = base::TimeTicks();

[Sami, 2015/03/02 16:38:32]

int: could do this unconditionally now.

   }
   TraceQueueSize(true);
 }
 
 void TaskQueue::SetPumpPolicy(TaskQueueManager::PumpPolicy pump_policy) {
   base::AutoLock lock(lock_);
   if (pump_policy == TaskQueueManager::PumpPolicy::AUTO &&
       pump_policy_ != TaskQueueManager::PumpPolicy::AUTO) {
     PumpQueueLocked();
   }
@@ skipping 309 matching lines @@
   state->EndArray();
   state->BeginDictionary("selector");
   selector_->AsValueInto(state.get());
   state->EndDictionary();
   if (should_run)
     state->SetInteger("selected_queue", selected_queue);
   return state;
 }
 
 }  // namespace content