Bug 53880 – Use bloom filter for descendant selector filtering

• Component: CSS
• Status: RESOLVED FIXED

[Antti Koivisto]

Bloom filter is faster than a hash set in this kind of use.

[Antti Koivisto]

Created attachment 81415 [details]
implement a bloom filter and use it for selector filtering

Shark thinks this speeds up style matching by ~30% on sites with lots of descendant selectors.

[WebKit Review Bot]

Attachment 81415 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/7701641

[Early Warning System Bot]

Attachment 81415 [details] did not build on qt:
Build output: http://queues.webkit.org/results/7708114

[Antti Koivisto]

Created attachment 81416 [details]
attempted build fixes for various build systems

[WebKit Review Bot]

Attachment 81415 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/7699787

[Maciej Stachowiak]

Comment on attachment 81416 [details]
attempted build fixes for various build systems

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

r=me with one minor comment

> Source/JavaScriptCore/wtf/BloomFilter.h:77
> +    char m_table[tableSize];

I'd suggest using "unsigned char" or uint8_t for this, since it's using char as a byte, not a character, and this avoids pain on platforms where char is signed by default.

[Dimitri Glazkov (Google)]

(In reply to comment #6)
> (From update of attachment 81416 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=81416&action=review
> 
> r=me with one minor comment
> 
> > Source/JavaScriptCore/wtf/BloomFilter.h:77
> > +    char m_table[tableSize];
> 
> I'd suggest using "unsigned char" or uint8_t for this, since it's using char as a byte, not a character, and this avoids pain on platforms where char is signed by default.

Pls don't land as is -- breaks Chromium.

[Dimitri Glazkov (Google)]

(In reply to comment #7)
> (In reply to comment #6)
> > (From update of attachment 81416 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=81416&action=review
> > 
> > r=me with one minor comment
> > 
> > > Source/JavaScriptCore/wtf/BloomFilter.h:77
> > > +    char m_table[tableSize];
> > 
> > I'd suggest using "unsigned char" or uint8_t for this, since it's using char as a byte, not a character, and this avoids pain on platforms where char is signed by default.
> 
> Pls don't land as is -- breaks Chromium.

Nevermind -- haven't seen the second patch :)

[Antti Koivisto]

http://trac.webkit.org/changeset/77777 (!!!!1)

[Dimitri Glazkov (Google)]

(In reply to comment #9)
> http://trac.webkit.org/changeset/77777 (!!!!1)

!!!!!

[Antti Koivisto]

I think I just won the webkit.

[WebKit Review Bot]

http://trac.webkit.org/changeset/77777 might have broken Qt Linux Release