3 ms·

Bloom Filter (Python recipe)

46 points by jcsalterego 15y ago

haberman 15y ago
One thing that takes a minute to sink with Bloom Filters is that the size requirements are independent of the size of the individual elements! Storing N elements with a given false positive probability has a fixed cost, whether you're storing integers or 100MB strings. If you are concerned with speed, a bloom filter is exactly the kind of thing I'd never implement in Python. Twiddling bits is orders of magnitude more expensive than in C.
- raymondh 15y ago
  Python is written in C and the time consuming parts of this algorithm are delegated to C modules (random, sha256, long int bitshifts, etc). Also, the space efficiency (which directly related to effective use of high-speed cache) is language independent. If you care about the cost of the Python glue code, the PyPy project nicely optimizes that away. Unless you're writing for a Google production server, the programmer time writing this in C will likely never be paid back in saved CPU cycles.
  - haberman 15y ago
    What you have said is theory. Here is practice. I wrote a simple bloom filter in C. It took about an hour, including debugging. Here is my bloom filter vs. CPython and PyPy doing 1M lookups: $ time ./bloom real 0m0.027s user 0m0.022s sys 0m0.002s $ time python bloom.py real 0m32.876s user 0m32.693s sys 0m0.119s $ time pypy bloom.py real 0m42.280s user 0m42.054s sys 0m0.178s In other words, C was 1216x (or 121,600%) faster than CPython, and 1564x (or 156,400%) faster than PyPy. If it took 1 second in C, it would take 20 minutes in Python. Put another way, Python runs this algorithm about as fast as a the C algorithm would run on an 8086 from 1978. Here is my C implementation: http://pastebin.com/TexbJjbB http://pastebin.com/TexbJjbB Here is the Python program I compared against (using code from the article): http://pastebin.com/gqw7C68e http://pastebin.com/gqw7C68e
    - raymondh 15y ago
      Not an apples-to-apples comparison. The Python version is fully general, using Random() to create probes (as many as needed). Instead use the optimized, 4Kb fixed size version shown later in the recipe. Also, improve your timing by making the loop in a function and using something other than range(1000000) to fill-up memory (like timeit does). The C version should also use sha224 for comparability (otherwise, you're basically comparing two different hash functions in two different languages meaning that some of the difference can be ascribed to the choice of hash algorithm). That being said, you've done a great job showing that it doesn't take long to correctly implement this algorithm in C. That is a nice win.
      - haberman 15y ago
        > Not an apples-to-apples comparison. These kinds of arguments make sense if you're 20% different, or 2x different, or even 10x different. When you're 1000x different, no amount of minor tweaking is going to bridge the gap. Using the 4k version and using timeit() instead of range(), the speed is 21 seconds instead of 32 seconds, so it did speed up, but it's still 800x slower. I'm pretty sure that only a tiny fraction of Python's time is calculating sha224, so I don't think that making them use the same hash function is necessary. Look, Python is cool and has it's place. But it's annoying to get downvoted for stating the obvious: algorithms like this will be much, much faster in C. It's annoying to hear people insist that dropping to C is a waste of time when my personal experience shows time and time again that it can lead to drastic improvements.

46 points by jcsalterego 15y ago

One thing that takes a minute to sink with Bloom Filters is that the size requirements are independent of the size of the individual elements! Storing N elements with a given false positive probability has a fixed cost, whether you're storing integers or 100MB strings. If you are concerned with speed, a bloom filter is exactly the kind of thing I'd never implement in Python. Twiddling bits is orders of magnitude more expensive than in C.

raymondh 15y ago
Python is written in C and the time consuming parts of this algorithm are delegated to C modules (random, sha256, long int bitshifts, etc). Also, the space efficiency (which directly related to effective use of high-speed cache) is language independent. If you care about the cost of the Python glue code, the PyPy project nicely optimizes that away. Unless you're writing for a Google production server, the programmer time writing this in C will likely never be paid back in saved CPU cycles.
- haberman 15y ago
  What you have said is theory. Here is practice. I wrote a simple bloom filter in C. It took about an hour, including debugging. Here is my bloom filter vs. CPython and PyPy doing 1M lookups: $ time ./bloom real 0m0.027s user 0m0.022s sys 0m0.002s $ time python bloom.py real 0m32.876s user 0m32.693s sys 0m0.119s $ time pypy bloom.py real 0m42.280s user 0m42.054s sys 0m0.178s In other words, C was 1216x (or 121,600%) faster than CPython, and 1564x (or 156,400%) faster than PyPy. If it took 1 second in C, it would take 20 minutes in Python. Put another way, Python runs this algorithm about as fast as a the C algorithm would run on an 8086 from 1978. Here is my C implementation: http://pastebin.com/TexbJjbB http://pastebin.com/TexbJjbB Here is the Python program I compared against (using code from the article): http://pastebin.com/gqw7C68e http://pastebin.com/gqw7C68e
  - raymondh 15y ago
    Not an apples-to-apples comparison. The Python version is fully general, using Random() to create probes (as many as needed). Instead use the optimized, 4Kb fixed size version shown later in the recipe. Also, improve your timing by making the loop in a function and using something other than range(1000000) to fill-up memory (like timeit does). The C version should also use sha224 for comparability (otherwise, you're basically comparing two different hash functions in two different languages meaning that some of the difference can be ascribed to the choice of hash algorithm). That being said, you've done a great job showing that it doesn't take long to correctly implement this algorithm in C. That is a nice win.
    - haberman 15y ago
      > Not an apples-to-apples comparison. These kinds of arguments make sense if you're 20% different, or 2x different, or even 10x different. When you're 1000x different, no amount of minor tweaking is going to bridge the gap. Using the 4k version and using timeit() instead of range(), the speed is 21 seconds instead of 32 seconds, so it did speed up, but it's still 800x slower. I'm pretty sure that only a tiny fraction of Python's time is calculating sha224, so I don't think that making them use the same hash function is necessary. Look, Python is cool and has it's place. But it's annoying to get downvoted for stating the obvious: algorithms like this will be much, much faster in C. It's annoying to hear people insist that dropping to C is a waste of time when my personal experience shows time and time again that it can lead to drastic improvements.