Bug 87034 – treeScope() is too slow

• Status: RESOLVED
• Resolution: FIXED
• Component: DOM

[Ryosuke Niwa]

We spend roughly 8% of time in treeScope() while loading https://bugs.webkit.org/attachment.cgi?id=142634&action=review
because treeScope() uses rareData(), which uses HashMap lookup.

Not only that, this method appeared on almost every single profiling I did with DOM methods.
We need to make treeScope() O(1).

[Eric Seidel (no email)]

In general it would be very useful to know what pages use rareData, and what attributes/methods caused the creation of that rare data.  If we had some auditing system for htat, we could run it over hte layout tests, or more interesting run it over a bunch of pages from the wild.

[Hajime Morrita]

(In reply to comment #0)
> We spend roughly 8% of time in treeScope() while loading https://bugs.webkit.org/attachment.cgi?id=142634&action=review
> because treeScope() uses rareData(), which uses HashMap lookup.
> 
> Not only that, this method appeared on almost every single profiling I did with DOM methods.
> We need to make treeScope() O(1).

Just for clarification: You are saying that O(1) isn't enough, right?
Hashtable lookup is usually considered as O(1) operation.

My current thought is:
- We could replace Node::m_document with Node::m_treeScope. But it could introduce
  some type checking which can regress speed from other side.
- We could get rid of treeScope() usage from the host path.

treeScope() uses rareData() only if the node is in shadow tree,
it happens only with form controls and a few others for builtin element.
I wonder what triggers the actual table lookup.

[Ryosuke Niwa]

(In reply to comment #2)
> Just for clarification: You are saying that O(1) isn't enough, right?
> Hashtable lookup is usually considered as O(1) operation.

Any most of hash table implementations (including our own) do not exhibit O(1) time complexity. Only the ideal hash table has O(1) time complexity.

> My current thought is:
> - We could replace Node::m_document with Node::m_treeScope. But it could introduce
>   some type checking which can regress speed from other side.
> - We could get rid of treeScope() usage from the host path.

Either option sounds good to me. A radical alternative is to add m_rareNodeData to Node.

[Dominic Cooney]

(In reply to comment #2)
> - We could replace Node::m_document with Node::m_treeScope. But it could introduce
>   some type checking which can regress speed from other side.

Two questions:

First, does this constrain us to having detached subtrees in the document tree scope? Will that be acceptable semantically for callers of treeScope?

Second, if detached subtrees are still in the document tree scope, don’t we just have to do a null test (or maybe equality test), not a type test?

[Ryosuke Niwa]

(In reply to comment #4)
> (In reply to comment #2)
> > - We could replace Node::m_document with Node::m_treeScope. But it could introduce
> >   some type checking which can regress speed from other side.
> 
> Two questions:
> 
> First, does this constrain us to having detached subtrees in the document tree scope? Will that be acceptable semantically for callers of treeScope?

Yes. document() should never be null for almost all nodes.

> Second, if detached subtrees are still in the document tree scope, don’t we just have to do a null test (or maybe equality test), not a type test?

I don't get what you mean here.

[Elliott Sprehn]

This was resolved by the removal of the rare data map in Bug 100057