Re: [go-nuts] xxhash-go wraps C xxhash

[Rémy Oudompheng]

On 2013/3/9 <st.k...@gmail.com> wrote:
> Hi,
>
> I discovered xxHash (very fast non cryptographic Hash algorithm) some days
> ago.
> I wrote a little wrapper and I wish your feedback on code:
> https://bitbucket.org/StephaneBunel/xxhash-go
>
> Regards.

Why not rewrite the algorithm in Go?
An easy to use implementation should provide an implementation of the
hash.Hash interface. See how it is done in other packages.

Rémy.

[Jan Mercl]

On Sat, Mar 9, 2013 at 11:00 AM, <st.k...@gmail.com> wrote:
> I discovered xxHash (very fast non cryptographic Hash algorithm) some days
> ago.
> I wrote a little wrapper and I wish your feedback on code:
> https://bitbucket.org/StephaneBunel/xxhash-go

I don't believe the numbers shown at [1].

If the FNV hash[2] needs _two_ fast CPU instructions to compute (a
step), how many CPU instructions xxHash uses to compute (a step) to be
able to claim it is _10 times faster_???

-j

[1]: https://code.google.com/p/xxhash/
[2]: http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

[Robert]

On Saturday, 9 March 2013 20:46:23 UTC+1, Jan Mercl wrote:

If the FNV hash[2] needs _two_ fast CPU instructions to compute (a
step), how many CPU instructions xxHash uses to compute (a step) to be
able to claim it is _10 times faster_???

It could process more data in one step. FNV seems to work on a byte at a time. If this worked on 64bit pieces and used the same number of instructions per step, these values wouldn't be unreasonable.

[Stéphane Bunel]

On 10/03/2013 09:09, Vova Niki wrote:
> Heres a pure go implementation I wrote just now, and it passes
> StephaneBunel/xxhash-go <https://github.com/vova616/xxhash> tests
> https://github.com/vova616/xxhash

I include your code in the benchmark (goxxhash32 line) to compare C and
pure Go implementation. Go is a good player and show that xxhash is
really fast. But pure Go implementation stay slower than C. At least
with go version go1.0.3.

CPU: i5-3570K CPU @ 3.40GHz

Benchmark_xxhash32 50000000 43.3 ns/op

Benchmark_goxxhash32 50000000 66.5 ns/op

Benchmark_CRC32IEEE 10000000 148.0 ns/op
Benchmark_Adler32 20000000 90.2 ns/op
Benchmark_Fnv32 10000000 153.0 ns/op
Benchmark_MurmurHash3Hash32 1000000 2972.0 ns/op

(...)

--
Stéphane.

[Jan Mercl]

On Sun, Mar 10, 2013 at 9:09 AM, Vova Niki <vov...@gmail.com> wrote:

That confirms my earlier stated disbelief in the numbers. If FNV is
processing 8 bits a step and xxhash 32 bits a step then the results
varying between 5:4 to 1:3 makes sense. 1:10 not.

The front page numbers at [1] are bogus, unfortunately.

-j

[1]: https://code.google.com/p/xxhash/

[Rémy Oudompheng]

On 2013/3/10 Vova Niki <vov...@gmail.com> wrote:
> Heres a pure go implementation I wrote just now, and it passes

> StephaneBunel/xxhash-go tests
> https://github.com/vova616/xxhash
>
> Bench results (go tip version devel +db1736b03009):
> vova616/xxhash:
> Benchmark_xxhash32 50000000 57.6 ns/op
> Benchmark_CRC32IEEE 20000000 136 ns/op
> Benchmark_Adler32 10000000 171 ns/op
> Benchmark_Fnv32 10000000 157 ns/op
> Benchmark_MurmurHash3Hash32 1000000 1857 ns/op

Your murmurhash implementation uses binary.Read, which makes it
incredibly slow. You could write this instead:

buf := key
for i := 0; i < nblocks; i++ {
k := binary.LittleEndian.Uint32(buf)
buf = buf[4:]
...
}

Rémy.

[Sébastien Paolacci]

Hello Vova,

I must be bad at `reply all', so here's a second attempt at forming a second fragmented response.

All those numbers obviously depend on which implementation and which test cases are selectively chosen for the benchmarks... By using another murmurhash3 implementation [1] (and the small here-below patch [2]), here are the numbers I now get on my workstation (tip, core i7 @ 3.4 Ghz, linux/amd64):

Benchmark_xxhash32       50000000     60.4 ns/op
Benchmark_CRC32IEEE      10000000    168.0 ns/op
Benchmark_Adler32        50000000     52.2 ns/op
Benchmark_Fnv32          10000000    144.0 ns/op
Benchmark_Murmur3Hash32  50000000     53.0 ns/op
 

`Fnv' clearly suffers from having on such small sequences from requiring a plain hasher, `crc' could really benefit from switching to the Castagnoli sequence that (most of time) has a hardware implementation (http://golang.org/src/pkg/hash/crc32/crc32_amd64.s), and `murmurhash3' could also be made faster by duplicating some part of the code (originally made for larger and segmented writes).

All of those reported benchmarks being based on pure Go implementations (and on the stock gc compiler), I indeed wonder how often does the burden of writing/maintaining wrappers really paybacks in real life situations ;)?..

