Chromium Code Reviews
Help | Chromium Project | Gerrit Changes | Sign in
(27)

Issue 182683002: Lazy evaluation of event.path by numbering TreeScopes in DFS order for later O(1) queries (Closed)

Created:
3 years, 9 months ago by hayato
Modified:
3 years, 8 months ago
Reviewers:
esprehn, dglazkov
CC:
blink-reviews
Visibility:
Public.

Description

In event path calculation, it's expected that we'd have a lot of queries to check if given two tree scopes in the tree of trees are in ancestor/descendant relationships. In the current implementation (TreeScope::isOlderSiblingOrInclusiveAncestor), this query takes O(N), where N is the height of the tree of trees. That causes the entire calculation of event.path for each node, on which even.path would be possibly called, to take O(MN^2). (M: The number of the nodes in event path, N: The number of the involved TreeScopes) That's the reason why event dispatching doesn't scale well once the height of tree of trees becomes too high. Pre-calculating event.path for each node would dominate event dispatching time. To reduce the order of computational cost, I've implemented O(1) query algorithm, instead of the current O(N) query time algorithm. The algorithm is: 1. Pre-process each TreeScope by depth-first-search and make them have numbers of 'preVisit' and 'postVisit'. Pre-processing takes O(N) in time and needs additional O(N) space. That shouldn't matter in this case. 2. By using these numbers, we can answer the query of isInclusiveAncestorOf() in O(1) by checking the range of numbers as follows: preVisit <= other.preVist && other.postVisit <= postVisit Furthermore, we get an additional, but very significant bonus by this data structures which are used in O(1) algorithm. Now we can delay the actual calculation of event.path for each nodes. We can calculate event.path *on demand* because we can answer the query of ancestor-descendant relationships only by checking these pre-visit and post-visit numbers. The structure of tree of trees at the beginning of the event dispatching would be *preserved* with these numbers. This is a huge win from the view of the performance of event dispatching. The following are the results of the benchmarks for event dispatching. The height of node trees in each benchmark is about 50. The major difference is the height of the tree of trees. 1. Events/EventsDispatching.html (The number of involved treeScope is small.) - Without this CL: 581.9 runs/s - With this CL: 697.2 runs/s (1.2 times faster) 2. Events/EventsDispatchingInShadowTrees.html (The number of involved treeScope is about 10) - Without this CL: 5105.9 runs/s - With this CL: 12448.1 runs/s (2.4 times faster) 3. Events/EventsDispatchingInDeeplyNestedShadowTrees.html (This is a new test and extreme case. The number of involved treeScope is about 200. That means event.path contains about 10000 (= 50 * 200) nodes) - Without this CL: 1.64 runs/s - With this CL: 708.75 runs/s (432 times faster. Now event dispatching can scale well in shadow trees) The relevant specs are: - http://w3c.github.io/webcomponents/spec/shadow/#event-paths - http://w3c.github.io/webcomponents/spec/shadow/#widl-Event-path BUG=345200 TEST=No behavior changes Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=168901

Patch Set 1 #

Patch Set 2 : Fix svg errors #

Patch Set 3 : Implement lazy evaluation #

Total comments: 10

Patch Set 4 : More explicit naming, pre-order and post-order. #

Patch Set 5 : One more renaming #

Messages

