develooper Front page | perl.perl5.porters | Postings from October 2012

benchmarking Murmurhash3 vs One-At-A-Time as perls hash function

From:
demerphq
Date:
October 31, 2012 02:30
Subject:
benchmarking Murmurhash3 vs One-At-A-Time as perls hash function
Message ID:
CANgJU+XVHMcH1m0PHFCEqy3Vgmi-wPVjxiDtuN-NVx1+Afq7nQ@mail.gmail.com
Existing Perls use one-at-a-time hashing.

My hash improvements patch/branch includes an implementation of Murmur Hash 3.

http://code.google.com/p/smhasher/wiki/MurmurHash3

The following is timings of various hash operations with keys of
different lengths with the two algorithms.

Conclusion: on my laptop Murmurhash3 is more than 3 times faster at
hashing longer strings than one-at-a-time, and roughly the same for
shorter strings.

Benchmark attached.

Yves

One at a time:
$ time ./perl -Ilib hash_benchmark.pl
* Length = 1
timethis 500:  4 wallclock secs ( 3.30 usr +  0.00 sys =  3.30 CPU) @
151.52/s (n=500)
* Length = 2
timethis 500:  6 wallclock secs ( 5.86 usr +  0.00 sys =  5.86 CPU) @
85.32/s (n=500)
* Length = 3
timethis 500:  6 wallclock secs ( 6.17 usr +  0.00 sys =  6.17 CPU) @
81.04/s (n=500)
* Length = 4
timethis 500:  6 wallclock secs ( 6.16 usr +  0.00 sys =  6.16 CPU) @
81.17/s (n=500)
* Length = 5
timethis 500:  6 wallclock secs ( 6.20 usr +  0.00 sys =  6.20 CPU) @
80.65/s (n=500)
* Length = 6
timethis 500:  7 wallclock secs ( 6.29 usr +  0.00 sys =  6.29 CPU) @
79.49/s (n=500)
* Length = 7
timethis 500:  6 wallclock secs ( 6.47 usr +  0.00 sys =  6.47 CPU) @
77.28/s (n=500)
* Length = 8
timethis 500:  7 wallclock secs ( 6.65 usr +  0.01 sys =  6.66 CPU) @
75.08/s (n=500)
* Length = 9
timethis 500:  7 wallclock secs ( 6.81 usr +  0.00 sys =  6.81 CPU) @
73.42/s (n=500)
* Length = 10
timethis 500:  7 wallclock secs ( 6.84 usr +  0.00 sys =  6.84 CPU) @
73.10/s (n=500)
* Length = 16
timethis 500:  7 wallclock secs ( 7.48 usr +  0.01 sys =  7.49 CPU) @
66.76/s (n=500)
* Length = 21
timethis 500:  8 wallclock secs ( 8.03 usr +  0.00 sys =  8.03 CPU) @
62.27/s (n=500)
* Length = 24
timethis 500:  8 wallclock secs ( 8.24 usr +  0.00 sys =  8.24 CPU) @
60.68/s (n=500)
* Length = 25
timethis 500:  9 wallclock secs ( 8.44 usr +  0.00 sys =  8.44 CPU) @
59.24/s (n=500)
* Length = 32
timethis 500:  9 wallclock secs ( 9.05 usr +  0.00 sys =  9.05 CPU) @
55.25/s (n=500)
* Length = 34
timethis 500:  9 wallclock secs ( 9.15 usr +  0.00 sys =  9.15 CPU) @
54.64/s (n=500)
* Length = 63
timethis 500: 12 wallclock secs (12.01 usr +  0.00 sys = 12.01 CPU) @
41.63/s (n=500)
* Length = 100
timethis 500: 16 wallclock secs (15.86 usr +  0.00 sys = 15.86 CPU) @
31.53/s (n=500)
* Length = 110
timethis 500: 17 wallclock secs (16.74 usr +  0.00 sys = 16.74 CPU) @
29.87/s (n=500)
* Length = 128
timethis 500: 19 wallclock secs (18.68 usr +  0.00 sys = 18.68 CPU) @
26.77/s (n=500)
* Length = 200
timethis 500: 26 wallclock secs (25.79 usr +  0.00 sys = 25.79 CPU) @
19.39/s (n=500)
* Length = 250
timethis 500: 30 wallclock secs (30.76 usr +  0.00 sys = 30.76 CPU) @
16.25/s (n=500)
* Length = 256
timethis 500: 31 wallclock secs (31.44 usr +  0.00 sys = 31.44 CPU) @
15.90/s (n=500)
* Length = 500
timethis 500: 56 wallclock secs (55.82 usr +  0.00 sys = 55.82 CPU) @
8.96/s (n=500)
* Length = 512
timethis 500: 57 wallclock secs (57.04 usr +  0.01 sys = 57.05 CPU) @
8.76/s (n=500)
* Length = 1000
timethis 500: 105 wallclock secs (104.70 usr +  0.08 sys = 104.78 CPU)
@  4.77/s (n=500)
* Length = 1024
timethis 500: 108 wallclock secs (107.79 usr +  0.04 sys = 107.83 CPU)
@  4.64/s (n=500)

