bitly/dablooms — pull request #41 by suranap (2012-08-16 19:38:04+00:00)
Title: Faster hash_func. No need for salts.

The performance bottleneck is in calling the hash function repeatedly. The solution is to call it less frequently. This paper (http://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf) says you can replace the expensive calls to a hash function with the equation: gi(x) = h1(x) + i * h2(x). Both h1 and h2 are generated by one call to the hash function. Then you just loop around that equation to generate all the hash values you need for the bloom filter. In my limited testing, performance improves about 20%.