Bug 53880 - Use bloom filter for descendant selector filtering
Summary: Use bloom filter for descendant selector filtering
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: CSS (show other bugs)
Version: 528+ (Nightly build)
Hardware: PC OS X 10.5
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2011-02-06 10:14 PST by Antti Koivisto
Modified: 2011-02-06 14:29 PST (History)
16 users (show)

See Also:


Attachments
implement a bloom filter and use it for selector filtering (17.17 KB, patch)
2011-02-06 10:44 PST, Antti Koivisto
no flags Details | Formatted Diff | Diff
attempted build fixes for various build systems (18.80 KB, patch)
2011-02-06 11:18 PST, Antti Koivisto
mjs: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Antti Koivisto 2011-02-06 10:14:57 PST
Bloom filter is faster than a hash set in this kind of use.
Comment 1 Antti Koivisto 2011-02-06 10:44:46 PST
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.
Comment 2 WebKit Review Bot 2011-02-06 10:58:50 PST
Attachment 81415 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/7701641
Comment 3 Early Warning System Bot 2011-02-06 10:59:29 PST
Attachment 81415 [details] did not build on qt:
Build output: http://queues.webkit.org/results/7708114
Comment 4 Antti Koivisto 2011-02-06 11:18:10 PST
Created attachment 81416 [details]
attempted build fixes for various build systems
Comment 5 WebKit Review Bot 2011-02-06 11:29:15 PST
Attachment 81415 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/7699787
Comment 6 Maciej Stachowiak 2011-02-06 12:07:30 PST
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.
Comment 7 Dimitri Glazkov (Google) 2011-02-06 12:11:27 PST
(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.
Comment 8 Dimitri Glazkov (Google) 2011-02-06 12:12:01 PST
(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 :)
Comment 9 Antti Koivisto 2011-02-06 12:46:50 PST
http://trac.webkit.org/changeset/77777 (!!!!1)
Comment 10 Dimitri Glazkov (Google) 2011-02-06 13:22:50 PST
(In reply to comment #9)
> http://trac.webkit.org/changeset/77777 (!!!!1)

!!!!!
Comment 11 Antti Koivisto 2011-02-06 13:41:09 PST
I think I just won the webkit.
Comment 12 WebKit Review Bot 2011-02-06 14:29:09 PST
http://trac.webkit.org/changeset/77777 might have broken Qt Linux Release