Bug 53880 - Use bloom filter for descendant selector filtering
: Use bloom filter for descendant selector filtering
Status: RESOLVED FIXED
: WebKit
CSS
: 528+ (Nightly build)
: PC Mac OS X 10.5
: P2 Normal
Assigned To:
:
:
:
:
  Show dependency treegraph
 
Reported: 2011-02-06 10:14 PST by
Modified: 2011-02-06 14:29 PST (History)


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 Review Patch | 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+
Review Patch | Details | Formatted Diff | Diff


Note

You need to log in before you can comment on or make changes to this bug.


Description From 2011-02-06 10:14:57 PST
Bloom filter is faster than a hash set in this kind of use.
------- Comment #1 From 2011-02-06 10:44:46 PST -------
Created an attachment (id=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 From 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 From 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 From 2011-02-06 11:18:10 PST -------
Created an attachment (id=81416) [details]
attempted build fixes for various build systems
------- Comment #5 From 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 From 2011-02-06 12:07:30 PST -------
(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.
------- Comment #7 From 2011-02-06 12:11:27 PST -------
(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.
------- Comment #8 From 2011-02-06 12:12:01 PST -------
(In reply to comment #7)
> (In reply to comment #6)
> > (From update of attachment 81416 [details] [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 From 2011-02-06 12:46:50 PST -------
http://trac.webkit.org/changeset/77777 (!!!!1)
------- Comment #10 From 2011-02-06 13:22:50 PST -------
(In reply to comment #9)
> http://trac.webkit.org/changeset/77777 (!!!!1)

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