Re: Why murmur3 for transaction_write_set_extraction

Mark Atwood <[email protected]> writes:
> Ask Austin =E2=80=9CTanj=E2=80=9D Appleby, as he was it=E2=80=99s creator.
>
> It was probably Brian who put it in MySQL, after watching Tanj=E2=80=99s =
presentation
>
> I think the argument was, at the time, it was insanely fast compared to s=
oftware implementations of CRC32, and it actually has better various proper=
ties than CRC32 (such as all 32 bits of the output are closer to flat 50% a=
nd independent with very short input strings.)
>
> Murmer proved it=E2=80=99s value the same way in Perl5=E2=80=99s hashs.

Software implementation maybe, but when comparing what we can do with
the optimized POWER8 implementation of CRC32 (about 52GiB/sec on a
4.1Ghz core), it's *INSANELY* slower.

Even compared to the best software implementation of CRC32, it's not
actually any faster (at least the implementation on the murmur3
wikipedia page).

When compared to the optimized CRC32 impl on POWER8, Murmur3 is about
53x slower.

The good news is that the 128bit version of MURMUR3 (taken straight from
Austin's github) is about twice as fast as straight 32bit murmur3... but
that's still 25x *slower* than optimized CRC32, but at least it starts
to beat the slice_by_8 implementation of CRC32 (fast portable impl) by
2x.

I'm not sure what the numbers are on intel, i'll let others do that
comparison (modern intel CPUs have both polynomial multiplication
instructions and a CRC32 instruction that will also accelerate CRC32
greatly).

CRC32 benchmarks from here:
https://github.com/antonblanchard/crc32-vpmsum/

My murmur3 benchmarks (run the same as anton's crc32 ones) are up here:
https://github.com/stewart-ibm/microbenchmarks/

--=20
Stewart Smith
OPAL Architect, IBM.


-- 
MySQL Internals Mailing List
For list archives: http://lists.mysql.com/internals
To unsubscribe:    http://lists.mysql.com/internals