Total messages: 24 (0 generated)
hayato
PTAL.
3 years, 9 months ago (2014-02-27 07:05:35 UTC) #1
hayato
I have come up with yet another *nice* idea. Now each TreeScopeEventContext has *pre-calculated* preVisit ...
3 years, 9 months ago (2014-02-27 08:43:30 UTC) #2
hayato
On 2014/02/27 08:43:30, hayato wrote: > I have come up with yet another *nice* idea. ...
3 years, 9 months ago (2014-02-27 08:51:14 UTC) #3
hayato
It's okay to review the patch set 1 if you are interested in, though I ...
3 years, 9 months ago (2014-02-27 09:29:56 UTC) #4
esprehn
Okay, I'll review all the ideas tomorrow! Thanks for the perf work. To unsubscribe from ...
3 years, 9 months ago (2014-02-27 09:35:31 UTC) #5
hayato
Let me clean up the patch next week. The latest uploaded patch has fixed svg ...
3 years, 8 months ago (2014-03-01 05:27:51 UTC) #6
hayato
The subject has changed. I've updated the patch so that the patch also include lazy ...
3 years, 8 months ago (2014-03-10 10:48:10 UTC) #7
hayato
I've updated the subject to reflect the patch's intention.
3 years, 8 months ago (2014-03-10 11:43:20 UTC) #8
dglazkov
This is lovely. lgtm. Elliott might want to do another check, though -- and possibly ...
3 years, 8 months ago (2014-03-10 16:34:53 UTC) #9
esprehn
This is really clever. https://codereview.chromium.org/182683002/diff/40001/Source/core/events/EventPath.cpp File Source/core/events/EventPath.cpp (right): https://codereview.chromium.org/182683002/diff/40001/Source/core/events/EventPath.cpp#newcode202 Source/core/events/EventPath.cpp:202: treeScopeEventContextMap.find(parent)->value->addChild(*treeScopeEventContext); Why do you need ...
3 years, 8 months ago (2014-03-11 01:23:11 UTC) #10
hayato
Thank you for the reviews. Let me update the patch, mainly just renaming, and land ...
3 years, 8 months ago (2014-03-11 05:54:03 UTC) #11
hayato
The CQ bit was checked by hayato@chromium.org
3 years, 8 months ago (2014-03-11 06:23:23 UTC) #12
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/hayato@chromium.org/182683002/70001
3 years, 8 months ago (2014-03-11 06:23:24 UTC) #13
commit-bot: I haz the power
The CQ bit was unchecked by commit-bot@chromium.org
3 years, 8 months ago (2014-03-11 06:59:39 UTC) #14
commit-bot: I haz the power
Try jobs failed on following builders: linux_blink
3 years, 8 months ago (2014-03-11 06:59:40 UTC) #15
esprehn
I meant m_children.last() not actual lastChild() so that shouldn't be effected by dom mutation. To ...
3 years, 8 months ago (2014-03-11 07:52:28 UTC) #16
hayato
On 2014/03/11 07:52:28, esprehn wrote: > I meant m_children.last() not actual lastChild() so that shouldn't ...
3 years, 8 months ago (2014-03-11 07:57:50 UTC) #17
esprehn
Yeah you're right, it'd be lastDeacendant() but that's a bit silly to implement again down ...
3 years, 8 months ago (2014-03-11 08:11:36 UTC) #18
esprehn
lgtm
3 years, 8 months ago (2014-03-11 08:12:04 UTC) #19
hayato
On 2014/03/11 08:11:36, esprehn wrote: > Yeah you're right, it'd be lastDeacendant() but that's a ...
3 years, 8 months ago (2014-03-11 08:18:14 UTC) #20
hayato
The CQ bit was checked by hayato@chromium.org
3 years, 8 months ago (2014-03-11 08:32:06 UTC) #21
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/hayato@chromium.org/182683002/70001
3 years, 8 months ago (2014-03-11 08:32:16 UTC) #22
commit-bot: I haz the power
Change committed as 168901
3 years, 8 months ago (2014-03-11 09:34:04 UTC) #23
Nils Barth (inactive)
3 years, 8 months ago (2014-03-17 04:37:19 UTC) #24
Message was sent while issue was closed.
On 2014/03/11 01:23:11, esprehn wrote:
> This is really clever.

This is very clever - great job Hayato!
(Is this a well-known algorithm? ...or your own cleverness?)

For what it's worth, here are some references.

The algorithm is known (by some) as "Dietz's numbering scheme", and is
apparently due to
Paul Dietz, "Maintaining order in a linked list" (1982), which states:

For two given nodes x and y of a tree T, x is an ancestor of y if and only if
x occurs before y in the preorder traversal of T and after y in the post-order
traversal.

This shows up in XML indexing (e.g., XISS):
http://www.cs.arizona.edu/xiss/numbering.htm

...and there are various variants, due to this needing O(n) work updating the
numbers if
nodes are inserted (ok to not update on deletion).

Stack overflow reference:
Check if 2 tree nodes are related (ancestor/descendant) in O(1) with
pre-processing
http://stackoverflow.com/questions/10310809/check-if-2-tree-nodes-are-related...

Powered by Google App Engine
This is Rietveld efc10ee0f