Bug 138549 - Remove BloomFilter size limit
Summary: Remove BloomFilter size limit
Status: NEW
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-11-09 14:50 PST by Antti Koivisto
Modified: 2014-11-10 08:59 PST (History)
4 users (show)

See Also:


Attachments
patch (1.15 KB, patch)
2014-11-09 14:53 PST, Antti Koivisto
kling: 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 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