Use bloom filter for descendant selector filtering
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 6 Feb 2011 20:43:41 +0000 (20:43 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 6 Feb 2011 20:43:41 +0000 (20:43 +0000)
commit91fb2813665391ea131e05d647294833a5bcfe52
tree4a268dd4f72e81077930c03aeb46f694b9d8109e
parentd00c2c8ced03c0cbba35223a4647adf6a3991826
Use bloom filter for descendant selector filtering
https://bugs.webkit.org/show_bug.cgi?id=53880

Reviewed by Maciej Stachowiak.

Source/JavaScriptCore:

Implement a bloom filter with k=2 and 8 bit counting.

* GNUmakefile.am:
* JavaScriptCore.gypi:
* JavaScriptCore.vcproj/WTF/WTF.vcproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* wtf/BloomFilter.h: Added.
(WTF::BloomFilter::maximumCount):
(WTF::BloomFilter::BloomFilter):
(WTF::BloomFilter::mayContain):
(WTF::BloomFilter::add):
(WTF::BloomFilter::remove):
(WTF::BloomFilter::firstSlot):
(WTF::BloomFilter::secondSlot):
(WTF::::add):
(WTF::::remove):
(WTF::::clear):
(WTF::::likelyEmpty):
(WTF::::isClear):

Source/WebCore:

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

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

* ForwardingHeaders/wtf/BloomFilter.h: Added.
* css/CSSStyleSelector.cpp:
(WebCore::collectElementIdentifierHashes):
(WebCore::CSSStyleSelector::pushParent):
(WebCore::CSSStyleSelector::popParent):
(WebCore::CSSStyleSelector::fastRejectSelector):
(WebCore::RuleData::collectDescendantSelectorIdentifierHashes):
* css/CSSStyleSelector.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@77777 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/GNUmakefile.am
Source/JavaScriptCore/JavaScriptCore.gypi
Source/JavaScriptCore/JavaScriptCore.vcproj/WTF/WTF.vcproj
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/wtf/BloomFilter.h [new file with mode: 0644]
Source/WebCore/ChangeLog
Source/WebCore/ForwardingHeaders/wtf/BloomFilter.h [new file with mode: 0644]
Source/WebCore/css/CSSStyleSelector.cpp
Source/WebCore/css/CSSStyleSelector.h