Make HTMLSlotElement.distributedNodeNextTo&distributedNodePreviousTo faster

Make HTMLSlotElement.distributedNodeNextTo & distributedNodePreviousTo faster

Currently distributedNodeNextTo & distributedNodePreviousTo are calculated using vector (O(N)). This CL makes this calculation O(1) by introducing a hashmap.
According to Performance Test, the calculation became 7.7% faster, in case of N=1000. (N being the number of distributed nodes)

With this CL:    avg 79094.69485003888 runs/s
Without this CL: avg 73466.4783609413  runs/s

BUG=531990
Committed: https://crrev.com/429b5ee96832287dd7c0747e6115227ac2447b31
Cr-Commit-Position: refs/heads/master@{#372632}

[yuzuchan, 2016-01-25 08:44:49]

Description was changed from

==========
Make HTMLSlotElement.distributedNodeNextTo/distributedNodePreviousTo faster
BUG=
==========

to

==========
Make HTMLSlotElement.distributedNodeNextTo & distributedNodePreviousTo faster

Currently distributedNodeNextTo & distributedNodePreviousTo are calculated using
vector (O(N)). This CL makes this calculation O(1) by introducing a hashmap.
According to Performance Test, the calculation became 7.7% faster, in case of
N=1000.

With this CL:    avg 79094.69485003888 runs/s
Without this CL: avg 73466.4783609413  runs/s

BUG=531990
==========

[yuzuchan, 2016-01-25 08:44:50]

yuzus@chromium.org changed reviewers:
+ hayato@chromium.org, kochi@chromium.org, kojii@chromium.org

[kochi, 2016-01-27 08:29:14]

At first glance I thought this can also be achieved
using WTF::DoublyLinkedList<T>, but noticed that type
T's  m_next/m_prev is used, which is already used
in Node class in another way.

Do you think this is better than reusing and unifying
dom/shadow/DistributedNodes.cpp class
which does very similar thing?

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/html/HTMLSlotElement.cpp (right):

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:95: for
(WillBeHeapHashMap<RawPtrWillBeMember<const Node>, size_t>::const_iterator it =
other.m_distributedIndices.begin(); it != other.m_distributedIndices.end();
++it) {
You can write "for (const auto& it = other.m_distributedIndices.begin; ...)".
Or even shorter, you can write "for (const auto& it :
other.m_distributedIndices) ..."
(in this case "it" becomes a reference of iterated object rather than
a pointer to iterated object, the next line will become it.key from
it->key).

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:96: const Node* node =
it.get()->key;
You can write "it->key".

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:98: index++;
You can write line97 as m_distributedIndices.set(node, index++);

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:111:
WillBeHeapHashMap<RawPtrWillBeMember<const Node>, size_t>::const_iterator it =
m_distributedIndices.find(&node);
You can write "const auto it = ...".

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:114: size_t index =
it.get()->value;
You can write "it->value".

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:122:
WillBeHeapHashMap<RawPtrWillBeMember<const Node>, size_t>::const_iterator it =
m_distributedIndices.find(&node);
You can write "const auto it = ...".

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:125: size_t index =
it.get()->value;
You can write "it->value".

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/html/HTMLSlotElement.h (left):

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.h:80: // TODO(hayato): Share
code with DistributedNode class
Does this CL really address this TODO?

[kochi, 2016-01-27 10:53:15]

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/html/HTMLSlotElement.h (left):

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.h:53: // TODO(hayato): This
takes O(N). Make it O(1) with node-to-index hash table.
You should remove this TODO.

[yuzuchan, 2016-02-01 05:40:42]

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/html/HTMLSlotElement.cpp (right):

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:95: for
(WillBeHeapHashMap<RawPtrWillBeMember<const Node>, size_t>::const_iterator it =
other.m_distributedIndices.begin(); it != other.m_distributedIndices.end();
++it) {
On 2016/01/27 08:29:13, kochi wrote:
> You can write "for (const auto& it = other.m_distributedIndices.begin; ...)".
> Or even shorter, you can write "for (const auto& it :
> other.m_distributedIndices) ..."
> (in this case "it" becomes a reference of iterated object rather than
> a pointer to iterated object, the next line will become it.key from
> it->key).

Done.

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:96: const Node* node =
it.get()->key;
On 2016/01/27 08:29:13, kochi wrote:
> You can write "it->key".

Done.

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:98: index++;
On 2016/01/27 08:29:13, kochi wrote:
> You can write line97 as m_distributedIndices.set(node, index++);

Done.

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:111:
WillBeHeapHashMap<RawPtrWillBeMember<const Node>, size_t>::const_iterator it =
m_distributedIndices.find(&node);
On 2016/01/27 08:29:13, kochi wrote:
> You can write "const auto it = ...".

Done.

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:114: size_t index =
it.get()->value;
On 2016/01/27 08:29:13, kochi wrote:
> You can write "it->value".

Done.

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:122:
WillBeHeapHashMap<RawPtrWillBeMember<const Node>, size_t>::const_iterator it =
m_distributedIndices.find(&node);
On 2016/01/27 08:29:13, kochi wrote:
> You can write "const auto it = ...".

Done.

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:125: size_t index =
it.get()->value;
On 2016/01/27 08:29:13, kochi wrote:
> You can write "it->value".

Done.

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/html/HTMLSlotElement.h (left):

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.h:53: // TODO(hayato): This
takes O(N). Make it O(1) with node-to-index hash table.
On 2016/01/27 10:53:15, kochi wrote:
> You should remove this TODO.

Done.

https://codereview.chromium.org/1611413005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.h:80: // TODO(hayato): Share
code with DistributedNode class
On 2016/01/27 08:29:14, kochi wrote:
> Does this CL really address this TODO?

I have decided to use a hash table here instead of sharing the code with
DistributedNode, since DistributedNode will be discarded anyway.

[kochi, 2016-02-01 06:12:15]

lgtm

https://codereview.chromium.org/1611413005/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/html/HTMLSlotElement.cpp (right):

https://codereview.chromium.org/1611413005/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/html/HTMLSlotElement.cpp:110: const auto& it =
m_distributedIndices.find(&node);
Yeah, 'const auto&' is better than 'const auto'.

[hayato, 2016-02-01 09:16:00]

lgtm

LGTM

> According to Performance Test, the calculation became 7.7% faster, in case of
N=1000.

Could you update the description? It looks N  = 100.
You might want to mention what N means here.

[yuzusan, 2016-02-01 09:20:46]

On 2016/02/01 09:16:00, hayato wrote:
> lgtm
> 
> LGTM
> 
> > According to Performance Test, the calculation became 7.7% faster, in case
of
> N=1000.
> 
> Could you update the description? It looks N  = 100.
> You might want to mention what N means here.

I tested when N=1000, and the result was as described in the description(7.7%
faster).
When N=100, performance with the CL was 7.3% faster.

[yuzusan, 2016-02-01 09:22:35]

Description was changed from

==========
Make HTMLSlotElement.distributedNodeNextTo & distributedNodePreviousTo faster

Currently distributedNodeNextTo & distributedNodePreviousTo are calculated using
vector (O(N)). This CL makes this calculation O(1) by introducing a hashmap.
According to Performance Test, the calculation became 7.7% faster, in case of
N=1000.

With this CL:    avg 79094.69485003888 runs/s
Without this CL: avg 73466.4783609413  runs/s

BUG=531990
==========

to

==========
Make HTMLSlotElement.distributedNodeNextTo & distributedNodePreviousTo faster

Currently distributedNodeNextTo & distributedNodePreviousTo are calculated using
vector (O(N)). This CL makes this calculation O(1) by introducing a hashmap.
According to Performance Test, the calculation became 7.7% faster, in case of
N=1000. (N being the number of distributed nodes)

With this CL:    avg 79094.69485003888 runs/s
Without this CL: avg 73466.4783609413  runs/s

BUG=531990
==========

[yuzusan, 2016-02-01 09:22:53]

The CQ bit was checked by yuzus@google.com

[commit-bot: I haz the power, 2016-02-01 09:23:38]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1611413005/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1611413005/60001

[commit-bot: I haz the power, 2016-02-01 10:22:37]

Description was changed from

==========
Make HTMLSlotElement.distributedNodeNextTo & distributedNodePreviousTo faster

Currently distributedNodeNextTo & distributedNodePreviousTo are calculated using
vector (O(N)). This CL makes this calculation O(1) by introducing a hashmap.
According to Performance Test, the calculation became 7.7% faster, in case of
N=1000. (N being the number of distributed nodes)

With this CL:    avg 79094.69485003888 runs/s
Without this CL: avg 73466.4783609413  runs/s

BUG=531990
==========

to

==========
Make HTMLSlotElement.distributedNodeNextTo & distributedNodePreviousTo faster

Currently distributedNodeNextTo & distributedNodePreviousTo are calculated using
vector (O(N)). This CL makes this calculation O(1) by introducing a hashmap.
According to Performance Test, the calculation became 7.7% faster, in case of
N=1000. (N being the number of distributed nodes)

With this CL:    avg 79094.69485003888 runs/s
Without this CL: avg 73466.4783609413  runs/s

BUG=531990
==========

[commit-bot: I haz the power, 2016-02-01 10:22:38]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2016-02-01 10:23:28]

