Front page | perl.perl5.porters |
Postings from October 2012
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/"