[Reland] Optimize blink scheduler with an intrusive heap

[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Committed: https://crrev.com/1e13bd23dd2aac48f6bbcce65a1c56b14d5254ef
Committed: https://crrev.com/efc263f7724823965b63cf2b7ff367288e526629
Cr-Original-Original-Commit-Position: refs/heads/master@{#425647}
Cr-Original-Commit-Position: refs/heads/master@{#425930}
Cr-Commit-Position: refs/heads/master@{#426467}

[alex clarke (OOO till 29th), 2016-10-13 14:16:58]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-13 14:17:12]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[alex clarke (OOO till 29th), 2016-10-13 14:19:07]

alexclarke@chromium.org changed reviewers:
+ haraken@chromium.org, skyostil@chromium.org

[alex clarke (OOO till 29th), 2016-10-13 14:19:09]

The IntrusiveHeap seems to be marginally faster than FlatHeap/Set for the
scheduler use case.  It's a pretty well understood data structure so hopefully a
little less controversial :)

[commit-bot: I haz the power, 2016-10-13 14:58:17]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-13 14:58:18]

Dry run: Try jobs failed on following builders:
  android_n5x_swarming_rel on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/android_n5x_...)

[alex clarke (OOO till 29th), 2016-10-13 16:03:28]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-13 16:03:58]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-13 17:05:18]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-13 17:05:19]

Dry run: Try jobs failed on following builders:
  win_chromium_compile_dbg_ng on master.tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_comp...)

[haraken, 2016-10-14 07:00:00]

haraken@chromium.org changed reviewers:
+ yutak@chromium.org

[haraken, 2016-10-14 07:00:01]

+yutak

I haven't looked at the details but am fine with adding IntrusiveHeap to
scheduler/.

[Sami, 2016-10-14 07:26:17]

Overall looks great, although I also didn't go through the heap logic with a
fine tooth comb. That stuff is pretty subtle so it would be good for someone to
dig in :)