Description was changed from

==========
Make HTMLSlotElement.distributedNodeNextTo & distributedNodePreviousTo faster

Currently distributedNodeNextTo & distributedNodePreviousTo are calculated using
vector (O(N)). This CL makes this calculation O(1) by introducing a hashmap.
According to Performance Test, the calculation became 7.7% faster, in case of
N=1000. (N being the number of distributed nodes)

With this CL:    avg 79094.69485003888 runs/s
Without this CL: avg 73466.4783609413  runs/s

BUG=531990
==========

to

==========
Make HTMLSlotElement.distributedNodeNextTo & distributedNodePreviousTo faster

Currently distributedNodeNextTo & distributedNodePreviousTo are calculated using
vector (O(N)). This CL makes this calculation O(1) by introducing a hashmap.
According to Performance Test, the calculation became 7.7% faster, in case of
N=1000. (N being the number of distributed nodes)

With this CL:    avg 79094.69485003888 runs/s
Without this CL: avg 73466.4783609413  runs/s

BUG=531990

Committed: https://crrev.com/429b5ee96832287dd7c0747e6115227ac2447b31
Cr-Commit-Position: refs/heads/master@{#372632}
==========

[commit-bot: I haz the power, 2016-02-01 10:23:28]

Patchset 4 (id:??) landed as
https://crrev.com/429b5ee96832287dd7c0747e6115227ac2447b31
Cr-Commit-Position: refs/heads/master@{#372632}