4 ms·

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.

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.

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.