7
\$\begingroup\$

I'm working on writing a Java class library which includes the following implementation of a counting bloom filter:

package sj224.lib.util;

import java.util.function.Predicate;
import java.util.Random;

public class BloomFilter<V> implements Predicate<V>{
    private final int size;
    private int count;
    private final int bpe;
    private final int[] data;
    public int hashCode(){
        long t=count;
        for(int i=0;i<size;i++){
            t+=(long)((data[i]%2)*Math.pow(2, i%64));
        }
        return new Random(t).nextInt();
    }
    public String toString(){
        return size+"-bit Bloom Filter containing "+count+" elements (hash code "+hashCode()+")";
    }
    public BloomFilter(int space){
        data=new int[space];
        size=space;
        bpe=Math.max(3, Math.min(size/8,(int)Math.sqrt(size)));
        count=0;
    }
    public int size(){
        return count;
    }
    private int[] hash(V v){
        Random r=new Random(v.hashCode());
        int[] keys=new int[size];
        for(int i=0;i<bpe;i++){
            keys[r.nextInt(size)]=1;
        }
        return keys;
    }
    public BloomFilter(){
        this(64);
    }
    public BloomFilter(Iterable<V> source){
        this(64);
        for(V i:source)insert(i);
    }
    public boolean remove(V v){
        int[] a=hash(v);
        for(int i=0;i<size;i++){
            if(data[i]<a[i])return false;
        }
        for(int i=0;i<size;i++){
            data[i]-=a[i];
        }
        count--;
        return true;
    }
    public void clear(){
        for(int i=0;i<size;i++)data[i]=0;
    }
    public void insert(V v){
        int[] a=hash(v);
        for(int i=0;i<size;i++){
            data[i]+=a[i];
        }
        count++;
    }
    public boolean contains(V v){
        int[] a=hash(v);
        for(int i=0;i<size;i++){
            if(data[i]<a[i])return false;
        }
        return true;
    }

    public boolean test(V v){
        return contains(v);
    }
}

Is there anything here that can reasonably be improved?

\$\endgroup\$
4
\$\begingroup\$

Typo

This probably happened when you cut and pasted your code, but your contains function had a few lines switched in their ordering.

Operations taking O(size) time, could be faster

Your add, remove, and contains operations all do approximately the same thing. They create a hash where the hash contains up to bpe bits set in an array of size bits. Then they iterate over the size bits.

The important thing here is that bpe is much smaller than size. For any size larger than 64, bpe will be sqrt(size). Since only bpe bits are set, you only need to take O(bpe) time instead of O(size) time.

Operations using 32x the required space

Also, when you create your array of bits, you use one int per bit even though you only ever set the int to 1 or 0. If size is very large, such as 100 million, you could be using 400 MB when you only need to be using 12.5 MB.

Putting it all together

I rewrote your functions, and also combined all of their functionality into the hashing function since all 3 functions were so similar. In the new code, the loops only run through bpe iterations instead of size iterations. I also packed the bits to minimize the space used.

/**
 * Performs one of three operations: add, remove, or contains.
 *
 * @param        v                The element to add/remove/test.
 * @param        operation        1 = add, -1 = remove, 0 = contains
 * @return                        If operation is "contains", returns true
 *                                if v is contained in the bloom filter, and
 *                                false if it is not.  If operation is
 *                                anything else, returns true.
 */
private boolean hashOperation(V v, int operation)
{
    Random r         = new Random(v.hashCode());
    int[]  bitsFound = new int[(size+31)/32];

    for(int i=0;i<bpe;i++){
        int bitNum   = r.nextInt(size);
        int bitIndex = bitNum >> 5;
        int bit      = (1 << (bitNum & 31));
        if ((bitsFound[bitIndex] & bit) == 0) {
            // New bit.  Perform operation.
            bitsFound[bitIndex] |= bit;
            if (operation == 0) {
                if(data[bitNum] == 0)
                    return false;
            } else {
                data[bitNum] += operation;
            }
        }
    }
    return true;
}

public boolean remove(V v)
{
    if (contains(v)) {
        hashOperation(v, -1);
        count--;
        return true;
    }
    return false;
}

public void insert(V v)
{
    hashOperation(v, 1);
    count++;
}

public boolean contains(V v)
{
    return hashOperation(v, 0);
}

Addendum: Testing the fastest way to hash using maaartinus's method

Maaartinus showed a fast way to hash using just 2 hash functions. I decided to test out 4 variants:

  1. Using a power of 2 size (should be fastest)
  2. Using modulus operator every loop (should be slowest)
  3. Using a compare + subtract
  4. Doing the subtract without using any compare

Note, the following is all done in C:

Variant 1

All variants use the following setup. The thing that varies will be in the loop:

uint32_t hash, hash1, hash2, size;

size  = rand();
hash1 = rand() % size;
hash2 = rand() % size;

hash = hash1;
uint32_t sizeMask = 0x3fffffff;  // Variant 1 only
for (i=0;i<iterations;i++) {
    hash = (hash + hash2) & (sizeMask);
}

Variant 2

for (i=0;i<iterations;i++) {
    hash = (hash + hash2) % size;
}

Variant 3

// If size is < 0x80000000
for (i=0;i<iterations;i++) {
    hash += hash2;
    if (hash > size)
        hash -= size;
}

// This works for all cases (and has the same runtime as the one above)
for (i=0;i<iterations;i++) {
    if (size - hash > hash2)
        hash += hash2;
    else
        hash -= (size - hash2);
}

Variant 4

