Bug 74284

Summary: Bloom filter has unnecesary collisions
Product: WebKit Reporter: Allan Sandfeld Jensen <allan.jensen>
Component: CSSAssignee: Allan Sandfeld Jensen <allan.jensen>
Severity: Minor CC: kling, koivisto, macpherson, mjs, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Description Flags
Patch none

Description Allan Sandfeld Jensen 2011-12-12 04:01:06 PST
The bloom filter used to optimize tag, id and class selectors on ancestor has a minor inefficiency in that the value those three different types all use the same hash value in the bloom-filter.

This means that if a site uses a class or id-selector on something that is also a common tag name, it bloom-filter will produce unnecessary false positives and forcing the styler into slow path.

My proposed solution is to add a salt to the hash so that the different selectors only collide by random chance, not because they use common words.

This is an minor optimization only, not a functionality bug.
Comment 1 Allan Sandfeld Jensen 2011-12-12 04:02:20 PST
Created attachment 118772 [details]
Comment 2 Antti Koivisto 2011-12-12 07:43:16 PST
Comment on attachment 118772 [details]

View in context: https://bugs.webkit.org/attachment.cgi?id=118772&action=review

r=me, with a comment

> Source/WebCore/css/SelectorChecker.cpp:85
> +    identifierHashes.append(element->localName().impl()->existingHash() * TagNameSalt);

It might consider adding an inline function for computing hash type from AtomicString.
Comment 3 Antti Koivisto 2011-12-12 09:15:52 PST
Comment 4 WebKit Review Bot 2011-12-14 05:52:13 PST
Comment on attachment 118772 [details]

Clearing flags on attachment: 118772

Committed r102770: <http://trac.webkit.org/changeset/102770>
Comment 5 WebKit Review Bot 2011-12-14 05:52:18 PST
All reviewed patches have been landed.  Closing bug.