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

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

[hayato, 2014-02-27 07:05:35]

PTAL.

[hayato, 2014-02-27 08:43:30]

I have come up with yet another *nice* idea.

Now each TreeScopeEventContext has *pre-calculated* preVisit and postVisit. That
means we can defer actual calculation of adjusted event path until even.path is
actually called.
DOM mutation doesn't affect the result of event.path as long as we use such
numbers.

[hayato, 2014-02-27 08:51:14]

On 2014/02/27 08:43:30, hayato wrote:
> I have come up with yet another *nice* idea.
> 
> Now each TreeScopeEventContext has *pre-calculated* preVisit and postVisit.
That
> means we can defer actual calculation of adjusted event path until even.path
is
> actually called.
> DOM mutation doesn't affect the result of event.path as long as we use such
> numbers.

Let me update the patch tomorrow to implement this idea.

[hayato, 2014-02-27 09:29:56]

It's okay to review the patch set 1 if you are interested in, though I have to
handle SVG errors further.

I can implement yet another idea in another patch. The new idea doesn't have to
be in the same patch.

[esprehn, 2014-02-27 09:35:31]

Okay, I'll review all the ideas tomorrow! Thanks for the perf work.

To unsubscribe from this group and stop receiving emails from it, send an email
to blink-reviews+unsubscribe@chromium.org.

[hayato, 2014-03-01 05:27:51]

Let me clean up the patch next week. The latest uploaded patch has fixed svg
errors, but it seems to contain unexpected changes which were not mentioned in
the description.
When I upload the patch which is ready for reviews, I'll ping this thread.

[hayato, 2014-03-10 10:48:10]

The subject has changed. I've updated the patch so that the patch also include
lazy evaluation of event.path.

Could you review this?

[hayato, 2014-03-10 11:43:20]

I've updated the subject to reflect the patch's intention.

[dglazkov, 2014-03-10 16:34:53]

This is lovely. lgtm.

Elliott might want to do another check, though -- and possibly come up with a
better term for "number" :)

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/Event...
File Source/core/events/EventPath.cpp (right):

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/Event...
Source/core/events/EventPath.cpp:182: void
EventPath::numberTreeScopeEventContexts()
calculateTreeScopePositions? These are just suggestions. It seems like there's a
really good term for this "number" thing that's just out of my grasp.

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/TreeS...
File Source/core/events/TreeScopeEventContext.h (right):

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/TreeS...
Source/core/events/TreeScopeEventContext.h:69: int numberByDepthFirstSearch(int
number);
"number" is awkward here.

What's the right term for this number? Tree scope position?

[esprehn, 2014-03-11 01:23:11]