// In C, >> is not guaranteed to do an arithmetic shift, so
// we use a logical shift instead.  The compiler optimizes this code
// to do an arithmetic shift anyways.  In java, change the ">>" here
// to a ">>>".
for (i=0;i<iterations;i++) {
    hash += hash2;
    hash -= (-((size - hash) >> 31)) & size;
}

// In java, where >> is arithmetic shift, you could write it like this.
for (i=0;i<iterations;i++) {
    hash += hash2;
    hash -= ((size - hash) >> 31) & size;
}

Timing results

Running each variant for 1 billion iterations (results in seconds):

Variant 1 (& power of 2): 0.58
Variant 2 (% size)      : 6.56
Variant 3 (if, subtract): 1.25
Variant 4 (no if)       : 1.44

However, this is a bit misleading because there was nothing in the loop except for the hash calculation. If I add in the part where we use the hash on each loop:

    bits[hash>>5] |= (1 << (hash & 31));

Then the timings all become much closer:

Size = 1 billion
Variant 1 (& power of 2): 15.92
Variant 2 (% size)      : 18.92
Variant 3 (if, subtract): 17.48
Variant 4 (no if)       : 16.76

Size = 4 million
Variant 1 (& power of 2): 2.48
Variant 2 (% size)      : 7.11
Variant 3 (if, subtract): 2.58
Variant 4 (no if)       : 2.52

Size = 256K
Variant 1 (& power of 2): 1.24
Variant 2 (% size)      : 6.64
Variant 3 (if, subtract): 1.79
Variant 4 (no if)       : 1.95

So it appears that at large sizes, the memory manipulation of the bit array will be the limiting factor and not the hash calculation. So you can choose from the above 4 variants based on:

  1. Whether you can force the size to be a power of 2 or not.
  2. How much you need that extra bit of speed versus how clear/simple you want your code to be.
\$\endgroup\$
  • \$\begingroup\$ I decided to modify it so, instead of generating the entire temporary array, the hash method just generates an array of size bpe the indices at which the 1s would be located; and theinsert, contains and remove methods have been modified accordingly. \$\endgroup\$ – SuperJedi224 May 9 '15 at 12:22
  • \$\begingroup\$ Does it matter to you if there are duplicates in that array? If not, that is a good approach. I wrote my solution under the assumption that you only ever wanted to add maximum 1 to each bloom filter data slot per item inserted. \$\endgroup\$ – JS1 May 9 '15 at 16:03
  • \$\begingroup\$ Darn, I forgot about that. \$\endgroup\$ – SuperJedi224 May 9 '15 at 16:06
  • \$\begingroup\$ And there doesn't seem to be a practical way to fix that that doesn't completely offset the time savings, so I changed it back. \$\endgroup\$ – SuperJedi224 May 9 '15 at 16:18
  • \$\begingroup\$ Alright, I decided to go with most of your original suggestion. \$\endgroup\$ – SuperJedi224 May 10 '15 at 12:03
3
\$\begingroup\$

I posted a question earlier asking for suggestions for improving the hash method specifically

OK, let's concentrate on it.

private int[] hash(V v){
    Random r=new Random(v.hashCode());
    int[] keys=new int[size];
    for(int i=0;i<bpe;i++){
        keys[r.nextInt(size)]=1;
    }
    return keys;
}

There's no real magic in Random. You want some good and fast mixing and what you get is not that useful.

I'd suggest to stick with a size being a power of two, so you can avoid the slow modulus operation (hidden in Random#nextInt(int)).

According to this paper, it's not necessary to generate n independent values. Instead, it suffices to get two independent hash functions and obtain the \$i\$-th value using this trivial formula

$$g_i(x) = h_1(x) + i \cdot h_2(x)$$

You could use the (up to) 16 lower bits of the hashCode for \$h_1\$ and the remaining ones for \$h_2\$. However, I'd suggest to shake and stir the hashCode before use. In case you need more bits, you're out of luck (with or without my proposal) as there's not enough information there. IMHO there are chances that the bloom filter will work rather well despite this.

\$\endgroup\$
  • \$\begingroup\$ I like the hash function, but if you make the size a power of 2 it will weaken the hash because you will only be using some of the bits of the hash. You can use an arbitrary size and only use two modulos: one on h1(x) and one on h2(x). Let h2m = h2(x) % size; Then on every iteration you add h2m to the previous hash and subtract size if the new hash exceeds size. \$\endgroup\$ – JS1 May 10 '15 at 5:27
  • \$\begingroup\$ @JS1 It won't weaken the hash when you do some mixing on it. Sometimes, (a*x) >>> n will suffice and it's way faster than modulus. +++ "subtract size if the new hash exceeds size" - but this is a hard to predict conditional jump, which may be slower than modulus (Guava, which is pretty heavily optimized, does not use it). \$\endgroup\$ – maaartinus May 10 '15 at 12:42
  • \$\begingroup\$ Point taken. You've now gotten me curious as to what is the fastest way to do this kind of hash with an arbitrary size (power of 2 size is of course fastest as you said). I'm going to try 3 different methods and see which is fastest. I'll post my results later on. \$\endgroup\$ – JS1 May 10 '15 at 17:57
  • \$\begingroup\$ @JS1 Are you aware about all the gotchas of Java benchmarking? Especially inline caching (start a new JVM for every run), warmup (let it run for at least one second and then start a measurement taking at least one second), dead code elimination (make sure all your results get used somehow), and others? I'd suggest to use JMH or Caliper, as they've solved it all. \$\endgroup\$ – maaartinus May 10 '15 at 18:13
  • \$\begingroup\$ See the addendum to my answer. I did the benchmarking in C but the results will probably carry over to Java. \$\endgroup\$ – JS1 May 10 '15 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.