bloom filters (was: concurrency suggestions for Gnus)

[Ted Zlatanov]

On Tue, 08 Feb 2011 13:31:39 +0900 Miles Bader <address@hidden> wrote: 

MB> Ted Zlatanov <address@hidden> writes:
Tom> If we went the "lock anything" route, I would suggest a weak hash table
Tom> for locks, instead of putting the lock into the object.
>> 
>> A bloom filter would guarantee no false negatives, which as you noted is
>> the vast majority of the cases, requires very little space per element

MB> A bloom filter...?!

(changing the subject accordingly)

Basically a fast membership query that uses pairwise independent hash
functions.  Runs in constant time, has no false negatives, and has a
false positive rate correlated to the number of bits per element.  It
would actually be a nice addition to the Emacs core to have a C
implementation.

Ted