Make appendChild/insertBefore faster with active ranges

Make appendChild/insertBefore faster with active Range objects

This patch makes |Node#appendChild()| and |Node#insertBefore()| faster when
there are active Range objects in document.

Before this path, we iterate over all active |Range| objects to make there
cached offset invalid for each |appendChild()| and |insertBefore()|.

From this patch, we use both DOM tree version and invalid value of
|m_offsetInContainer| as invalid offset marker to avoid iterating over
all active |Range| objects. This makes execution of speed of |appendChild()| and
|insertBefore()| independent from number of active |Range| objects.

On my Linux box, "append-child-with-ranges.html" (with 100 |Range| objects)
results are:

w/patch:
avg 13.4ms, median 14 ms, min 10ms, max 21ms

w/o patch:
avg 42.1ms, median 42ms, min 38ms, max 49ms

Note: This patch is inspired by esphren@'s comments regarding to crbug/613658
and based on kouhei@'s great idea and strong push.

BUG=n/a
TEST=PerformanceTests/Mutation/append-child-with-ranges.html

Committed: https://crrev.com/023a90124852ea2ceab04d4a5662e1dcb5caba68
Cr-Commit-Position: refs/heads/master@{#397987}

[yosin_UTC9, 2016-06-03 10:01:42]

Description was changed from

==========
2016-06-03T18:48:37

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

to

==========
Make appendChild/insertBefore faster with active Range objects

This patch makes |Node#appendChild()| and |Node#insertBefore()| faster when
there are active Range objects in document.

Before this path, we iterate over all active |Range| objects to make there
cached offset invalid for each |appendChild()| and |insertBefore()|.

From this patch, we use both DOM tree version and invalid value of
|m_offsetInContainer| as invalid offset marker to avoid iterating over
all active |Range| objects. This makes execution of speed of |appendChild()| and
|insertBefore()| independent from number of active |Range| objects.

On my Linux box, "append-child-with-ranges.html" (with 100 |Range| objects)
results are:

w/patch:
avg 13.4ms, median 14 ms, min 10ms, max 21ms

w/o patch:
avg 42.1ms, median 42ms, min 38ms, max 49ms


Note: This patch is inspired by esphren@'s comments regarding to crbug/613658
and based on kouhei@'s great idea and strong push.

BUG=n/a
TEST=PerformanceTests/Mutation/append-child-with-ranges.html
==========

[yosin_UTC9, 2016-06-03 10:01:43]

yosin@chromium.org changed reviewers:
+ haraken@chromium.org, keishi@chromium.org, kouhei@chromium.org

[kouhei (in TOK), 2016-06-04 05:00:36]

lgtm % nits

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/dom/RangeBoundaryPoint.h (right):

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/dom/RangeBoundaryPoint.h:141:
const_cast<RangeBoundaryPoint*>(this)->ensureOffsetIsValid();
this const_cast shouldn't be needed

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/dom/RangeBoundaryPoint.h:149:
const_cast<RangeBoundaryPoint*>(this)->ensureOffsetIsValid();
ditto

[keishi, 2016-06-04 07:02:45]

LGTM

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Performa...
File third_party/WebKit/PerformanceTests/Mutation/append-child-with-ranges.html
(right):

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Performa...
third_party/WebKit/PerformanceTests/Mutation/append-child-with-ranges.html:2:
<!-- Identical to "append-child.html" but having 10,000 active ranges -->
Shouldn't this test be based on PerformanceTests/Bindings/append-child.html ? We
don't need the MutationObserver.

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/dom/ContainerNode.cpp (right):

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/dom/ContainerNode.cpp:778: && change.type !=
TextChanged
nit: would the code be easier to understand if it listed the positive matches?

[yosin_UTC9, 2016-06-06 05:21:26]

The CQ bit was checked by yosin@chromium.org

[yosin_UTC9, 2016-06-06 05:21:27]

Thanks for review!
I updated CL as review comments.
Committing...

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Performa...
File third_party/WebKit/PerformanceTests/Mutation/append-child-with-ranges.html
(right):

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Performa...
third_party/WebKit/PerformanceTests/Mutation/append-child-with-ranges.html:2:
<!-- Identical to "append-child.html" but having 10,000 active ranges -->
On 2016/06/04 at 07:02:45, keishi wrote:
> Shouldn't this test be based on PerformanceTests/Bindings/append-child.html ?
We don't need the MutationObserver.

Done

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/dom/ContainerNode.cpp (right):

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/dom/ContainerNode.cpp:778: && change.type !=
TextChanged
On 2016/06/04 at 07:02:45, keishi wrote:
> nit: would the code be easier to understand if it listed the positive matches?

Done.

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/dom/RangeBoundaryPoint.h (right):

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/dom/RangeBoundaryPoint.h:141:
const_cast<RangeBoundaryPoint*>(this)->ensureOffsetIsValid();
On 2016/06/04 at 05:00:36, kouhei (catching up) wrote:
> this const_cast shouldn't be needed

Done

https://codereview.chromium.org/2034023003/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/dom/RangeBoundaryPoint.h:149:
const_cast<RangeBoundaryPoint*>(this)->ensureOffsetIsValid();
On 2016/06/04 at 05:00:36, kouhei (catching up) wrote:
> ditto

Done

[yosin_UTC9, 2016-06-06 05:21:27]

The patchset sent to the CQ was uploaded after l-g-t-m from keishi@chromium.org,
kouhei@chromium.org
Link to the patchset: https://codereview.chromium.org/2034023003/#ps20001
(title: "2016-06-06T14:17:03 Adopt for review comments")

[commit-bot: I haz the power, 2016-06-06 05:21:34]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2034023003/20001

[commit-bot: I haz the power, 2016-06-06 06:48:41]

Committed patchset #2 (id:20001)

[commit-bot: I haz the power, 2016-06-06 06:50:27]

Description was changed from

==========
Make appendChild/insertBefore faster with active Range objects

This patch makes |Node#appendChild()| and |Node#insertBefore()| faster when
there are active Range objects in document.

Before this path, we iterate over all active |Range| objects to make there
cached offset invalid for each |appendChild()| and |insertBefore()|.

From this patch, we use both DOM tree version and invalid value of
|m_offsetInContainer| as invalid offset marker to avoid iterating over
all active |Range| objects. This makes execution of speed of |appendChild()| and
|insertBefore()| independent from number of active |Range| objects.

On my Linux box, "append-child-with-ranges.html" (with 100 |Range| objects)
results are:

w/patch:
avg 13.4ms, median 14 ms, min 10ms, max 21ms

w/o patch:
avg 42.1ms, median 42ms, min 38ms, max 49ms


Note: This patch is inspired by esphren@'s comments regarding to crbug/613658
and based on kouhei@'s great idea and strong push.

BUG=n/a
TEST=PerformanceTests/Mutation/append-child-with-ranges.html
==========

to

==========
Make appendChild/insertBefore faster with active Range objects

This patch makes |Node#appendChild()| and |Node#insertBefore()| faster when
there are active Range objects in document.

Before this path, we iterate over all active |Range| objects to make there
cached offset invalid for each |appendChild()| and |insertBefore()|.

From this patch, we use both DOM tree version and invalid value of
|m_offsetInContainer| as invalid offset marker to avoid iterating over
all active |Range| objects. This makes execution of speed of |appendChild()| and
|insertBefore()| independent from number of active |Range| objects.

On my Linux box, "append-child-with-ranges.html" (with 100 |Range| objects)
results are:

w/patch:
avg 13.4ms, median 14 ms, min 10ms, max 21ms

w/o patch:
avg 42.1ms, median 42ms, min 38ms, max 49ms

Note: This patch is inspired by esphren@'s comments regarding to crbug/613658
and based on kouhei@'s great idea and strong push.

BUG=n/a
TEST=PerformanceTests/Mutation/append-child-with-ranges.html

Committed: https://crrev.com/023a90124852ea2ceab04d4a5662e1dcb5caba68
Cr-Commit-Position: refs/heads/master@{#397987}
==========

[commit-bot: I haz the power, 2016-06-06 06:50:28]

Patchset 2 (id:??) landed as
https://crrev.com/023a90124852ea2ceab04d4a5662e1dcb5caba68
Cr-Commit-Position: refs/heads/master@{#397987}