Bug 138549

Summary: Remove BloomFilter size limit
Product: WebKit Reporter: Antti Koivisto <koivisto>
Component: Web Template FrameworkAssignee: Nobody <webkit-unassigned>
Status: NEW ---    
Severity: Normal CC: benjamin, cdumez, cmarcelo, commit-queue
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
patch kling: review+

Description Antti Koivisto 2014-11-09 14:50:47 PST
It works fine with sizes greater than 2^16.
Comment 1 Antti Koivisto 2014-11-09 14:53:46 PST
Created attachment 241261 [details]
patch
Comment 2 Chris Dumez 2014-11-09 15:18:46 PST
Comment on attachment 241261 [details]
patch

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

> Source/WTF/wtf/BloomFilter.h:-40
> -    static_assert(keyBits <= 16, "BloomFilter key size must be less than or equal to 16!");

Shouldn't we make sure it is at least <= 32 so that 1 << keyBits below doesn't overflow?

I have looked carefully at the implementation but was this 16 value somehow corrected to the 16 value used in secondSlot() below?
Comment 3 Chris Dumez 2014-11-09 15:26:40 PST
(In reply to comment #2)
> Comment on attachment 241261 [details]
> patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=241261&action=review
> 
> > Source/WTF/wtf/BloomFilter.h:-40
> > -    static_assert(keyBits <= 16, "BloomFilter key size must be less than or equal to 16!");
> 
> Shouldn't we make sure it is at least <= 32 so that 1 << keyBits below
> doesn't overflow?
> 
> I have looked carefully at the implementation but was this 16 value somehow
> corrected to the 16 value used in secondSlot() below?

typo: s/corrected/connected
Comment 4 Antti Koivisto 2014-11-09 15:38:20 PST
I just removed the assert as it is unlikely anyone would try to create anything close to a 4GB filter.

I think we get sensible slot spread without any code changes. It is not entirely symmetric anymore, first slot uses the entire table while second is the lowest 2^16 slots. However there are only 16 unique bits per slot in the key anyway.
Comment 5 Andreas Kling 2014-11-10 08:59:16 PST
Comment on attachment 241261 [details]
patch

Sure, r=me