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: http://svn.webkit.org/repository/webkit/trunk@77777
268f45cc-cd09-0410-ab3c-
d52691b4dbfc