haraken@/yutak@, I'll be OoO soon so do you mind taking over reviewing this
patch?

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h (right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:38: void
eraseMin() {
nit: EraseMin/ExtractMin/etc. (I think we should just use Chromium style for new
code from now on.)

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:92: void
HeapifyUp(size_t pos, T& element) {
nit: non-const reference maybe should be a pointer? (below too)

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.h
(right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.h:236:
base::TimeTicks time_domain_wakeup;
It's a bit unclear what this is. |scheduled_time_domain_wakeup| maybe?

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/time_domain.cc (right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/time_domain.cc:48:
queue->set_heap_index(0u);
Could we make 0u a named constant so 1-basedness of IntrusiveHeap doesn't leak
out?

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/time_domain.cc:94:
delayed_wakeup_queue_.insert({delayed_run_time, queue});
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.

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/time_domain.h (right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/time_domain.h:138: struct
HeapElement;
Is there a more descriptive name for this? DelayedWakeup or something like that?

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
(right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc:44: if
(heap_index == 0u)
Ditto about using a constant.

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.h
(right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.h:69:
std::vector<IntrusiveHeap<HeapElement>> work_queue_heaps_;
WDYT of:

using EnqueueOrderToWorkQueueHeap = IntrusiveHeap<HeapElement>;
std::vector<EnqueueOrderToWorkQueueHeap> work_queue_heaps_;?

(I'm trying to make it more obvious to the casual reader what these data
structures contain. Another name for HeapElement might be good too but I'm
drawing a blank.)

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

haraken@chromium.org changed reviewers:
+ altimin@chromium.org

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

IntrusiveHeap LGTM with comments.

altimin@: Would you review the scheduler part?

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h (right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:11: #include
"public/platform/WebCommon.h"

This is unused.

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:20: class
BLINK_PLATFORM_EXPORT IntrusiveHeap {

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

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:20: class
BLINK_PLATFORM_EXPORT IntrusiveHeap {

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

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:22:
IntrusiveHeap() : nodes_(4), size_(0) {}

Add a comment about why 4.

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:45: T
extractMin() {

Can we remove eraseMin? extractMin would be enough.

extractMin => popMin ?

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:92: void
HeapifyUp(size_t pos, T& element) {

MoveElementUp ?

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:107: void
HeapifyDown(size_t pos, T& element) {

MoveElementDown ?

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:130: // NB
this is a standard optimization, as used by the STL. HeapifyDown does

NB => Note ?

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

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

PTAL

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h (right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:11: #include
"public/platform/WebCommon.h"
On 2016/10/14 13:12:26, haraken wrote:
> 
> This is unused.

It's needed for BLINK_PLATFORM_EXPORT

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:20: class
BLINK_PLATFORM_EXPORT IntrusiveHeap {
On 2016/10/14 13:12:26, haraken wrote:
> 
> I'm just curious but what's a difference between an intrusive heap and a
normal
> binary heap?

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.

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:22:
IntrusiveHeap() : nodes_(4), size_(0) {}
On 2016/10/14 13:12:25, haraken wrote:
> 
> Add a comment about why 4.

Done.

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:38: void
eraseMin() {
On 2016/10/14 07:26:16, Sami (OoO 0x1F1EF 0x1F1F5) wrote:
> nit: EraseMin/ExtractMin/etc. (I think we should just use Chromium style for
new
> code from now on.)

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

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:45: T
extractMin() {
On 2016/10/14 13:12:25, haraken wrote:
> 
> Can we remove eraseMin? extractMin would be enough.
> 
> extractMin => popMin ?

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).

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:92: void
HeapifyUp(size_t pos, T& element) {
On 2016/10/14 07:26:16, Sami (OoO 0x1F1EF 0x1F1F5) wrote:
> nit: non-const reference maybe should be a pointer? (below too)

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

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:92: void
HeapifyUp(size_t pos, T& element) {
On 2016/10/14 13:12:25, haraken wrote:
> 
> MoveElementUp ?


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

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:107: void
HeapifyDown(size_t pos, T& element) {
On 2016/10/14 13:12:26, haraken wrote:
> 
> MoveElementDown ?

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

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:130: // NB
this is a standard optimization, as used by the STL. HeapifyDown does
On 2016/10/14 13:12:25, haraken wrote:
> 
> NB => Note ?
> 
> BTW, we normally don't write "Note" for comments.

Done.

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.h
(right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/task_queue_impl.h:236:
base::TimeTicks time_domain_wakeup;
On 2016/10/14 07:26:16, Sami (OoO 0x1F1EF 0x1F1F5) wrote:
> It's a bit unclear what this is. |scheduled_time_domain_wakeup| maybe?

Done.

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/time_domain.cc (right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/time_domain.cc:48:
queue->set_heap_index(0u);
On 2016/10/14 07:26:16, Sami (OoO 0x1F1EF 0x1F1F5) wrote:
> Could we make 0u a named constant so 1-basedness of IntrusiveHeap doesn't leak
> out?

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

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/time_domain.cc:94:
delayed_wakeup_queue_.insert({delayed_run_time, queue});
On 2016/10/14 07:26:16, Sami (OoO 0x1F1EF 0x1F1F5) wrote:
> 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.

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.

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/time_domain.h (right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/time_domain.h:138: struct
HeapElement;
On 2016/10/14 07:26:16, Sami (OoO 0x1F1EF 0x1F1F5) wrote:
> Is there a more descriptive name for this? DelayedWakeup or something like
that?

Done.

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
(right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc:44: if
(heap_index == 0u)
On 2016/10/14 07:26:16, Sami (OoO 0x1F1EF 0x1F1F5) wrote:
> Ditto about using a constant.

Done.

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.h
(right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.h:69:
std::vector<IntrusiveHeap<HeapElement>> work_queue_heaps_;
On 2016/10/14 07:26:16, Sami (OoO 0x1F1EF 0x1F1F5) wrote:
> WDYT of:
> 
> using EnqueueOrderToWorkQueueHeap = IntrusiveHeap<HeapElement>;
> std::vector<EnqueueOrderToWorkQueueHeap> work_queue_heaps_;?
> 
> (I'm trying to make it more obvious to the casual reader what these data
> structures contain. Another name for HeapElement might be good too but I'm
> drawing a blank.)

Perhaps OldestTaskEnqueueOrder?  That is what we're sorting by.

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

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-14 13:56:04]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[alex clarke (OOO till 29th), 2016-10-14 14:05:19]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-14 14:05:30]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[alex clarke (OOO till 29th), 2016-10-14 14:07:51]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-14 14:08:04]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[alex clarke (OOO till 29th), 2016-10-14 14:14:17]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-14 14:14:24]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-14 14:48:19]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-14 14:48:20]

Dry run: Exceeded global retry quota

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

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h (right):

https://codereview.chromium.org/2419793002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:20: class
BLINK_PLATFORM_EXPORT IntrusiveHeap {
On 2016/10/14 13:12:25, haraken wrote:
> 
> You might want to add a couple of more DCHECKs (to HeapifyDown, HeapifyUp,
> MoveHoleDown etc) about the invariant that a binary heap must hold.

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

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

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-14 14:52:51]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-14 15:40:25]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-14 15:40:27]

Dry run: Try jobs failed on following builders:
  win_clang on master.tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_clang/builds/...)

[alex clarke (OOO till 29th), 2016-10-14 16:06:02]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-14 16:06:32]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[altimin, 2016-10-14 17:06:37]

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
File third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h (right):

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:18: // 2. T
has method void SetHeapIndex(size_t index)
3. T is moveable?
4. T is default-constructible? (it's not a very good thing to want).

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:18: // 2. T
has method void SetHeapIndex(size_t index)
I'd like to suggest using a callback, passed to constructor of InstrusiveHeap,
and invoke it when index changes.

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:38: void
pop() {
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.

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:40: size_t
top_index = size_--;
Do we want to shrink down the size of the underlying vector?

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:43:
MoveHoleDownAndFillWithLeafElement(1u, std::move(nodes_[top_index]));
Should we report to SetHeapIndex about element being deleted? Preferably, with
base:Optional<size_t>: SetHeapIndex(base::nullopt);

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:75: const
std::vector<T>& GetNodesForTesting() const { return nodes_; }
I believe that we can replace this method with:
1. Returning deleted elements.
2. Adding iterator to iterate over a container.

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:77: enum {
kInvalidIndex = 0u };
For my curiosity — what's the advantage of using enums (vs constexpr members)?

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
File third_party/WebKit/Source/platform/scheduler/base/time_domain.cc (right):

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/time_domain.cc:58:
queue->set_scheduled_time_domain_wakeup(base::TimeTicks());
(I feel like I'm becoming the evangelist of base::Optional)
I'd prefer to have base::Optional<TimeTicks> with explicit NULL option instead
of using default constructor for base::TimeTicks.

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
File third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
(right):

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc:34: if
(heap_index == IntrusiveHeap<OldestTaskEnqueueOrder>::kInvalidIndex)
I don't like exposing implementation detail (kInvalidIndex).
base::Optional<size_t> maybe?

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc:40:
work_queue_heaps_[set_index].GetNodesForTesting()[heap_index].value);
Here it should be possible to use return value of EraseHeapIndex instead of
using GetNodesForTesting.

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc:111: if
(heap.GetNodesForTesting()[i].value == work_queue) {
I believe that adding iteration support to public API covers this use case
instead of GetNodesForTesting.

[commit-bot: I haz the power, 2016-10-14 17:22:15]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-14 17:22:16]

Dry run: Try jobs failed on following builders:
  win_chromium_rel_ng on master.tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_rel_...)

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

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

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

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
File third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h (right):

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:18: // 2. T
has method void SetHeapIndex(size_t index)
On 2016/10/14 17:06:36, altimin wrote:
> 3. T is moveable?
> 4. T is default-constructible? (it's not a very good thing to want).
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.

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:18: // 2. T
has method void SetHeapIndex(size_t index)
On 2016/10/14 17:06:36, altimin wrote:
> I'd like to suggest using a callback, passed to constructor of InstrusiveHeap,
> and invoke it when index changes.

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

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:38: void
pop() {
On 2016/10/14 17:06:36, altimin wrote:
> 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.

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.

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:40: size_t
top_index = size_--;
On 2016/10/14 17:06:36, altimin wrote:
> Do we want to shrink down the size of the underlying vector?

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

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:43:
MoveHoleDownAndFillWithLeafElement(1u, std::move(nodes_[top_index]));
On 2016/10/14 17:06:35, altimin wrote:
> Should we report to SetHeapIndex about element being deleted?
We know when that happens already since we call erase or pop.

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:75: const
std::vector<T>& GetNodesForTesting() const { return nodes_; }
On 2016/10/14 17:06:36, altimin wrote:
> I believe that we can replace this method with:
> 1. Returning deleted elements.
I'd rather not.

> 2. Adding iterator to iterate over a container.
I have reservations about iterators since mutating the heap invalidates them
still I suppose its less ugly.

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.h:77: enum {
kInvalidIndex = 0u };
On 2016/10/14 17:06:35, altimin wrote:
> For my curiosity — what's the advantage of using enums (vs constexpr members)?

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

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

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
File third_party/WebKit/Source/platform/scheduler/base/time_domain.cc (right):

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/time_domain.cc:58:
queue->set_scheduled_time_domain_wakeup(base::TimeTicks());
On 2016/10/14 17:06:36, altimin wrote:
> (I feel like I'm becoming the evangelist of base::Optional)
> I'd prefer to have base::Optional<TimeTicks> with explicit NULL option instead
> of using default constructor for base::TimeTicks.

I don't dislike the idea of Optional (I used it quite a bit in java) but
TimeTicks has a well defined null value so I don't really see what it adds.

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
File third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc
(right):

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc:34: if
(heap_index == IntrusiveHeap<OldestTaskEnqueueOrder>::kInvalidIndex)
On 2016/10/14 17:06:36, altimin wrote:
> I don't like exposing implementation detail (kInvalidIndex).
Agreed.

> base::Optional<size_t> maybe?
Overkill ;O  We can add a HeapHandle class which has a IsValid method.

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc:40:
work_queue_heaps_[set_index].GetNodesForTesting()[heap_index].value);
On 2016/10/14 17:06:36, altimin wrote:
> Here it should be possible to use return value of EraseHeapIndex instead of
> using GetNodesForTesting.

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 :)

https://codereview.chromium.org/2419793002/diff/140001/third_party/WebKit/Sou...
third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc:111: if
(heap.GetNodesForTesting()[i].value == work_queue) {
On 2016/10/14 17:06:36, altimin wrote:
> I believe that adding iteration support to public API covers this use case
> instead of GetNodesForTesting.

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

[commit-bot: I haz the power, 2016-10-14 21:50:06]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-14 23:55:45]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-14 23:55:46]

Dry run: Try jobs failed on following builders:
  win_chromium_x64_rel_ng on master.tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_x64_...)

[haraken, 2016-10-15 01:58:14]

IntrusiveHeap LGTM

Maybe IntrusiveBinaryHeap or IndexedBinaryHeap sounds better (at first I thought
IntrusiveHeap is a kind of memory-allocator heap), but I don't have any strong
opinion.

[alex clarke (OOO till 29th), 2016-10-17 08:49:40]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-17 08:49:56]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[altimin, 2016-10-17 09:04:40]

lgtm

[alex clarke (OOO till 29th), 2016-10-17 10:16:49]

The CQ bit was unchecked by alexclarke@chromium.org

[alex clarke (OOO till 29th), 2016-10-17 10:16:54]

The CQ bit was checked by alexclarke@chromium.org

[commit-bot: I haz the power, 2016-10-17 10:17:10]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-17 10:23:32]

Committed patchset #11 (id:200001)

[commit-bot: I haz the power, 2016-10-17 10:25:36]

Description was changed from

==========
Optimize blink scheduler with an intrusive heap

BUG=
==========

to

==========
Optimize blink scheduler with an intrusive heap

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

[commit-bot: I haz the power, 2016-10-17 10:25:37]

Patchset 11 (id:??) landed as
https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}

[henrika (OOO until Aug 14), 2016-10-17 11:06:55]

A revert of this CL (patchset #11 id:200001) has been created in
https://codereview.chromium.org/2421283002/ by henrika@chromium.org.

The reason for reverting is: Seems to break blimp_browsertests

https://uberchromegw.corp.google.com/i/chromium.linux/builders/Blimp%20Linux%....

[henrika (OOO until Aug 14), 2016-10-17 12:47:24]

A revert of this CL (patchset #11 id:200001) has been created in
https://codereview.chromium.org/2424003002/ by henrika@chromium.org.

The reason for reverting is: Seems to break many tests on many platforms.

Example:

https://luci-logdog.appspot.com/v/?s=chromium%2Fbb%2Fchromium.win%2FWin7_Test....

[alex clarke (OOO till 29th), 2016-10-17 14:32:19]

Description was changed from

==========
Optimize blink scheduler with an intrusive heap

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

to

==========
Optimize blink scheduler with an intrusive heap

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

[alex clarke (OOO till 29th), 2016-10-17 15:01:32]

Looks like the problem was an off-by one bug with std::is_heap. According to the
docs it checks the range [first, last) but according to the assert it accessed
last...  That's not supposed to happen.

Anyway adjusting for that seems to fix it.

[alex clarke (OOO till 29th), 2016-10-17 15:45:12]

Patchset #12 (id:220001) has been deleted

[alex clarke (OOO till 29th), 2016-10-17 15:47:55]

On closer inspection, the bug was this: 

T* end() const {
  return &nodes_[size_ + 1];
}

std::vector didn't understand what we where trying to do and quite reasonably
asserted when size_+1 was past the end of the array.  I worked around this by
doing some pointer arithmetic.

[alex clarke (OOO till 29th), 2016-10-17 15:50:00]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[alex clarke (OOO till 29th), 2016-10-17 15:50:16]

PTAL

[commit-bot: I haz the power, 2016-10-17 15:50:16]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[alex clarke (OOO till 29th), 2016-10-17 15:50:31]

Description was changed from

==========
Optimize blink scheduler with an intrusive heap

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

to

==========
[Reland] Optimize blink scheduler with an intrusive heap

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

[haraken, 2016-10-17 15:52:42]

LGTM to reland

[commit-bot: I haz the power, 2016-10-17 17:33:11]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-17 17:33:12]

Dry run: This issue passed the CQ dry run.

[ojan, 2016-10-17 18:27:30]

ojan@chromium.org changed reviewers:
+ ojan@chromium.org

[ojan, 2016-10-17 18:27:31]

What did you use to measure performance impact? In the future, please include in
the change description what you measured and why it's faster (e.g. that it's
optimizing for small maps). 

I'm not questioning the value of this change. I just want it recorded what went
into making the decision so that someone looking at this change 3 years from now
and considering an alternative data structure can evaluate whether they are
regressing the motivation for this change.

A pointer to the discussions ruling out alternatives in the codereview comments
or in a bug that the change description linked to would be good too.

[alex clarke (OOO till 29th), 2016-10-18 09:03:01]

Description was changed from

==========
[Reland] Optimize blink scheduler with an intrusive heap

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

to

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

[alex clarke (OOO till 29th), 2016-10-18 09:13:16]

Description was changed from

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

to

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set 
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

[alex clarke (OOO till 29th), 2016-10-18 09:14:03]

The CQ bit was checked by alexclarke@chromium.org

[alex clarke (OOO till 29th), 2016-10-18 09:14:04]

The patchset sent to the CQ was uploaded after l-g-t-m from altimin@chromium.org
Link to the patchset: https://codereview.chromium.org/2419793002/#ps240001
(title: "The bug was in intrusiveHeap::end, now fixed")

[commit-bot: I haz the power, 2016-10-18 09:14:24]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[alex clarke (OOO till 29th), 2016-10-18 09:14:26]

Done.

[commit-bot: I haz the power, 2016-10-18 09:20:00]

Description was changed from

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set 
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

to

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set 
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

[commit-bot: I haz the power, 2016-10-18 09:20:01]

Committed patchset #12 (id:240001)

[commit-bot: I haz the power, 2016-10-18 09:21:58]

Description was changed from

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set 
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Cr-Commit-Position: refs/heads/master@{#425647}
==========

to

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Committed: https://crrev.com/1e13bd23dd2aac48f6bbcce65a1c56b14d5254ef
Cr-Original-Commit-Position: refs/heads/master@{#425647}
Cr-Commit-Position: refs/heads/master@{#425930}
==========

[commit-bot: I haz the power, 2016-10-18 09:21:59]

Patchset 12 (id:??) landed as
https://crrev.com/1e13bd23dd2aac48f6bbcce65a1c56b14d5254ef
Cr-Commit-Position: refs/heads/master@{#425930}

[ojan, 2016-10-18 16:42:40]

On 2016/10/18 at 09:14:26, alexclarke wrote:
> Done.

Oh nice. Somehow I misread this and thought the patch had already landed. \o/

[alex clarke (OOO till 29th), 2016-10-18 16:55:19]

A revert of this CL (patchset #12 id:240001) has been created in
https://codereview.chromium.org/2428073002/ by alexclarke@chromium.org.

The reason for reverting is: Looks like an assert is firing:
https://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium....

[alex clarke (OOO till 29th), 2016-10-19 09:23:13]

Description was changed from

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Committed: https://crrev.com/1e13bd23dd2aac48f6bbcce65a1c56b14d5254ef
Cr-Original-Commit-Position: refs/heads/master@{#425647}
Cr-Commit-Position: refs/heads/master@{#425930}
==========

to

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Committed: https://crrev.com/1e13bd23dd2aac48f6bbcce65a1c56b14d5254ef
Cr-Original-Commit-Position: refs/heads/master@{#425647}
Cr-Commit-Position: refs/heads/master@{#425930}
==========

[alex clarke (OOO till 29th), 2016-10-19 09:28:22]

On 2016/10/18 16:55:19, alex clarke wrote:
> A revert of this CL (patchset #12 id:240001) has been created in
> https://codereview.chromium.org/2428073002/ by mailto:alexclarke@chromium.org.
> 
> The reason for reverting is: Looks like an assert is firing:
>
https://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium....

I've found the bug that was causing the asserts. In TimeDomain
TimeDomain::MigrateQueue we were doing
this:

delayed_wakeup_queue_.erase(queue->heap_handle());          // Fine
queue->set_scheduled_time_domain_wakeup(base::TimeTicks()); // Also fine

destination_time_domain->ScheduleDelayedWork(
    queue, 
    queue->scheduled_time_domain_wakeup(),  // No that's not going to work,
since it's base::TimeTicks()
    destination_now);

The code then gets confused since queue->heap_handle() is valid but
queue->scheduled_time_domain_wakeup() isn't.

I've got a fix and will add some extra DCHECKS and test coverage to lock it in.

[alex clarke (OOO till 29th), 2016-10-19 15:42:35]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-19 15:42:54]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[alex clarke (OOO till 29th), 2016-10-19 16:41:08]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-19 16:41:44]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-19 18:26:11]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-19 18:26:12]

Dry run: This issue passed the CQ dry run.

[alex clarke (OOO till 29th), 2016-10-20 10:36:16]

The CQ bit was checked by alexclarke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-20 10:36:29]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-20 11:56:41]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-20 11:56:42]

Dry run: This issue passed the CQ dry run.

[alex clarke (OOO till 29th), 2016-10-20 12:34:12]

PTAL

[haraken, 2016-10-20 13:41:15]

LGTM

[alex clarke (OOO till 29th), 2016-10-20 13:42:09]

The CQ bit was checked by alexclarke@chromium.org

[alex clarke (OOO till 29th), 2016-10-20 13:42:09]

The patchset sent to the CQ was uploaded after l-g-t-m from altimin@chromium.org
Link to the patchset: https://codereview.chromium.org/2419793002/#ps300001
(title: "Fixed perf test and increaced test coverage")

[commit-bot: I haz the power, 2016-10-20 13:42:25]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-20 13:52:10]

Description was changed from

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Committed: https://crrev.com/1e13bd23dd2aac48f6bbcce65a1c56b14d5254ef
Cr-Original-Commit-Position: refs/heads/master@{#425647}
Cr-Commit-Position: refs/heads/master@{#425930}
==========

to

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Committed: https://crrev.com/1e13bd23dd2aac48f6bbcce65a1c56b14d5254ef
Cr-Original-Commit-Position: refs/heads/master@{#425647}
Cr-Commit-Position: refs/heads/master@{#425930}
==========

[commit-bot: I haz the power, 2016-10-20 13:52:13]

Committed patchset #15 (id:300001)

[commit-bot: I haz the power, 2016-10-21 13:17:59]

Description was changed from

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Committed: https://crrev.com/1e13bd23dd2aac48f6bbcce65a1c56b14d5254ef
Cr-Original-Commit-Position: refs/heads/master@{#425647}
Cr-Commit-Position: refs/heads/master@{#425930}
==========

to

==========
[Reland] Optimize blink scheduler with an intrusive heap.

This shows a ~10% improvement on the TaskQueueManagerPerfTest
micro benchmark.

Alternatives considered: A flat map/set
https://codereview.chromium.org/2396533004/

BUG=

Committed: https://crrev.com/36d98e3b544f310943986dcaa98beabacdbccc96
Committed: https://crrev.com/1e13bd23dd2aac48f6bbcce65a1c56b14d5254ef
Committed: https://crrev.com/efc263f7724823965b63cf2b7ff367288e526629
Cr-Original-Original-Commit-Position: refs/heads/master@{#425647}
Cr-Original-Commit-Position: refs/heads/master@{#425930}
Cr-Commit-Position: refs/heads/master@{#426467}
==========

[commit-bot: I haz the power, 2016-10-21 13:18:01]

Patchset 15 (id:??) landed as
https://crrev.com/efc263f7724823965b63cf2b7ff367288e526629
Cr-Commit-Position: refs/heads/master@{#426467}