[Reland] Optimize blink scheduler with an intrusive heap

third_party/WebKit/Source/platform/scheduler/base/time_domain.cc

 // Copyright 2015 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 "platform/scheduler/base/time_domain.h"
 
 #include <set>
 
 #include "platform/scheduler/base/task_queue_impl.h"
 #include "platform/scheduler/base/task_queue_manager_delegate.h"
 #include "platform/scheduler/base/work_queue.h"
 
 namespace blink {
 namespace scheduler {
 
+struct TimeDomain::HeapElement {
+  base::TimeTicks key;
+  internal::TaskQueueImpl* value;
+
+  bool operator<=(const HeapElement& other) const { return key <= other.key; }
+
+  void SetHeapIndex(size_t i) { value->set_heap_index(i); }
+};
+
 TimeDomain::TimeDomain(Observer* observer) : observer_(observer) {}
 
 TimeDomain::~TimeDomain() {
   DCHECK(main_thread_checker_.CalledOnValidThread());
 }
 
 void TimeDomain::RegisterQueue(internal::TaskQueueImpl* queue) {
   DCHECK(main_thread_checker_.CalledOnValidThread());
   DCHECK_EQ(queue->GetTimeDomain(), this);
 }
 
 void TimeDomain::UnregisterQueue(internal::TaskQueueImpl* queue) {
   DCHECK(main_thread_checker_.CalledOnValidThread());
   DCHECK_EQ(queue->GetTimeDomain(), this);
   UnregisterAsUpdatableTaskQueue(queue);
 
-  // If present remove |task_queue| from delayed_wakeup_multimap_.
-  // O(log n)
-  QueueToDelayedWakeupMultimapIteratorMap::iterator it =
-      queue_to_delayed_wakeup_multimap_iterator_map_.find(queue);
-
-  if (it == queue_to_delayed_wakeup_multimap_iterator_map_.end())
+  // If no wakeup has been requested then bail out.
+  if (queue->time_domain_wakeup().is_null())
     return;
 
-  // O(1) amortized.
-  delayed_wakeup_multimap_.erase(it->second);
-  queue_to_delayed_wakeup_multimap_iterator_map_.erase(it);
+  // O(log n)
+  delayed_wakeup_queue_.eraseHeapIndex(queue->heap_index());
+  queue->set_time_domain_wakeup(base::TimeTicks());
+  queue->set_heap_index(0u);

[Sami, 2016/10/14 07:26:16]

Could we make 0u a named constant so 1-basedness of IntrusiveHeap doesn't leak
out?

[alex clarke (OOO till 29th), 2016/10/14 13:55:35]

I think I should actually move this into the template, it's easy to get wrong.

 }
 
 void TimeDomain::MigrateQueue(internal::TaskQueueImpl* queue,
                               TimeDomain* destination_time_domain) {
   DCHECK(main_thread_checker_.CalledOnValidThread());
   DCHECK_EQ(queue->GetTimeDomain(), this);
   DCHECK(destination_time_domain);
 
   // Make sure we remember to update |queue| if it's got incoming immediate
   // work.
   if (UnregisterAsUpdatableTaskQueue(queue))
     destination_time_domain->updatable_queue_set_.insert(queue);
 
-  // If present remove |task_queue| from delayed_wakeup_multimap_.
-  // O(log n)
-  QueueToDelayedWakeupMultimapIteratorMap::iterator it =
-      queue_to_delayed_wakeup_multimap_iterator_map_.find(queue);
-
-  if (it == queue_to_delayed_wakeup_multimap_iterator_map_.end())
+  // If no wakeup has been requested then bail out.
+  if (queue->time_domain_wakeup().is_null())
     return;
 
+  // O(log n)
+  delayed_wakeup_queue_.eraseHeapIndex(queue->heap_index());
+  queue->set_time_domain_wakeup(base::TimeTicks());
+  queue->set_heap_index(0u);
+
   base::TimeTicks destination_now = destination_time_domain->Now();
-  destination_time_domain->ScheduleDelayedWork(queue, it->second->first,
-                                               destination_now);
-
-  // O(1) amortized.
-  delayed_wakeup_multimap_.erase(it->second);
-  queue_to_delayed_wakeup_multimap_iterator_map_.erase(it);
+  destination_time_domain->ScheduleDelayedWork(
+      queue, queue->time_domain_wakeup(), destination_now);
 }
 
 void TimeDomain::ScheduleDelayedWork(internal::TaskQueueImpl* queue,
                                      base::TimeTicks delayed_run_time,
                                      base::TimeTicks now) {
   DCHECK(main_thread_checker_.CalledOnValidThread());
   // We only want to store a single wakeup per queue, so we need to remove any
   // previously registered wake up for |queue|.
-  QueueToDelayedWakeupMultimapIteratorMap::iterator it =
-      queue_to_delayed_wakeup_multimap_iterator_map_.find(queue);
+  if (!queue->time_domain_wakeup().is_null()) {
+    delayed_wakeup_queue_.eraseHeapIndex(queue->heap_index());
+    queue->set_time_domain_wakeup(base::TimeTicks());
+    queue->set_heap_index(0u);
+  }
 
-  if (it != queue_to_delayed_wakeup_multimap_iterator_map_.end())
-    delayed_wakeup_multimap_.erase(it->second);
-
-  if (delayed_wakeup_multimap_.empty() ||
-      delayed_run_time < delayed_wakeup_multimap_.begin()->first) {
+  if (delayed_wakeup_queue_.empty() ||
+      delayed_run_time < delayed_wakeup_queue_.min().key) {
     base::TimeDelta delay = std::max(base::TimeDelta(), delayed_run_time - now);
     RequestWakeup(now, delay);
   }
 
-  if (it != queue_to_delayed_wakeup_multimap_iterator_map_.end()) {
-    // TODO(alexclarke): Use C++17 extract & insert to more efficiently modify
-    // |queue_to_delayed_wakeup_multimap_iterator_map_|.
-    it->second = delayed_wakeup_multimap_.insert({delayed_run_time, queue});
-  } else {
-    // Insert the wakeup and store the map iterator for later convenience.
-    queue_to_delayed_wakeup_multimap_iterator_map_.insert(
-        {queue, delayed_wakeup_multimap_.insert({delayed_run_time, queue})});
-  }
+  delayed_wakeup_queue_.insert({delayed_run_time, queue});

[Sami, 2016/10/14 07:26:16]

Would it make sense to add an emplace() for this? Probably doesn't change much
in practice but it seems like that's the operation you want here.

[alex clarke (OOO till 29th), 2016/10/14 13:55:35]

The thing about emplace is, if we're gonna do it we should try to construct in
place with a placement new.  (The whole point of emplace is to avoid copies)

The thing I don't know how to do is extract the key from a parameter pack. It
also might not be possible depending on what T is.

+  queue->set_time_domain_wakeup(delayed_run_time);
 
   if (observer_)
     observer_->OnTimeDomainHasDelayedWork(queue);
 }
 
 void TimeDomain::RegisterAsUpdatableTaskQueue(internal::TaskQueueImpl* queue) {
   {
     base::AutoLock lock(newly_updatable_lock_);
     newly_updatable_.push_back(queue);
   }
@@ skipping 50 matching lines @@
     updatable_queue_set_.insert(newly_updatable_.back());
     newly_updatable_.pop_back();
   }
 }
 
 void TimeDomain::WakeupReadyDelayedQueues(LazyNow* lazy_now) {
   DCHECK(main_thread_checker_.CalledOnValidThread());
   // Wake up any queues with pending delayed work.  Note std::multipmap stores
   // the elements sorted by key, so the begin() iterator points to the earliest
   // queue to wakeup.
-  while (!delayed_wakeup_multimap_.empty()) {
-    DelayedWakeupMultimap::iterator next_wakeup =
-        delayed_wakeup_multimap_.begin();
-    if (next_wakeup->first > lazy_now->Now())
-      break;
+  while (!delayed_wakeup_queue_.empty() &&
+         delayed_wakeup_queue_.min().key <= lazy_now->Now()) {
+    internal::TaskQueueImpl* queue = delayed_wakeup_queue_.min().value;
+    // O(log n)
+    delayed_wakeup_queue_.eraseMin();
 
-    internal::TaskQueueImpl* queue = next_wakeup->second;
-
-    // O(1) amortized.
-    delayed_wakeup_multimap_.erase(next_wakeup);
-    // O(log n).
-    queue_to_delayed_wakeup_multimap_iterator_map_.erase(queue);
-
+    queue->set_time_domain_wakeup(base::TimeTicks());
     queue->WakeUpForDelayedWork(lazy_now);
   }
 }
 
 bool TimeDomain::NextScheduledRunTime(base::TimeTicks* out_time) const {
   DCHECK(main_thread_checker_.CalledOnValidThread());
-  if (delayed_wakeup_multimap_.empty())
+  if (delayed_wakeup_queue_.empty())
     return false;
 
-  *out_time = delayed_wakeup_multimap_.begin()->first;
+  *out_time = delayed_wakeup_queue_.min().key;
   return true;
 }
 
 bool TimeDomain::NextScheduledTaskQueue(TaskQueue** out_task_queue) const {
   DCHECK(main_thread_checker_.CalledOnValidThread());
-  if (delayed_wakeup_multimap_.empty())
+  if (delayed_wakeup_queue_.empty())
     return false;
 
-  *out_task_queue = delayed_wakeup_multimap_.begin()->second;
+  *out_task_queue = delayed_wakeup_queue_.min().value;
   return true;
 }
 
 void TimeDomain::AsValueInto(base::trace_event::TracedValue* state) const {
   state->BeginDictionary();
   state->SetString("name", GetName());
   state->BeginArray("updatable_queue_set");
   for (auto* queue : updatable_queue_set_)
     state->AppendString(queue->GetName());
   state->EndArray();
-  state->SetInteger("registered_delay_count", delayed_wakeup_multimap_.size());
-  if (!delayed_wakeup_multimap_.empty()) {
-    base::TimeDelta delay = delayed_wakeup_multimap_.begin()->first - Now();
+  state->SetInteger("registered_delay_count", delayed_wakeup_queue_.size());
+  if (!delayed_wakeup_queue_.empty()) {
+    base::TimeDelta delay = delayed_wakeup_queue_.min().key - Now();
     state->SetDouble("next_delay_ms", delay.InMillisecondsF());
   }
   AsValueIntoInternal(state);
   state->EndDictionary();
 }
 
 }  // namespace scheduler
 }  // namespace blink