Monday, 29 June 2009

Performance benchmark of CRC32, MD5 and SHA1 implementations in Ruby

Not long ago, I was experimenting with memcached from Ruby and I suddenly reached the maximum length of the key used to write to memcached, which is by default 250 chars.
However in my use case, I need to concatenate several requests params to create a unique key for my cached data.
So I fought of using some sort of hashing, unique to start with. Immediately thought of MD5. Found out it is available in the digest module so I used it.
Finally when I looked again at that code, I wondered if the MD5 was not actually too slow and counter productive in a caching mechanism. I could use SHA1 or even CRC32 as the collision risk is small and was not an issue in my instance.
So I ran the following ruby benchmark, to compare all implementations.

require 'benchmark'
require 'digest/md5'
require 'digest/sha1'
require 'zlib'

def b(n,s)
Benchmark.bm(7) do |x|
x.report("base:") { for i in 1..n; s; end }
x.report("crc32:") { for i in 1..n; Zlib.crc32(s); end }
x.report("md5:") { for i in 1..n; Digest::MD5.hexdigest(s); end }
x.report("sha1:") { for i in 1..n; Digest::SHA1.hexdigest(s); end }
end
end

And got the output for 100,000 iterations


irb(main):016:0> b(100000,Time.now.to_s)
user system total real
base: 0.020000 0.000000 0.020000 ( 0.018913)
crc32: 0.090000 0.010000 0.100000 ( 0.096223)
md5: 0.350000 0.000000 0.350000 ( 0.420743)
sha1: 0.390000 0.010000 0.400000 ( 0.421582)

Interestingly, SHA1 and MD5 implementations are similarly slow in comparison the CRC32.
CRC32 is roughly 4 times faster than SHA1 or MD5 but 5 times slower than no hashing.
Of course, the CRC32 algorithm has a risk of collision but if used with another attribute like a timestamp, it creates a key fairly unique and suitable for caching.

3 comments:

Anonymous said...

Um, you have MD5 reporting SHA1 results and SHA1 reporting MD5 results.

Romain said...

Corrected typo in label. Thanks 'Anonymous'. Results stand though :-)

Felix said...

using an actual file (81 KB), results look more sane:
ruby-1.9.2-head :025 > b(100000, File.read('import/import1/man-16353_1.jpg'))
user system total real
base: 0.000000 0.000000 0.000000 ( 0.006332)
crc32: 8.010000 0.010000 8.020000 ( 8.015790)
md5: 13.720000 0.030000 13.750000 ( 13.742495)
sha1: 21.820000 0.030000 21.850000 ( 21.846747)