Timeline for Counting Bloom Filter
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 11, 2015 at 2:12 | comment | added | JS1 | You're right, I was using a very large size (1 billion) to do my test. I added a new set of results for size = 4 million which should be a more reasonable sized test. | |
| May 10, 2015 at 23:15 | comment | added | maaartinus |
@JS1 Nice! The differences (with the memory access included) are surprisingly small; I believe to have seen bigger differences in Java (but it's too long ago and I may be wrong). IIRC the range of rand() in C is rather undefined - with a huge size, there'll be L3 misses which slow it down a lot. I guess, I've tested with a rather small filter.
|
|
| May 10, 2015 at 22:22 | comment | added | JS1 | See the addendum to my answer. I did the benchmarking in C but the results will probably carry over to Java. | |
| May 10, 2015 at 18:13 | comment | added | maaartinus | @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. | |
| May 10, 2015 at 17:57 | comment | added | JS1 | 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. | |
| May 10, 2015 at 12:42 | comment | added | maaartinus |
@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).
|
|
| May 10, 2015 at 5:27 | comment | added | JS1 |
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.
|
|
| May 10, 2015 at 3:42 | history | answered | maaartinus | CC BY-SA 3.0 |