Cheers,

Sebastien

[1] https://github.com/spaolacci/murmur3

[2]

--- xxhash_test.go.1    2013-03-11 09:15:48.890205106 +0100 
+++ xxhash_test.go      2013-03-11 15:26:58.180768743 +0100 
@@ -7,6 +7,7 @@ 
        "hash/adler32" 
        "hash/crc32" 
        "hash/fnv" 
+       "murmur3" 
        "testing" 
 ) 
  
@@ -143,13 +144,15 @@ 
 func Benchmark_Fnv32(b *testing.B) { 
        h := fnv.New32() 
        for i := 0; i < b.N; i++ { 
-               h.Sum(blob1) 
+               h.Write(blob1) 
+               h.Sum(nil) 
+               h.Reset() 
        } 
 } 
  
-func Benchmark_MurmurHash3Hash32(b *testing.B) { 
+func Benchmark_Murmur3Hash32(b *testing.B) { 
        for i := 0; i < b.N; i++ { 
-               mmh3Hash32(blob1) 
+               murmur3.Sum32(blob1) 
        } 
 } 

On Sun, Mar 10, 2013 at 9:09 AM, Vova Niki <vov...@gmail.com> wrote:
> Heres a pure go implementation I wrote just now, and it passes
> StephaneBunel/xxhash-go tests
> https://github.com/vova616/xxhash
>
> Bench results (go tip version devel +db1736b03009):
> vova616/xxhash:
> Benchmark_xxhash32      50000000                57.6 ns/op
> Benchmark_CRC32IEEE     20000000               136 ns/op
> Benchmark_Adler32       10000000               171 ns/op
> Benchmark_Fnv32 10000000               157 ns/op
> Benchmark_MurmurHash3Hash32      1000000              1857 ns/op
>

> StephaneBunel/xxhash-go:
> Benchmark_xxhash32      10000000               138 ns/op
> Benchmark_CRC32IEEE     10000000               142 ns/op
> Benchmark_Adler32       10000000               166 ns/op
> Benchmark_Fnv32 10000000               279 ns/op
> Benchmark_MurmurHash3Hash32       500000              4436 ns/op
>
> go 1.0.3
> vova616/xxhash:
> Benchmark_xxhash32       5000000               349 ns/op
> Benchmark_CRC32IEEE     10000000               149 ns/op
> Benchmark_Adler32       10000000               166 ns/op
> Benchmark_Fnv32 10000000               280 ns/op
> Benchmark_MurmurHash3Hash32       500000              4324 ns/op
>
> StephaneBunel/xxhash-go:
> Benchmark_xxhash32      10000000               150 ns/op
> Benchmark_CRC32IEEE     10000000               136 ns/op
> Benchmark_Adler32       10000000               171 ns/op
> Benchmark_Fnv32 10000000               155 ns/op
> Benchmark_MurmurHash3Hash32      1000000              1887 ns/op
>
> On Saturday, March 9, 2013 12:00:58 PM UTC+2, st.k...@gmail.com wrote:
>>
>> Hi,

>>
>> I discovered xxHash (very fast non cryptographic Hash algorithm) some days
>> ago.
>> I wrote a little wrapper and I wish your feedback on code:
>> https://bitbucket.org/StephaneBunel/xxhash-go
>>

>> Regards.
>>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>  
>  

[Sébastien Paolacci]

Hi Vova,

With your repo as of ~5 hours ago, and few additional (pushed) tweaks to https://github.com/spaolacci/murmur3, I got

Benchmark_xxhash32       50000000      28.5 ns/op
Benchmark_CRC32IEEE      10000000     168.0 ns/op
Benchmark_Adler32        50000000      52.1 ns/op
Benchmark_Fnv32          10000000     143.0 ns/op
Benchmark_Murmur3Hash32 100000000      29.6 ns/op

I'll have a look at your last changes, but I can't see any reason for your last run to not be trustworthy.

The original post being around cgo wrappers against native Go implementations, I guess it should now also be tested against them.

Another interesting case would be to analyse that hash speed as a function of the input size, as well of course as xxhash collision rate, dispersion quality and so on. Do you have any pointer to such an analysis?

Thanks,

Sebastien

On Tue, Mar 12, 2013 at 6:19 AM, Vova Niki <vov...@gmail.com> wrote:
> After some more unsafe using I got to
> Benchmark_xxhash32      100000000               19.8 ns/op
>
> so thats another less 5 ns/op
> its not yet in the repo because its kind of unsafe and I only ported
> Checksum32Seed
>
>
> 2013/3/11 Sébastien Paolacci <sebastien...@gmail.com>
>>
>> On Mon, Mar 11, 2013 at 9:33 PM, Vova Niki <vov...@gmail.com> wrote:
>>>
>>> spaolacci/murmur3 used unsafe to make the performance higher.
>>>
>>
>> Yes it is cheating. Sort of. It doesn't really do anything unsafe per se,
>> it just manually propagate range analysis result (and prevent a few
>> bound-checks) that the `gc' can't automatically handle right now. Read
>> validity comes from two lines above, right before the loop (nblocks :=
>> len(p) / 4).
>>
>> I'll have a run at your last xxhash tomorrow.
>>
>> Sebastien
>
>