real	10m19.313s
user	10m17.483s
sys	0m0.248s

Murmur hash (v3):
$ time ./perl -Ilib hash_benchmark.pl
* Length = 1
timethis 500:  3 wallclock secs ( 3.28 usr +  0.00 sys =  3.28 CPU) @
152.44/s (n=500)
* Length = 2
timethis 500:  6 wallclock secs ( 5.98 usr +  0.00 sys =  5.98 CPU) @
83.61/s (n=500)
* Length = 3
timethis 500:  6 wallclock secs ( 5.93 usr +  0.00 sys =  5.93 CPU) @
84.32/s (n=500)
* Length = 4
timethis 500:  6 wallclock secs ( 5.82 usr +  0.00 sys =  5.82 CPU) @
85.91/s (n=500)
* Length = 5
timethis 500:  6 wallclock secs ( 6.00 usr +  0.00 sys =  6.00 CPU) @
83.33/s (n=500)
* Length = 6
timethis 500:  6 wallclock secs ( 6.02 usr +  0.00 sys =  6.02 CPU) @
83.06/s (n=500)
* Length = 7
timethis 500:  6 wallclock secs ( 6.06 usr +  0.00 sys =  6.06 CPU) @
82.51/s (n=500)
* Length = 8
timethis 500:  6 wallclock secs ( 6.01 usr +  0.00 sys =  6.01 CPU) @
83.19/s (n=500)
* Length = 9
timethis 500:  7 wallclock secs ( 6.71 usr +  0.00 sys =  6.71 CPU) @
74.52/s (n=500)
* Length = 10
timethis 500:  7 wallclock secs ( 6.47 usr +  0.00 sys =  6.47 CPU) @
77.28/s (n=500)
* Length = 16
timethis 500:  6 wallclock secs ( 6.16 usr +  0.00 sys =  6.16 CPU) @
81.17/s (n=500)
* Length = 21
timethis 500:  6 wallclock secs ( 6.46 usr +  0.00 sys =  6.46 CPU) @
77.40/s (n=500)
* Length = 24
timethis 500:  7 wallclock secs ( 6.36 usr +  0.00 sys =  6.36 CPU) @
78.62/s (n=500)
* Length = 25
timethis 500:  6 wallclock secs ( 6.53 usr +  0.00 sys =  6.53 CPU) @
76.57/s (n=500)
* Length = 32
timethis 500:  7 wallclock secs ( 6.58 usr +  0.00 sys =  6.58 CPU) @
75.99/s (n=500)
* Length = 34
timethis 500:  7 wallclock secs ( 6.61 usr +  0.00 sys =  6.61 CPU) @
75.64/s (n=500)
* Length = 63
timethis 500:  7 wallclock secs ( 7.63 usr +  0.00 sys =  7.63 CPU) @
65.53/s (n=500)
* Length = 100
timethis 500:  9 wallclock secs ( 8.73 usr +  0.00 sys =  8.73 CPU) @
57.27/s (n=500)
* Length = 110
timethis 500:  9 wallclock secs ( 9.06 usr +  0.00 sys =  9.06 CPU) @
55.19/s (n=500)
* Length = 128
timethis 500: 10 wallclock secs ( 9.58 usr +  0.00 sys =  9.58 CPU) @
52.19/s (n=500)
* Length = 200
timethis 500: 12 wallclock secs (11.70 usr +  0.00 sys = 11.70 CPU) @
42.74/s (n=500)
* Length = 250
timethis 500: 13 wallclock secs (13.33 usr +  0.00 sys = 13.33 CPU) @
37.51/s (n=500)
* Length = 256
timethis 500: 13 wallclock secs (13.40 usr +  0.00 sys = 13.40 CPU) @
37.31/s (n=500)
* Length = 500
timethis 500: 21 wallclock secs (20.75 usr +  0.00 sys = 20.75 CPU) @
24.10/s (n=500)
* Length = 512
timethis 500: 21 wallclock secs (21.05 usr +  0.00 sys = 21.05 CPU) @
23.75/s (n=500)
* Length = 1000
timethis 500: 35 wallclock secs (34.75 usr +  0.00 sys = 34.75 CPU) @
14.39/s (n=500)
* Length = 1024
timethis 500: 36 wallclock secs (35.38 usr +  0.00 sys = 35.38 CPU) @
14.13/s (n=500)

real	5m17.628s
user	5m16.684s
sys	0m0.104s




Yves

-- 
perl -Mre=debug -e "/just|another|perl|hacker/"




nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About