Bug 74284 - Bloom filter has unnecesary collisions
Summary: Bloom filter has unnecesary collisions
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: CSS (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Minor
Assignee: Allan Sandfeld Jensen
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2011-12-12 04:01 PST by Allan Sandfeld Jensen
Modified: 2011-12-14 05:52 PST (History)
5 users (show)

See Also:


Attachments
Patch (4.28 KB, patch)
2011-12-12 04:02 PST, Allan Sandfeld Jensen
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
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]
Patch
Comment 2 Antti Koivisto 2011-12-12 07:43:16 PST
Comment on attachment 118772 [details]
Patch

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
s/It/You/
Comment 4 WebKit Review Bot 2011-12-14 05:52:13 PST
Comment on attachment 118772 [details]
Patch

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.