This is really clever.

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/Event...
File Source/core/events/EventPath.cpp (right):

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/Event...
Source/core/events/EventPath.cpp:202:
treeScopeEventContextMap.find(parent)->value->addChild(*treeScopeEventContext);
Why do you need the hash map? Aren't we traversing them in order?

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/TreeS...
File Source/core/events/TreeScopeEventContext.cpp (right):

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/TreeS...
Source/core/events/TreeScopeEventContext.cpp:78: for (size_t i = 0; i <
m_children.size(); ++i) {
extra braces

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/TreeS...
Source/core/events/TreeScopeEventContext.cpp:81: m_postVisit = number + 1;
Why do you need postVisit? Can't you just do lastChild()->number() + 1 ? I don't
think you need to store that.

[hayato, 2014-03-11 05:54:03]

Thank you for the reviews.
Let me update the patch, mainly just renaming, and land this.

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/Event...
File Source/core/events/EventPath.cpp (right):

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/Event...
Source/core/events/EventPath.cpp:182: void
EventPath::numberTreeScopeEventContexts()
On 2014/03/10 16:34:53, Dimitri Glazkov wrote:
> calculateTreeScopePositions? These are just suggestions. It seems like there's
a
> really good term for this "number" thing that's just out of my grasp.

To make it more explicit, I'd like to use "preorder number" and "postorder
number".

How about calculateTreeScopePreOrderAndPostOrderNumbers?

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/Event...
Source/core/events/EventPath.cpp:202:
treeScopeEventContextMap.find(parent)->value->addChild(*treeScopeEventContext);
On 2014/03/11 01:23:11, esprehn wrote:
> Why do you need the hash map? Aren't we traversing them in order?

We don't have any assumption about the order of m_treeScopeEventContexts here.

To traverse each treeScope in DFS order, we need:
1. Pointers from parent to its children because TreeScope doesn't have pointers
to its children in a tree of trees.
   We store such children list in TreeScopeEventContext.
   In *for* loop, each TreeScope has to ask the parent to add me to the parent's
children list. We need hashmap here to lookup TreeScopeEventContext by
TreeScope.

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/TreeS...
File Source/core/events/TreeScopeEventContext.cpp (right):

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/TreeS...
Source/core/events/TreeScopeEventContext.cpp:78: for (size_t i = 0; i <
m_children.size(); ++i) {
On 2014/03/11 01:23:11, esprehn wrote:
> extra braces

Done.

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/TreeS...
Source/core/events/TreeScopeEventContext.cpp:81: m_postVisit = number + 1;
On 2014/03/11 01:23:11, esprehn wrote:
> Why do you need postVisit? Can't you just do lastChild()->number() + 1 ? I
don't
> think you need to store that.

The reason is that the spec requires pre-calculation for event.path.
The event.path should not be affected by DOM mutations after event dispatching
starts.

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/TreeS...
File Source/core/events/TreeScopeEventContext.h (right):

https://codereview.chromium.org/182683002/diff/40001/Source/core/events/TreeS...
Source/core/events/TreeScopeEventContext.h:69: int numberByDepthFirstSearch(int
number);
On 2014/03/10 16:34:53, Dimitri Glazkov wrote:
> "number" is awkward here.
> 
> What's the right term for this number? Tree scope position?

Let me use more explicit name, pre-order number and post-order number.

[hayato, 2014-03-11 06:23:23]

The CQ bit was checked by hayato@chromium.org

[commit-bot: I haz the power, 2014-03-11 06:23:24]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/hayato@chromium.org/182683002/70001

[commit-bot: I haz the power, 2014-03-11 06:59:39]

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

[commit-bot: I haz the power, 2014-03-11 06:59:40]

Try jobs failed on following builders: linux_blink

[esprehn, 2014-03-11 07:52:28]

I meant m_children.last() not actual lastChild() so that shouldn't be
effected by dom mutation.

To unsubscribe from this group and stop receiving emails from it, send an email
to blink-reviews+unsubscribe@chromium.org.

[hayato, 2014-03-11 07:57:50]

On 2014/03/11 07:52:28, esprehn wrote:
> I meant m_children.last() not actual lastChild() so that shouldn't be
> effected by dom mutation.

m_children.last()->preOrderNumber() + 1 cannot replace post-order number That
can't be equivalent, I think.

[esprehn, 2014-03-11 08:11:36]

Yeah you're right, it'd be lastDeacendant() but that's a bit silly to
implement again down here.

Lgtm

On Tuesday, March 11, 2014, <hayato@chromium.org> wrote:

> On 2014/03/11 07:52:28, esprehn wrote:
>
>> I meant m_children.last() not actual lastChild() so that shouldn't be
>> effected by dom mutation.
>>
>
> m_children.last()->preOrderNumber() + 1 cannot replace post-order number
> That
> can't be equivalent, I think.
>
>
> https://codereview.chromium.org/182683002/
>
> To unsubscribe from this group and stop receiving emails from it, send an
> email to blink-reviews+unsubscribe@chromium.org.
>

To unsubscribe from this group and stop receiving emails from it, send an email
to blink-reviews+unsubscribe@chromium.org.

[esprehn, 2014-03-11 08:12:04]

lgtm

[hayato, 2014-03-11 08:18:14]

On 2014/03/11 08:11:36, esprehn wrote:
> Yeah you're right, it'd be lastDeacendant() but that's a bit silly to
> implement again down here.
> 

Oh, I understand. Here, memory constraint is not so severe. It might be okay to
prefer code simplicity to using lastDescendant().

[hayato, 2014-03-11 08:32:06]

The CQ bit was checked by hayato@chromium.org

[commit-bot: I haz the power, 2014-03-11 08:32:16]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/hayato@chromium.org/182683002/70001

[commit-bot: I haz the power, 2014-03-11 09:34:04]

Change committed as 168901

[Nils Barth (inactive), 2014-03-17 04:37:19]

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