[Reland] Optimize blink scheduler with an intrusive heap

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

Index: third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
diff --git a/third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc b/third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
index 194524f1740f557c25154ab3aeed6097d013fef3..c41b870f7ba1508c45ff346aebd345a14266e44e 100644
--- a/third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
+++ b/third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
@@ -5,59 +5,55 @@
 #include "platform/scheduler/base/work_queue_sets.h"
 
 #include "base/logging.h"
-#include "platform/scheduler/base/work_queue.h"
 
 namespace blink {
 namespace scheduler {
 namespace internal {
 
 WorkQueueSets::WorkQueueSets(size_t num_sets, const char* name)
-    : enqueue_order_to_work_queue_maps_(num_sets), name_(name) {}
+    : work_queue_heaps_(num_sets), name_(name) {}
 
 WorkQueueSets::~WorkQueueSets() {}
 
 void WorkQueueSets::AddQueue(WorkQueue* work_queue, size_t set_index) {
   DCHECK(!work_queue->work_queue_sets());
-  DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size());
+  DCHECK_LT(set_index, work_queue_heaps_.size());
   EnqueueOrder enqueue_order;
   bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
   work_queue->AssignToWorkQueueSets(this);
   work_queue->AssignSetIndex(set_index);
   if (!has_enqueue_order)
     return;
-  enqueue_order_to_work_queue_maps_[set_index].insert(
-      std::make_pair(enqueue_order, work_queue));
+  work_queue_heaps_[set_index].insert({enqueue_order, work_queue});
 }
 
 void WorkQueueSets::RemoveQueue(WorkQueue* work_queue) {
   DCHECK_EQ(this, work_queue->work_queue_sets());
-  EnqueueOrder enqueue_order;
-  bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
   work_queue->AssignToWorkQueueSets(nullptr);
-  if (!has_enqueue_order)
+  size_t heap_index = work_queue->heap_index();
+  if (heap_index == IntrusiveHeap<OldestTaskEnqueueOrder>::kInvalidIndex)

[altimin, 2016/10/14 17:06:36]

I don't like exposing implementation detail (kInvalidIndex).
base::Optional<size_t> maybe?

[alex clarke (OOO till 29th), 2016/10/14 21:49:46]

Agreed.
Overkill ;O  We can add a HeapHandle class which has a IsValid method.

     return;
   size_t set_index = work_queue->work_queue_set_index();
-  DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size());
+  DCHECK_LT(set_index, work_queue_heaps_.size());
   DCHECK_EQ(
       work_queue,
-      enqueue_order_to_work_queue_maps_[set_index].find(enqueue_order)->second);
-  enqueue_order_to_work_queue_maps_[set_index].erase(enqueue_order);
+      work_queue_heaps_[set_index].GetNodesForTesting()[heap_index].value);

[altimin, 2016/10/14 17:06:36]

Here it should be possible to use return value of EraseHeapIndex instead of
using GetNodesForTesting.

[alex clarke (OOO till 29th), 2016/10/14 21:49:46]

We could, but the problem is in release we don't need the return value.  The
cost isn't that great but it's counter to the spirit of what I'm trying to do.

Incidentally I added the DCHECK during a period where we where paranoid about
possible set corruption.  It's never fired. I'd sooner get rid of it :)

+  work_queue_heaps_[set_index].EraseHeapIndex(heap_index);
 }
 
 void WorkQueueSets::ChangeSetIndex(WorkQueue* work_queue, size_t set_index) {
   DCHECK_EQ(this, work_queue->work_queue_sets());
-  DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size());
+  DCHECK_LT(set_index, work_queue_heaps_.size());
   EnqueueOrder enqueue_order;
   bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
   size_t old_set = work_queue->work_queue_set_index();
-  DCHECK_LT(old_set, enqueue_order_to_work_queue_maps_.size());
+  DCHECK_LT(old_set, work_queue_heaps_.size());
   DCHECK_NE(old_set, set_index);
   work_queue->AssignSetIndex(set_index);
   if (!has_enqueue_order)
     return;
