Run task queue manager work in batches

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 "base/bind.h"
 #include "base/debug/trace_event.h"
 #include "base/debug/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();
+}
+
 namespace content {
 namespace internal {
 
 class TaskQueue : public base::SingleThreadTaskRunner {
  public:
   TaskQueue(TaskQueueManager* task_queue_manager);
 
   // base::SingleThreadTaskRunner implementation.
   bool RunsTasksOnCurrentThread() const override;
   bool PostDelayedTask(const tracked_objects::Location& from_here,
@@ skipping 11 matching lines @@
   // 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);
 
   bool IsQueueEmpty() const;
 
   void SetAutoPump(bool auto_pump);
   void PumpQueue();
 
-  bool UpdateWorkQueue();
+  bool UpdateWorkQueue(base::TimeTicks* next_pending_delayed_task);
   base::PendingTask TakeTaskFromWorkQueue();
 
   void WillDeleteTaskQueueManager();
 
   base::TaskQueue& work_queue() { return work_queue_; }
 
   void set_name(const char* name) { name_ = name; }
 
   void AsValueInto(base::debug::TracedValue* state) const;
 
@@ skipping 13 matching lines @@
                                base::debug::TracedValue* state);
   static void TaskAsValueInto(const base::PendingTask& task,
                               base::debug::TracedValue* state);
 
   // This lock protects all members except the work queue.
   mutable base::Lock lock_;
   TaskQueueManager* task_queue_manager_;
   base::TaskQueue incoming_queue_;
   bool auto_pump_;
   const char* name_;
+  std::priority_queue<base::TimeTicks,
+                      std::vector<base::TimeTicks>,
+                      std::greater<base::TimeTicks>> delayed_task_run_times_;

[rmcilroy, 2015/01/21 12:18:26]

Would it be simpler to maintain a single queue in the TaskQueueManager rather
than one in each TaskQueue?  Delayed runtimes could be pushed in
TaskQueueManager::PostDelayedTask and popped in DoWork. WDYT?

[Sami, 2015/01/21 14:31:16]

Like we talked about, having a shared queue would need a lock around it. My
handwavey feeling is that having an extra lock would be worse than the current
code which polls each queue for the nearest task (basically an std::min<int64>
per task queue). Any preference?

[rmcilroy, 2015/01/21 15:13:09]

Yeah I agree, it's better to keep these in seperate queues to avoid a global TQM
lock.

 
   base::TaskQueue work_queue_;
 
   DISALLOW_COPY_AND_ASSIGN(TaskQueue);
 };
 
 TaskQueue::TaskQueue(TaskQueueManager* task_queue_manager)
     : task_queue_manager_(task_queue_manager),
       auto_pump_(true),
       name_(nullptr) {
@@ skipping 19 matching lines @@
                                     base::TimeDelta delay,
                                     bool nestable) {
   base::AutoLock lock(lock_);
   if (!task_queue_manager_)
     return false;
 
   base::PendingTask pending_task(from_here, task, base::TimeTicks(), 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);
   }
   EnqueueTaskLocked(pending_task);
   return true;
 }
 
 bool TaskQueue::IsQueueEmpty() const {
   if (!work_queue_.empty())
     return false;
 
   {
     base::AutoLock lock(lock_);
     return incoming_queue_.empty();
   }
 }
 
-bool TaskQueue::UpdateWorkQueue() {
+bool TaskQueue::UpdateWorkQueue(base::TimeTicks* next_pending_delayed_task) {
   if (!work_queue_.empty())
     return true;
 
   {
     base::AutoLock lock(lock_);
+    if (!delayed_task_run_times_.empty()) {
+      *next_pending_delayed_task =
+          std::min(*next_pending_delayed_task, delayed_task_run_times_.top());
+    }
     if (!auto_pump_ || incoming_queue_.empty())
       return false;
     work_queue_.Swap(&incoming_queue_);
     TraceWorkQueueSize();
     return true;
   }
 }
 
 base::PendingTask TaskQueue::TakeTaskFromWorkQueue() {
   base::PendingTask pending_task = work_queue_.front();
@@ skipping 14 matching lines @@
   EnqueueTaskLocked(pending_task);
 }
 
 void TaskQueue::EnqueueTaskLocked(const base::PendingTask& pending_task) {
   lock_.AssertAcquired();
   if (!task_queue_manager_)
     return;
   if (auto_pump_ && 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();
+    }
+  }
 }
 
 void TaskQueue::SetAutoPump(bool auto_pump) {
   base::AutoLock lock(lock_);
   if (auto_pump) {
     auto_pump_ = true;
     PumpQueueLocked();
   } else {
     auto_pump_ = false;
   }
@@ skipping 55 matching lines @@
 
 }  // namespace internal
 
 TaskQueueManager::TaskQueueManager(
     size_t task_queue_count,
     scoped_refptr<base::SingleThreadTaskRunner> main_task_runner,
     TaskQueueSelector* selector)
     : main_task_runner_(main_task_runner),
       selector_(selector),
       pending_dowork_count_(0),
+      work_batch_size_(1),
+      time_source_(nullptr),
       weak_factory_(this) {
   DCHECK(main_task_runner->RunsTasksOnCurrentThread());
   TRACE_EVENT_OBJECT_CREATED_WITH_ID(
       TRACE_DISABLED_BY_DEFAULT("renderer.scheduler"), "TaskQueueManager",
       this);
 
   task_queue_manager_weak_ptr_ = weak_factory_.GetWeakPtr();
   for (size_t i = 0; i < task_queue_count; i++) {
     scoped_refptr<internal::TaskQueue> queue(
         make_scoped_refptr(new internal::TaskQueue(this)));
@@ skipping 34 matching lines @@
   internal::TaskQueue* queue = Queue(queue_index);
   queue->SetAutoPump(auto_pump);
 }
 
 void TaskQueueManager::PumpQueue(size_t queue_index) {
   main_thread_checker_.CalledOnValidThread();
   internal::TaskQueue* queue = Queue(queue_index);
   queue->PumpQueue();
 }
 
-bool TaskQueueManager::UpdateWorkQueues() {
+bool TaskQueueManager::UpdateWorkQueues(
+    base::TimeTicks* next_pending_delayed_task) {
   // TODO(skyostil): This is not efficient when the number of queues grows very
   // large due to the number of locks taken. Consider optimizing when we get
   // there.
   main_thread_checker_.CalledOnValidThread();
   bool has_work = false;
   for (auto& queue : queues_)
-    has_work |= queue->UpdateWorkQueue();
+    has_work |= queue->UpdateWorkQueue(next_pending_delayed_task);
   return has_work;
 }
 
 void TaskQueueManager::MaybePostDoWorkOnMainRunner() {
   bool on_main_thread = main_task_runner_->BelongsToCurrentThread();
   if (on_main_thread) {
     // We only want one pending DoWork posted from the main thread, or we risk
     // an explosion of pending DoWorks which could starve out everything else.
     if (pending_dowork_count_ > 0) {
       return;
     }
     pending_dowork_count_++;
   }
 
   main_task_runner_->PostTask(
       FROM_HERE, Bind(&TaskQueueManager::DoWork, task_queue_manager_weak_ptr_,
                       on_main_thread));
 }
 
 void TaskQueueManager::DoWork(bool posted_from_main_thread) {
   if (posted_from_main_thread) {
     pending_dowork_count_--;
     DCHECK_GE(pending_dowork_count_, 0);
   }
   main_thread_checker_.CalledOnValidThread();
-  if (!UpdateWorkQueues())
-    return;
 
-  size_t queue_index;
-  if (!SelectWorkQueueToService(&queue_index))
-    return;
-  MaybePostDoWorkOnMainRunner();
-  ProcessTaskFromWorkQueue(queue_index);
+  base::TimeTicks next_pending_delayed_task(
+      base::TimeTicks::FromInternalValue(kMaxTimeTicks));
+  for (int i = 0; i < work_batch_size_; i++) {
+    if (!UpdateWorkQueues(&next_pending_delayed_task))
+      return;
+
+    // Interrupt the work batch if we should run the next delayed task.
+    if (i > 0 && next_pending_delayed_task.ToInternalValue() != kMaxTimeTicks &&
+        Now() >= next_pending_delayed_task)

[picksi1, 2015/01/21 11:16:08]

The checks for i>0 and (on line 377) checking for i==0 makes this for loop a bit
tricky to understand (plus adds some inefficiency here?). How much duplicated
code would result in pulling the i==0 work out of the loop?

also (I haven't followed the logic entirely...) is the check for !=
kMaxTimeTicks needed here? If UpdateWorkQueues returns true doesn't it imply
that the next_pending_delayed_task has a decent value?

[Sami, 2015/01/21 14:31:15]

Actually the i==0 is a bit of a premature optimization so I've gotten rid of it.
Pulling it out would've meant duplicating almost all of the loop :\
Good question. We need the check because it's possible that we won't have any
pending *delayed* tasks (just normal tasks), and I wanted to avoid the overhead
of reading the current time in that case.

+      return;
+
+    size_t queue_index;
+    if (!SelectWorkQueueToService(&queue_index))
+      return;
+    if (i == 0)
+      MaybePostDoWorkOnMainRunner();
+    ProcessTaskFromWorkQueue(queue_index);
+  }
 }
 
 bool TaskQueueManager::SelectWorkQueueToService(size_t* out_queue_index) {
   bool should_run = selector_->SelectWorkQueueToService(out_queue_index);
   TRACE_EVENT_OBJECT_SNAPSHOT_WITH_ID(
       TRACE_DISABLED_BY_DEFAULT("renderer.scheduler"), "TaskQueueManager", this,
       AsValueWithSelectorResult(should_run, *out_queue_index));
   return should_run;
 }
 
@@ skipping 28 matching lines @@
   DCHECK(delay > base::TimeDelta());
   return main_task_runner_->PostDelayedTask(from_here, task, delay);
 }
 
 void TaskQueueManager::SetQueueName(size_t queue_index, const char* name) {
   main_thread_checker_.CalledOnValidThread();
   internal::TaskQueue* queue = Queue(queue_index);
   queue->set_name(name);
 }
 
+void TaskQueueManager::SetWorkBatchSize(int work_batch_size) {
+  main_thread_checker_.CalledOnValidThread();
+  DCHECK_GE(work_batch_size, 1);
+  work_batch_size_ = work_batch_size;
+}
+
+void TaskQueueManager::SetTimeSourceForTesting(
+    scoped_refptr<cc::TestNowSource> time_source) {
+  main_thread_checker_.CalledOnValidThread();
+  time_source_ = time_source;
+}
+
+base::TimeTicks TaskQueueManager::Now() const {
+  return UNLIKELY(time_source_) ? time_source_->Now() : base::TimeTicks::Now();
+}
+
 scoped_refptr<base::debug::ConvertableToTraceFormat>
 TaskQueueManager::AsValueWithSelectorResult(bool should_run,
                                             size_t selected_queue) const {
   main_thread_checker_.CalledOnValidThread();
   scoped_refptr<base::debug::TracedValue> state =
       new base::debug::TracedValue();
   state->BeginArray("queues");
   for (auto& queue : queues_)
     queue->AsValueInto(state.get());
   state->EndArray();
   state->BeginDictionary("selector");
   selector_->AsValueInto(state.get());
   state->EndDictionary();
   if (should_run)
     state->SetInteger("selected_queue", selected_queue);
   return state;
 }
 
 }  // namespace content