Bug 87034 - treeScope() is too slow
Summary: treeScope() is too slow
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on: 59816 82681 89635 100057
Blocks: 97279
  Show dependency treegraph
 
Reported: 2012-05-21 11:32 PDT by Ryosuke Niwa
Modified: 2012-11-07 15:32 PST (History)
11 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Ryosuke Niwa 2012-05-21 11:32:41 PDT
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).
Comment 1 Eric Seidel (no email) 2012-05-21 11:57:32 PDT
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.
Comment 2 Hajime Morrita 2012-05-21 17:52:43 PDT
(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.
Comment 3 Ryosuke Niwa 2012-05-21 17:59:31 PDT
(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.
Comment 4 Dominic Cooney 2012-06-19 21:04:03 PDT
(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?
Comment 5 Ryosuke Niwa 2012-06-19 21:12:41 PDT
(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.
Comment 6 Elliott Sprehn 2012-11-07 15:32:03 PST
This was resolved by the removal of the rare data map in Bug 100057