Bug 21465

Summary: Yet another querySelectorAll speedup
Product: WebKit Reporter: David Smith <catfish.man>
Component: DOMAssignee: David Smith <catfish.man>
Severity: Normal CC: benjamin
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Mac   
OS: OS X 10.5   
Description Flags
The speedup
Fixed none

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.