~ubuntu-push-hackers/ubuntu-push/murmur3 : changes

~ubuntu-push-hackers/ubuntu-push/murmur3 » Changes from revision 24

From Revision 24 to 5

Rev	Summary	Authors	Tags	Date
24	Remove extra reference to `digest128` (#23) Remove extra reference to `digest128` (#23) This extra reference isn't really required as this object should be anyway allocated on the stack. I wasn't able to reproduce it with micro-benchmarks for murmur3, but with bigger library I'm working on this leads to one extra memory allocation when slice passed to `Sum128()` is taken from byte array. Performance improvement is small, but noticeable for smaller slices: ``` name old time/op new time/op delta 128/1-8 29.6ns ± 1% 25.0ns ± 1% -15.42% (p=0.008 n=5+5) 128/2-8 30.0ns ± 2% 25.9ns ± 2% -13.66% (p=0.008 n=5+5) 128/4-8 30.5ns ± 2% 27.5ns ± 2% -9.83% (p=0.008 n=5+5) 128/8-8 31.7ns ± 1% 28.8ns ± 2% -8.97% (p=0.008 n=5+5) 128/16-8 28.9ns ± 1% 26.0ns ± 1% -10.10% (p=0.008 n=5+5) 128/32-8 32.3ns ± 2% 28.9ns ± 1% -10.64% (p=0.008 n=5+5) 128/64-8 39.2ns ± 1% 35.0ns ± 1% -10.66% (p=0.008 n=5+5) 128/128-8 51.3ns ± 2% 47.6ns ± 1% -7.14% (p=0.008 n=5+5) 128/256-8 75.0ns ± 3% 72.3ns ± 2% -3.55% (p=0.016 n=5+5) 128/512-8 127ns ± 2% 125ns ± 1% ~ (p=0.056 n=5+5) 128/1024-8 223ns ± 1% 225ns ± 2% ~ (p=0.183 n=5+5) 128/2048-8 420ns ± 1% 425ns ± 1% ~ (p=0.056 n=5+5) 128/4096-8 822ns ± 2% 815ns ± 2% ~ (p=0.333 n=5+5) 128/8192-8 1.60µs ± 2% 1.61µs ± 3% ~ (p=0.516 n=5+5) name old speed new speed delta 128/1-8 33.8MB/s ± 1% 40.0MB/s ± 1% +18.27% (p=0.008 n=5+5) 128/2-8 66.6MB/s ± 2% 77.1MB/s ± 2% +15.76% (p=0.008 n=5+5) 128/4-8 131MB/s ± 2% 145MB/s ± 2% +10.96% (p=0.008 n=5+5) 128/8-8 253MB/s ± 1% 278MB/s ± 2% +9.86% (p=0.008 n=5+5) 128/16-8 554MB/s ± 1% 616MB/s ± 1% +11.26% (p=0.008 n=5+5) 128/32-8 990MB/s ± 2% 1108MB/s ± 1% +11.90% (p=0.008 n=5+5) 128/64-8 1.63GB/s ± 1% 1.83GB/s ± 2% +11.95% (p=0.008 n=5+5) 128/128-8 2.49GB/s ± 2% 2.69GB/s ± 1% +7.73% (p=0.008 n=5+5) 128/256-8 3.42GB/s ± 3% 3.54GB/s ± 2% +3.66% (p=0.016 n=5+5) 128/512-8 4.00GB/s ± 2% 4.09GB/s ± 1% +2.23% (p=0.032 n=5+5) 128/1024-8 4.58GB/s ± 1% 4.53GB/s ± 2% ~ (p=0.222 n=5+5) 128/2048-8 4.87GB/s ± 1% 4.81GB/s ± 1% -1.12% (p=0.032 n=5+5) 128/4096-8 4.98GB/s ± 3% 5.02GB/s ± 2% ~ (p=0.421 n=5+5) 128/8192-8 5.11GB/s ± 2% 5.08GB/s ± 3% ~ (p=0.548 n=5+5) ```	Andrey Smirnov		5 years ago
23	Use Go 1.9 bits.RotateLeft32 functions. Use Go 1.9 bits.RotateLeft32 functions. As per Maciej Biłas suggestion for rotate 64.	Sebastien Paolacci		5 years ago
22	Murmur128: use Go 1.9 bits.RotateLeft64 functions (#22) Murmur128: use Go 1.9 bits.RotateLeft64 functions (#22) Sadly does not look like it improves performance without `bits.RotateLeft64`: ``` go test -run - -bench Benchmark128 . goos: darwin goarch: amd64 pkg: github.com/spaolacci/murmur3 Benchmark128/1-8 100000000 18.8 ns/op 53.20 MB/s Benchmark128/2-8 100000000 20.0 ns/op 100.16 MB/s Benchmark128/4-8 100000000 20.6 ns/op 194.31 MB/s Benchmark128/8-8 100000000 23.0 ns/op 348.01 MB/s Benchmark128/16-8 100000000 20.3 ns/op 787.21 MB/s Benchmark128/32-8 100000000 23.0 ns/op 1391.11 MB/s Benchmark128/64-8 50000000 28.8 ns/op 2223.46 MB/s Benchmark128/128-8 50000000 38.9 ns/op 3292.33 MB/s Benchmark128/256-8 20000000 62.7 ns/op 4083.19 MB/s Benchmark128/512-8 20000000 111 ns/op 4577.90 MB/s Benchmark128/1024-8 10000000 209 ns/op 4877.98 MB/s Benchmark128/2048-8 3000000 419 ns/op 4885.73 MB/s Benchmark128/4096-8 2000000 804 ns/op 5093.00 MB/s Benchmark128/8192-8 1000000 1589 ns/op 5154.91 MB/s ``` with `bits.RotateLeft64`: ``` go test -run - -bench Benchmark128 . goos: darwin goarch: amd64 pkg: github.com/spaolacci/murmur3 Benchmark128/1-8 100000000 18.6 ns/op 53.65 MB/s Benchmark128/2-8 100000000 19.0 ns/op 105.24 MB/s Benchmark128/4-8 100000000 20.2 ns/op 198.10 MB/s Benchmark128/8-8 100000000 22.9 ns/op 348.85 MB/s Benchmark128/16-8 100000000 20.4 ns/op 786.13 MB/s Benchmark128/32-8 100000000 24.2 ns/op 1322.43 MB/s Benchmark128/64-8 50000000 28.3 ns/op 2257.56 MB/s Benchmark128/128-8 30000000 39.0 ns/op 3279.77 MB/s Benchmark128/256-8 20000000 63.4 ns/op 4036.51 MB/s Benchmark128/512-8 20000000 113 ns/op 4520.35 MB/s Benchmark128/1024-8 10000000 222 ns/op 4604.64 MB/s Benchmark128/2048-8 3000000 432 ns/op 4739.47 MB/s Benchmark128/4096-8 2000000 781 ns/op 5240.30 MB/s Benchmark128/8192-8 1000000 1551 ns/op 5280.24 MB/s ```	Maciej Biłas		5 years ago
21	Write benchmarks using sub-benchmarks (#20) Write benchmarks using sub-benchmarks (#20) * Write benchmarks using sub-benchmarks While I'm at it, also add benchmarks for Sum64.	Caleb Spare	v1.0.0, v1.1.0	6 years ago
20	Ease `IMUL 5, h1` 32 bits hash (~10 % for > 256 B). Ease `IMUL 5, h1` 32 bits hash (~10 % for > 256 B). Replace by a left shift and an addition. Generated code for 64 bits version already map to the even most adequate `LEA`. On a mid-2012 MBA, benchmark old MB/s new MB/s speedup Benchmark32_1-4 90.18 91.08 1.01x Benchmark32_2-4 168.26 168.55 1.00x Benchmark32_4-4 342.13 338.26 0.99x Benchmark32_8-4 587.46 584.68 1.00x Benchmark32_16-4 981.80 990.72 1.01x Benchmark32_32-4 1349.67 1370.62 1.02x Benchmark32_64-4 1684.94 1696.83 1.01x Benchmark32_128-4 1748.24 1746.80 1.00x Benchmark32_256-4 1805.96 1933.24 1.07x Benchmark32_512-4 1845.56 2019.75 1.09x Benchmark32_1024-4 1856.36 2031.61 1.09x Benchmark32_2048-4 1890.43 2032.47 1.08x Benchmark32_4096-4 1881.13 2085.36 1.11x Benchmark32_8192-4 1889.83 2103.02 1.11x	Sébastien Paolacci	v1.1	6 years ago
19	Restore digest32 complile check for bmixer interface. Restore digest32 complile check for bmixer interface. Not a big deal, but always better to ensure expected interfaces are implemented.	Sébastien Paolacci		6 years ago
18	Merge pull request #15 from mbyczkowski/master Merge pull request #15 from mbyczkowski/master linter and test readability fixes	Sébastien Paolacci		6 years ago
17	Add (long overdue) support for seed parameters. Add (long overdue) support for seed parameters. Since compatibility is key here, use very the same parametrization as in reference C++ implementation (i.e always propose a single uint32 even for `MurmurHash3_x64_128`). API is kept backward compatible, all constructors and top-level accessors gain a `WithSeed(uint32)`. Tests have been extended using the SMHasher original implementation and have been enhanced with reset sequences.	Sébastien Paolacci		6 years ago
16	travis: add wildcard on Go1 major/minor versions. travis: add wildcard on Go1 major/minor versions. As suggested by https://docs.travis-ci.com/user/languages/go	Sébastien Paolacci		6 years ago
15	Merge pull request #14 from mengzhuo/master Merge pull request #14 from mengzhuo/master add travis support	Sébastien Paolacci		6 years ago
14	Merge pull request #7 from mengzhuo/master Merge pull request #7 from mengzhuo/master fix #6 and all 32,64,128, "Sum() method doesn't work after small Write()s"	Sébastien Paolacci	v1.0	8 years ago
13	Update benchmarks to Go1.3 Update benchmarks to Go1.3 Nice speedups for small inputs. Include Go1.0 to Go1.3 comparisons.	Sébastien Paolacci		9 years ago
12	Merge pull request #4 from pedronis/master Merge pull request #4 from pedronis/master test standalone Sum64 and fix seed for it as well	Sébastien Paolacci		9 years ago
11	Change seed from 1 to 0 for better compatibility. Change seed from 1 to 0 for better compatibility. As suggested by Damian Gryski, compatibility with other implementations does matter. The change obviously breaks the backward compatibility. The most embarrassing part being that I can't remember why `1' was chosen at first, but I mainly suspect a misunderstanding of Go's stdlib hash interface (thought 1 was to be preferred to 0). Closes issue #3.	Sébastien Paolacci		9 years ago
10	Merge pull request #1 from dgryski/master Merge pull request #1 from dgryski/master Fix Sum32() index-out-of-range on empty string	Sébastien Paolacci		10 years ago
9	Faster Sum32(data []byte) shortcut. Faster Sum32(data []byte) shortcut. benchmark old ns/op new ns/op delta Benchmark32_1 26 8 -68.50% Benchmark32_2 28 9 -66.73% Benchmark32_4 26 7 -70.08% Benchmark32_8 29 9 -67.69% Benchmark32_16 32 12 -62.54% Benchmark32_32 39 18 -53.33% Benchmark32_64 54 31 -42.33% Benchmark32_128 84 58 -30.37% Benchmark32_256 150 116 -22.67% Benchmark32_512 273 227 -16.85% Benchmark32_1024 523 449 -14.15% Benchmark32_2048 1012 894 -11.66% Benchmark32_4096 2014 1792 -11.02% Benchmark32_8192 4189 3559 -15.04% benchmark old MB/s new MB/s speedup Benchmark32_1 37.54 119.39 3.18x Benchmark32_2 70.39 211.69 3.01x Benchmark32_4 151.30 506.24 3.35x Benchmark32_8 275.73 853.40 3.10x Benchmark32_16 494.69 1324.19 2.68x Benchmark32_32 820.16 1760.81 2.15x Benchmark32_64 1183.45 2051.59 1.73x Benchmark32_128 1518.72 2180.34 1.44x Benchmark32_256 1704.27 2194.85 1.29x Benchmark32_512 1873.52 2247.43 1.20x Benchmark32_1024 1955.82 2276.88 1.16x Benchmark32_2048 2022.21 2289.87 1.13x Benchmark32_4096 2033.24 2284.64 1.12x Benchmark32_8192 1955.41 2301.33 1.18x	Sébastien Paolacci		11 years ago
8	fix not up-to-date unit tests. fix not up-to-date unit tests.	Sébastien Paolacci		11 years ago
7	Add turn-key (and alloc-free) Sum{32,64,128} calls. Add turn-key (and alloc-free) Sum{32,64,128} calls. They all follow the `result := SumXXX(data []byte)' pattern, and are exactly equivalent to: ` func Hash(data []byte) HXXX { hasher := NewXXX() hasher.Write(data) return hasher.SumXXX() } ' In addition to being handy for most usages, it also greatly improves small (few kilobytes and below) writes performance: benchmark old ns/op new ns/op delta Benchmark32_1 118 26 -77.37% Benchmark32_2 134 28 -78.96% Benchmark32_4 116 26 -77.24% Benchmark32_8 118 29 -75.42% Benchmark32_16 121 32 -73.31% Benchmark32_32 129 39 -69.69% Benchmark32_64 145 54 -62.69% Benchmark32_128 177 84 -52.37% Benchmark32_256 246 150 -39.02% Benchmark32_512 375 272 -27.47% Benchmark32_1024 627 520 -17.07% Benchmark32_2048 1105 1012 -8.42% Benchmark32_4096 2091 1998 -4.45% Benchmark32_8192 4062 3973 -2.19% Benchmark128_1 122 33 -72.79% Benchmark128_2 138 33 -75.87% Benchmark128_4 159 35 -77.74% Benchmark128_8 143 36 -74.41% Benchmark128_16 122 35 -70.90% Benchmark128_32 125 35 -71.76% Benchmark128_64 133 44 -66.69% Benchmark128_128 149 58 -60.94% Benchmark128_256 181 85 -52.87% Benchmark128_512 240 142 -40.83% Benchmark128_1024 360 258 -28.33% Benchmark128_2048 606 494 -18.48% Benchmark128_4096 1064 955 -10.24% Benchmark128_8192 1994 1884 -5.52% benchmark old MB/s new MB/s speedup Benchmark32_1 8.46 37.47 4.43x Benchmark32_2 14.88 70.95 4.77x Benchmark32_4 34.21 151.56 4.43x Benchmark32_8 67.65 275.42 4.07x Benchmark32_16 131.31 495.74 3.78x Benchmark32_32 246.21 818.67 3.33x Benchmark32_64 440.35 1182.40 2.69x Benchmark32_128 723.01 1518.96 2.10x Benchmark32_256 1037.15 1700.58 1.64x Benchmark32_512 1363.39 1877.52 1.38x Benchmark32_1024 1631.87 1968.68 1.21x Benchmark32_2048 1853.38 2022.71 1.09x Benchmark32_4096 1958.09 2049.31 1.05x Benchmark32_8192 2016.45 2061.41 1.02x Benchmark128_1 8.14 30.15 3.70x Benchmark128_2 14.48 59.99 4.14x Benchmark128_4 25.01 112.88 4.51x Benchmark128_8 55.92 218.30 3.90x Benchmark128_16 131.09 450.86 3.44x Benchmark128_32 254.00 905.84 3.57x Benchmark128_64 479.22 1443.76 3.01x Benchmark128_128 856.81 2201.02 2.57x Benchmark128_256 1408.09 2999.88 2.13x Benchmark128_512 2132.96 3592.97 1.68x Benchmark128_1024 2843.22 3963.74 1.39x Benchmark128_2048 3374.67 4144.65 1.23x Benchmark128_4096 3849.06 4285.80 1.11x Benchmark128_8192 4106.64 4347.12 1.06x	Sébastien Paolacci		11 years ago
6	add few benchmarks. add few benchmarks.	Sébastien Paolacci		11 years ago
5	add hash.Hash64 interface. add hash.Hash64 interface. Just a stripped-down version of the Hash128 implementation, but can be handy though.	Sébastien Paolacci		11 years ago

Older »