-  enqueue_order_to_work_queue_maps_[old_set].erase(enqueue_order);
-  enqueue_order_to_work_queue_maps_[set_index].insert(
-      std::make_pair(enqueue_order, work_queue));
+  work_queue_heaps_[old_set].EraseHeapIndex(work_queue->heap_index());
+  work_queue_heaps_[set_index].insert({enqueue_order, work_queue});
 }
 
 void WorkQueueSets::OnPushQueue(WorkQueue* work_queue) {
@@ -68,55 +64,40 @@ void WorkQueueSets::OnPushQueue(WorkQueue* work_queue) {
   bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
   DCHECK(has_enqueue_order);
   size_t set_index = work_queue->work_queue_set_index();
-  DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size())
-      << " set_index = " << set_index;
-  enqueue_order_to_work_queue_maps_[set_index].insert(
-      std::make_pair(enqueue_order, work_queue));
+  DCHECK_LT(set_index, work_queue_heaps_.size()) << " set_index = "
+                                                 << set_index;
+  work_queue_heaps_[set_index].insert({enqueue_order, work_queue});
 }
 
 void WorkQueueSets::OnPopQueue(WorkQueue* work_queue) {
   // Assume that |work_queue| contains the lowest enqueue_order.
   size_t set_index = work_queue->work_queue_set_index();
   DCHECK_EQ(this, work_queue->work_queue_sets());
-  DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size());
-  DCHECK(!enqueue_order_to_work_queue_maps_[set_index].empty())
+  DCHECK_LT(set_index, work_queue_heaps_.size());
+  DCHECK(!work_queue_heaps_[set_index].empty()) << " set_index = " << set_index;
+  DCHECK_EQ(work_queue_heaps_[set_index].min().value, work_queue)
       << " set_index = " << set_index;
-  DCHECK_EQ(enqueue_order_to_work_queue_maps_[set_index].begin()->second,
-            work_queue)
-      << " set_index = " << set_index;
-  EnqueueOrderToWorkQueueMap::iterator old_it =
-      enqueue_order_to_work_queue_maps_[set_index].begin();
   EnqueueOrder enqueue_order;
   if (work_queue->GetFrontTaskEnqueueOrder(&enqueue_order)) {
-    // Amortized O(1) if the new location is close to |old_it|, otherwise
-    // O(log n).
-    enqueue_order_to_work_queue_maps_[set_index].insert(
-        std::make_pair(enqueue_order, work_queue));
+    work_queue_heaps_[set_index].ReplaceMin({enqueue_order, work_queue});
+  } else {
+    work_queue_heaps_[set_index].pop();
   }
-  // O(1)
-  enqueue_order_to_work_queue_maps_[set_index].erase(old_it);
 }
 
 bool WorkQueueSets::GetOldestQueueInSet(size_t set_index,
                                         WorkQueue** out_work_queue) const {
-  DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size());
-  if (enqueue_order_to_work_queue_maps_[set_index].empty())
+  DCHECK_LT(set_index, work_queue_heaps_.size());
+  if (work_queue_heaps_[set_index].empty())
     return false;
-  *out_work_queue =
-      enqueue_order_to_work_queue_maps_[set_index].begin()->second;
-#ifndef NDEBUG
-  EnqueueOrder enqueue_order;
-  DCHECK((*out_work_queue)->GetFrontTaskEnqueueOrder(&enqueue_order));
-  DCHECK_EQ(enqueue_order,
-            enqueue_order_to_work_queue_maps_[set_index].begin()->first);
-#endif
+  *out_work_queue = work_queue_heaps_[set_index].min().value;
   return true;
 }
 
 bool WorkQueueSets::IsSetEmpty(size_t set_index) const {
-  DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size())
-      << " set_index = " << set_index;
-  return enqueue_order_to_work_queue_maps_[set_index].empty();
+  DCHECK_LT(set_index, work_queue_heaps_.size()) << " set_index = "
+                                                 << set_index;
+  return work_queue_heaps_[set_index].empty();
 }
 
 #if DCHECK_IS_ON() || !defined(NDEBUG)
@@ -125,12 +106,11 @@ bool WorkQueueSets::ContainsWorkQueueForTest(
   EnqueueOrder enqueue_order;
   bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
 
-  for (const EnqueueOrderToWorkQueueMap& map :
-       enqueue_order_to_work_queue_maps_) {
-    for (const EnqueueOrderToWorkQueueMap::value_type& key_value_pair : map) {
-      if (key_value_pair.second == work_queue) {
+  for (const IntrusiveHeap<OldestTaskEnqueueOrder>& heap : work_queue_heaps_) {
+    for (size_t i = 1; i <= heap.size(); i++) {
+      if (heap.GetNodesForTesting()[i].value == work_queue) {

[altimin, 2016/10/14 17:06:36]

I believe that adding iteration support to public API covers this use case
instead of GetNodesForTesting.

[alex clarke (OOO till 29th), 2016/10/14 21:49:46]

As mentioned I have reservations about iterators, however it does result in
nicer looking code.  Done.

         DCHECK(has_enqueue_order);
-        DCHECK_EQ(key_value_pair.first, enqueue_order);
+        DCHECK_EQ(heap.GetNodesForTesting()[i].key, enqueue_order);
         DCHECK_EQ(this, work_queue->work_queue_sets());
         return true;
       }