Ubuntu Push Notifications

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

Created by Samuele Pedroni and last modified
Get this branch:
bzr branch lp:~ubuntu-push-hackers/ubuntu-push/murmur3

Branch merges

Related bugs

Related blueprints

Branch information

Owner:
Ubuntu Push Hackers
Project:
Ubuntu Push Notifications
Status:
Development

Import details

Import Status: Reviewed

This branch is an import of the HEAD branch of the Git repository at https://github.com/spaolacci/murmur3.git.

The next import is scheduled to run .

Last successful import was .

Import started on juju-98ee42-prod-launchpad-codeimport-4 and finished taking 10 seconds — see the log
Import started on juju-98ee42-prod-launchpad-codeimport-4 and finished taking 10 seconds — see the log
Import started on juju-98ee42-prod-launchpad-codeimport-1 and finished taking 5 seconds — see the log
Import started on juju-98ee42-prod-launchpad-codeimport-1 and finished taking 5 seconds — see the log
Import started on juju-98ee42-prod-launchpad-codeimport-0 and finished taking 10 seconds — see the log
Import started on juju-98ee42-prod-launchpad-codeimport-5 and finished taking 10 seconds — see the log
Import started on juju-98ee42-prod-launchpad-codeimport-5 and finished taking 10 seconds — see the log
Import started on juju-98ee42-prod-launchpad-codeimport-5 and finished taking 5 seconds — see the log
Import started on juju-98ee42-prod-launchpad-codeimport-4 and finished taking 5 seconds — see the log
Import started on juju-98ee42-prod-launchpad-codeimport-1 and finished taking 5 seconds — see the log

Recent revisions

24. By Andrey Smirnov <email address hidden>

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)
```

23. By Sebastien Paolacci <email address hidden>

Use Go 1.9 bits.RotateLeft32 functions.

As per Maciej Biłas suggestion for rotate 64.

22. By Maciej Biłas

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
```

21. By Caleb Spare

Write benchmarks using sub-benchmarks (#20)

* Write benchmarks using sub-benchmarks

While I'm at it, also add benchmarks for Sum64.

20. By Sébastien Paolacci <email address hidden>

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

19. By Sébastien Paolacci <email address hidden>

Restore digest32 complile check for bmixer interface.

Not a big deal, but always better to ensure expected interfaces are
implemented.

18. By Sébastien Paolacci <email address hidden>

Merge pull request #15 from mbyczkowski/master

linter and test readability fixes

17. By Sébastien Paolacci <email address hidden>

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.

16. By Sébastien Paolacci <email address hidden>

travis: add wildcard on Go1 major/minor versions.

As suggested by https://docs.travis-ci.com/user/languages/go

15. By Sébastien Paolacci <email address hidden>

Merge pull request #14 from mengzhuo/master

add travis support

Branch metadata

Branch format:
Branch format 7
Repository format:
Bazaar repository format 2a (needs bzr 1.16 or later)
This branch contains Public information 
Everyone can see this information.