Bug 74284 – Bloom filter has unnecesary collisions

• Component: CSS
• Status: RESOLVED FIXED

[Allan Sandfeld Jensen]

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.

[Allan Sandfeld Jensen]

Created attachment 118772 [details]
Patch

[Antti Koivisto]

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.

[Antti Koivisto]

s/It/You/

[WebKit Review Bot]

Comment on attachment 118772 [details]
Patch

Clearing flags on attachment: 118772

Committed r102770: <http://trac.webkit.org/changeset/102770>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.