[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..34fafb905512eae8210adf2d85840838a8919a5e
--- /dev/null
+++ b/third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h
@@ -0,0 +1,153 @@
+// 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"

[haraken, 2016/10/14 13:12:26]

This is unused.

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

It's needed for BLINK_PLATFORM_EXPORT

+
+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)
+template <typename T>
+class BLINK_PLATFORM_EXPORT IntrusiveHeap {

[haraken, 2016/10/14 13:12:25]

You might want to add a couple of more DCHECKs (to HeapifyDown, HeapifyUp,
MoveHoleDown etc) about the invariant that a binary heap must hold.

[haraken, 2016/10/14 13:12:26]

I'm just curious but what's a difference between an intrusive heap and a normal
binary heap?

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

It's a binary heap that requires the element to store the index somewhere. If
you ca think of a better name, please let me know.

[alex clarke (OOO till 29th), 2016/10/14 14:52:38]

Thanks for making that suggestion, it revealed a bug with
DelayedWakeup::operator<=

+ public:
+  IntrusiveHeap() : nodes_(4), size_(0) {}

[haraken, 2016/10/14 13:12:25]

Add a comment about why 4.

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

Done.

+
+  bool empty() const { return size_ == 0; }
+
+  size_t size() const { return size_; }
+
+  void clear() {
+    nodes_.resize(4);
+    size_ = 0;
+  }
+
+  const T& min() const {
+    DCHECK_GE(size_, 1u);
+    return nodes_[1];
+  }
+
+  void eraseMin() {

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

nit: EraseMin/ExtractMin/etc. (I think we should just use Chromium style for new
code from now on.)

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

For containers my preference is stl style where the names match and chromium
otherwise. I.e. this should really be called pop WDYT?

+    DCHECK_GE(size_, 1u);
+    size_t top_index = size_--;
+    if (!empty())
+      MoveHoleDown(1u, nodes_[top_index]);
+  }
+
+  T extractMin() {

[haraken, 2016/10/14 13:12:25]

Can we remove eraseMin? extractMin would be enough.

extractMin => popMin ?

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

I had thought we'd end up using this but it didn't turn out that way - lets
remove it.

Incidentally extract is the STL style name of this kind of thing (as of C++17
anyway).

+    DCHECK_GE(size_, 1u);
+    T top = std::move(nodes_[1]);
+    size_t top_index = size_--;
+    if (!empty())
+      MoveHoleDown(1u, nodes_[top_index]);
+    return std::move(top);
+  }
+
+  void insert(T element) {
+    size_++;
+    if (size_ >= nodes_.size())
+      nodes_.resize(size_ * 2);
+    HeapifyUp(size_, element);
+  }
+
+  void eraseHeapIndex(size_t index) {
+    DCHECK_GE(index, 1u);
+    DCHECK_LE(index, size_);
+    size_t top_index = size_--;
+    if (empty() || top_index == index)
+      return;
+    if (nodes_[index] <= nodes_[top_index]) {
+      MoveHoleDown(index, nodes_[top_index]);
+    } else {
+      HeapifyUp(index, nodes_[top_index]);
+    }
+  }
+
+  void replaceMin(T element) {
+    // Note |element| might not be a leaf node so we can't use MoveHoleDown.
+    HeapifyDown(1u, element);
+  }
+
+  const std::vector<T>& GetNodesForTesting() const { return nodes_; }
+
+ private:
+  void MoveNode(size_t from, size_t to) {
+    DCHECK_GE(from, 1u);
+    DCHECK_LE(from, size_);
+    DCHECK_GE(to, 1u);
+    DCHECK_LE(to, size_);
+    DCHECK_NE(from, to);
+    nodes_[to] = std::move(nodes_[from]);
+    nodes_[to].SetHeapIndex(to);
+  }
+
+  void HeapifyUp(size_t pos, T& element) {

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

nit: non-const reference maybe should be a pointer? (below too)

[haraken, 2016/10/14 13:12:25]

MoveElementUp ?

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

I ended up calling this MoveHoleUpAndFillWithElement to better describe what it
does.  WDYT?

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

It should probably be an R value, since that better reflects what we're doing
with it.

+    DCHECK_GE(pos, 1u);
+    DCHECK_LE(pos, size_);
+    while (pos >= 2u) {
+      size_t parent_pos = pos / 2;
+      if (nodes_[parent_pos] <= element)
+        break;
+
+      MoveNode(parent_pos, pos);
+      pos = parent_pos;
+    }
+    nodes_[pos] = std::move(element);
+    nodes_[pos].SetHeapIndex(pos);
+  }
+
+  void HeapifyDown(size_t pos, T& element) {

[haraken, 2016/10/14 13:12:26]

MoveElementDown ?

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

I ended up calling this MoveHoleDownAndFillWithElement to better describe what
it does.  WDYT?

+    DCHECK_GE(pos, 1u);
+    DCHECK_LE(pos, size_);
+    size_t child_pos = pos * 2;
+    while (child_pos < size_) {
+      if (nodes_[child_pos + 1] <= nodes_[child_pos])
+        child_pos++;
+
+      if (element <= nodes_[child_pos])
+        break;
+
+      MoveNode(child_pos, pos);
+      pos = child_pos;
+      child_pos *= 2;
+    }
+    if (child_pos == size_ && !(element <= nodes_[child_pos])) {
+      MoveNode(child_pos, pos);
+      pos = child_pos;
+    }
+    nodes_[pos] = std::move(element);
+    nodes_[pos].SetHeapIndex(pos);
+  }
+
+  // NB this is a standard optimization, as used by the STL. HeapifyDown does

[haraken, 2016/10/14 13:12:25]

NB => Note ?

BTW, we normally don't write "Note" for comments.

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

Done.

+  // two comparisons per level, but this only does one.
+  // NOTE |element| is assumed to be a leaf node.
+  void MoveHoleDown(size_t hole, T& element) {
+    size_t new_hole = hole * 2;
+    while (new_hole <= size_) {
+      size_t second_child = new_hole + 1;
+      if (second_child <= size_ && nodes_[second_child] <= nodes_[new_hole])
+        new_hole = second_child;
+      MoveNode(new_hole, hole);
+      hole = new_hole;
+      new_hole *= 2;
+    }
+    HeapifyUp(hole, 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_