Bug 21465 - Yet another querySelectorAll speedup
Summary: Yet another querySelectorAll speedup
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Mac OS X 10.5
: P2 Normal
Assignee: David Smith
Depends on:
Reported: 2008-10-08 02:33 PDT by David Smith
Modified: 2014-11-01 16:10 PDT (History)
1 user (show)

See Also:

The speedup (4.19 KB, patch)
2008-10-08 02:38 PDT, David Smith
no flags Details | Formatted Diff | Diff
Fixed (4.22 KB, patch)
2008-10-08 03:09 PDT, David Smith
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description David Smith 2008-10-08 02:33:48 PDT
We can generalize the id optimization still further by using non-rightmost id selectors to limit the subtree that qsa looks at.
Comment 1 David Smith 2008-10-08 02:38:20 PDT
Created attachment 24186 [details]
The speedup

I'm not real happy with the cleanliness of this code. Too many early returns, and the tempSelector == querySelector to avoid code duplication with the earlier id optimization is nasty.

That said, it works, passes tests, and speeds things up as expected.
Comment 2 David Smith 2008-10-08 03:09:44 PDT
Created attachment 24187 [details]

Oops, that was the wrong version of the patch. This one now has 100% more compiling successfully!
Comment 3 Darin Adler 2008-10-11 13:34:46 PDT
Comment on attachment 24187 [details]

+        for (CSSSelector* tempSelector = querySelector; !newRoot && tempSelector; tempSelector = tempSelector->m_tagHistory) {

I think the word "temp" in "tempSelector" is confusing here; there's nothing temporary about the selector. Maybe just "selector" would be a better name. Or maybe "idSelector", because that's what it is once we get past that first if statement in the loop.

+            if (tempSelector == querySelector && (rootNode->isDocumentNode() || newRoot->isDescendantOf(rootNode)) && selectorChecker.checkSelector(querySelector, newRoot)) {

What is the purpose of the "rootNode->isDocumentNode()" here? Can we just leave that out? Do we have a test case that would fail if we left it out?

Do we have a test suite that covers all the cases here? I know this patch doesn't change behavior, but I'm worried about whether there's enough coverage. I'd like to know that there's at least one case for each if statement and case in switch statement.

I'm going to say r=me, but I'd like to be reassured about test coverage.
Comment 4 David Smith 2008-10-13 07:06:04 PDT
I agree. I'll see if I can cook up some stress tests for it.

I don't recall why the isDocumentNode check is there; It was in the old check, so I left it in, but I'll try removing it and see if breaks anything. Doesn't seem like it should.
Comment 5 David Smith 2008-10-14 13:01:28 PDT
Comment on attachment 24187 [details]

Marking this obsolete to get it off the commit queue until I can add better tests.