[Reland] Optimize blink scheduler with an intrusive heap

third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h

Index: third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h
diff --git a/third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h b/third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h
new file mode 100644
index 0000000000000000000000000000000000000000..aee3c3a5ce3ec6e3136c049c8756164a0d59b1f2
--- /dev/null
+++ b/third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h
@@ -0,0 +1,169 @@
+// 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.
+
+#ifndef THIRD_PARTY_WEBKIT_SOURCE_PLATFORM_SCHEDULER_BASE_INTRUSIVE_HEAP_H_
+#define THIRD_PARTY_WEBKIT_SOURCE_PLATFORM_SCHEDULER_BASE_INTRUSIVE_HEAP_H_
+
+#include <vector>
+
+#include "base/logging.h"
+#include "public/platform/WebCommon.h"
+
+namespace blink {
+namespace scheduler {
+
+// A standard min-heap with the following assumptions:
+// 1. T has operator <=
+// 2. T has method void SetHeapIndex(size_t index)

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

I'd like to suggest using a callback, passed to constructor of InstrusiveHeap,
and invoke it when index changes.

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

3. T is moveable?
4. T is default-constructible? (it's not a very good thing to want).

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

Please bear in mind this probably isn't going to be used outside the scheduler. 
I could go to the effort of fixing that but honestly I don't think it's worth
it.

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

That will be a performance regression.  The method I chose has several benefits:

1.  It can be fully inlined
2. If the SetHeapHandle method is empty then compiler would completely remove
it.  It couldn't do that with a callback

+template <typename T>
+class BLINK_PLATFORM_EXPORT IntrusiveHeap {
+ public:
+  IntrusiveHeap() : nodes_(kMinimumHeapSize), size_(0) {}
+
+  bool empty() const { return size_ == 0; }
+
+  size_t size() const { return size_; }
+
+  void clear() {
+    nodes_.resize(kMinimumHeapSize);
+    size_ = 0;
+  }
+
+  const T& min() const {
+    DCHECK_GE(size_, 1u);
+    return nodes_[1];
+  }
+
+  void pop() {

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

It may be a good idea for pop and EraseHeapIndex to return elements. It will be
possible to get rid of GetNodesForTesting in that case.

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

Two points:

1. In general it's a good idea for containers to be similar to STL ones where
possible, to minimize confusion.  In the STL pop is void pop();
2. I originally added an extractMin method as well (which does what you
describe). It wasn't needed by the scheduler code so I removed it.

+    DCHECK_GE(size_, 1u);
+    size_t top_index = size_--;

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

Do we want to shrink down the size of the underlying vector?

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

No. These never get very large anyway (perhaps 100 at most)  Reclaiming memory
isn't a big deal for us.  Lets add a comment.

+    MakeHole(1u);
+    if (!empty())
+      MoveHoleDownAndFillWithLeafElement(1u, std::move(nodes_[top_index]));

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

Should we report to SetHeapIndex about element being deleted? Preferably, with
base:Optional<size_t>: SetHeapIndex(base::nullopt); 

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

We know when that happens already since we call erase or pop.

+  }
+
+  void insert(T&& element) {
+    size_++;
+    if (size_ >= nodes_.size())
+      nodes_.resize(size_ * 2);
+    // Notionally we have a hole in the tree at index |size_|, move this up
+    // to find the right insertion point.
+    MoveHoleUpAndFillWithElement(size_, std::move(element));
+  }
+
+  void EraseHeapIndex(size_t index) {
+    DCHECK_GT(index, kInvalidIndex);
+    DCHECK_LE(index, size_);
+    size_t top_index = size_--;
+    if (empty() || top_index == index)
+      return;
+    MakeHole(index);
+    if (nodes_[index] <= nodes_[top_index]) {
+      MoveHoleDownAndFillWithLeafElement(index, std::move(nodes_[top_index]));
+    } else {
+      MoveHoleUpAndFillWithElement(index, std::move(nodes_[top_index]));
+    }
+  }
+
+  void ReplaceMin(T&& element) {
+    // Note |element| might not be a leaf node so we can't use
+    // MoveHoleDownAndFillWithLeafElement.
+    MoveHoleDownAndFillWithElement(1u, std::move(element));
+  }
+
+  const std::vector<T>& GetNodesForTesting() const { return nodes_; }

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

I believe that we can replace this method with:
1. Returning deleted elements.
2. Adding iterator to iterate over a container.

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

I'd rather not.
I have reservations about iterators since mutating the heap invalidates them
still I suppose its less ugly.

+
+  enum { kInvalidIndex = 0u };

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

For my curiosity — what's the advantage of using enums (vs constexpr members)?

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

None.  It's just the old school way of doing it.

In fact it's a problem on MSVC since enums are signed there :(

+
+ private:
+  enum {
+    // The majority of sets in the scheduler have 0-3 items in them (a few will
+    // have perhaps up to 100), so this means we usually only have to allocate
+    // memory once.
+    kMinimumHeapSize = 4u
+  };
+
+  size_t MoveHole(size_t new_hole_pos, size_t old_hole_pos) {
+    DCHECK_GT(new_hole_pos, kInvalidIndex);
+    DCHECK_LE(new_hole_pos, size_);
+    DCHECK_GT(new_hole_pos, kInvalidIndex);
+    DCHECK_LE(new_hole_pos, size_);
+    DCHECK_NE(old_hole_pos, new_hole_pos);
+    nodes_[old_hole_pos] = std::move(nodes_[new_hole_pos]);
+    nodes_[old_hole_pos].SetHeapIndex(old_hole_pos);
+    return new_hole_pos;
+  }
+
+  // Notionally creates a hole in the tree at |index|.
+  void MakeHole(size_t index) { nodes_[index].SetHeapIndex(kInvalidIndex); }
+
+  void FillHole(size_t hole, T&& element) {
+    nodes_[hole] = std::move(element);
+    nodes_[hole].SetHeapIndex(hole);
+  }
+
+  // Moves the |hole| up the tree and when the right position has been found
+  // |element| is moved in.
+  void MoveHoleUpAndFillWithElement(size_t hole, T&& element) {
+    DCHECK_GT(hole, kInvalidIndex);
+    DCHECK_LE(hole, size_);
+    while (hole >= 2u) {
+      size_t parent_pos = hole / 2;
+      if (nodes_[parent_pos] <= element)
+        break;
+
+      hole = MoveHole(parent_pos, hole);
+    }
+    FillHole(hole, std::move(element));
+  }
+
+  // Moves the |hole| down the tree and when the right position has been found
+  // |element| is moved in.
+  void MoveHoleDownAndFillWithElement(size_t hole, T&& element) {
+    DCHECK_GT(hole, kInvalidIndex);
+    DCHECK_LE(hole, size_);
+    size_t child_pos = hole * 2;
+    while (child_pos < size_) {
+      if (nodes_[child_pos + 1] <= nodes_[child_pos])
+        child_pos++;
+
+      if (element <= nodes_[child_pos])
+        break;
+
+      hole = MoveHole(child_pos, hole);
+      child_pos *= 2;
+    }
+    if (child_pos == size_ && !(element <= nodes_[child_pos]))
+      hole = MoveHole(child_pos, hole);
+    FillHole(hole, std::move(element));
+  }
+
+  // Moves the |hole| down the tree and when the right position has been found
+  // |leaf_element| is moved in.  Faster than MoveHoleDownAndFillWithElement
+  // (it does one key comparison per level instead of two) but only valid for
+  // leaf elements (i.e. one of the max values).
+  void MoveHoleDownAndFillWithLeafElement(size_t hole, T&& leaf_element) {
+    DCHECK_GT(hole, kInvalidIndex);
+    DCHECK_LE(hole, size_);
+    size_t child_pos = hole * 2;
+    while (child_pos < size_) {
+      size_t second_child = child_pos + 1;
+      if (nodes_[second_child] <= nodes_[child_pos])
+        child_pos = second_child;
+      hole = MoveHole(child_pos, hole);
+      child_pos *= 2;
+    }
+    if (child_pos == size_)
+      hole = MoveHole(child_pos, hole);
+    MoveHoleUpAndFillWithElement(hole, std::move(leaf_element));
+  }
+
+  std::vector<T> nodes_;  // NOTE we use 1-based indexing
+  size_t size_;
+};
+
+}  // namespace scheduler
+}  // namespace blink
+
+#endif  // THIRD_PARTY_WEBKIT_SOURCE_PLATFORM_SCHEDULER_BASE_INTRUSIVE_HEAP_H_