Are there any other hashes we should be benchmarking against? about meow_hash HOT 18 CLOSED

FarmHash - compile with SSE4.2 enabled.

from meow_hash.

Highway Hash and Metro Hash come to mind.

from meow_hash.

And https://github.com/lemire/clhash

from meow_hash.

Metro hash is already in the benchmark set. Highway Hash was in the set, but it was so slow I had to pull it - it was an order of magnitude slower than all the other hashes in the set, and was dominating the amount of time it took to run the benchmark series :(

I will look at adding FarmHash and CLHash.

- Casey

from meow_hash.

I just added Meow to the devel branch of t1ha's internal benchmark.
Yet only MeowHash1() with -maes GCC's flag.

Preparing to benchmarking...
 - running on CPU#3
 - use RDPMC_40000001 as clock source for benchmarking
 - assume it cheap and stable
 - measure granularity and overhead: 53 cycles, 0.0188679 iteration/cycle

Bench for tiny keys (7 bytes):
t1ha2_atonce            :     17.300 cycle/hash,  2.471 cycle/byte,  0.405 byte/cycle,  1.214 Gb/s @3GHz 
t1ha0                   :     16.125 cycle/hash,  2.304 cycle/byte,  0.434 byte/cycle,  1.302 Gb/s @3GHz 
meow1_aes               :     96.312 cycle/hash, 13.759 cycle/byte,  0.073 byte/cycle,  0.218 Gb/s @3GHz 
xxhash64                :     26.219 cycle/hash,  3.746 cycle/byte,  0.267 byte/cycle,  0.801 Gb/s @3GHz 
StadtX                  :     19.302 cycle/hash,  2.757 cycle/byte,  0.363 byte/cycle,  1.088 Gb/s @3GHz 
HighwayHash64_avx2      :     56.750 cycle/hash,  8.107 cycle/byte,  0.123 byte/cycle,  0.370 Gb/s @3GHz 

Bench for large keys (16384 bytes):
t1ha2_atonce            :   3547.000 cycle/hash,  0.216 cycle/byte,  4.619 byte/cycle, 13.857 Gb/s @3GHz 
t1ha0                   :   1308.000 cycle/hash,  0.080 cycle/byte, 12.526 byte/cycle, 37.578 Gb/s @3GHz 
meow1_aes               :   1139.000 cycle/hash,  0.070 cycle/byte, 14.385 byte/cycle, 43.154 Gb/s @3GHz 
xxhash64                :   4119.000 cycle/hash,  0.251 cycle/byte,  3.978 byte/cycle, 11.933 Gb/s @3GHz 
StadtX                  :   3670.000 cycle/hash,  0.224 cycle/byte,  4.464 byte/cycle, 13.393 Gb/s @3GHz 
HighwayHash64_avx2      :   4405.000 cycle/hash,  0.269 cycle/byte,  3.719 byte/cycle, 11.158 Gb/s @3GHz 

from meow_hash.

Highway Hash was in the set, but it was so slow I had to pull it

That's surprising, sounds like it might not be compiled with -mavx2 - should be around 0.25 cpb (0.269 in the above results).

from meow_hash.

Highway Hash was in the set, but it was so slow I had to pull it

That's surprising, sounds like it might not be compiled with -mavx2 - should be around 0.25 cpb (0.269 in the above results).

In the my benchmark -mavx2 for HWH is here.

Intel(R) Core(TM) i7-4600U CPU @ 2.10GHz
gcc version 7.3.0 (Ubuntu 7.3.0-27ubuntu1~18.04)

from meow_hash.

That is correct, it would not have been compiled with AVX2. At the moment we generally don't allow anything past AVX. Technically we should be benchmarking only up through SSE AES-NI, since that is all that Meow requires. And if Highway Hash only gets in the 4bytes/cycle even when extended to AVX2, I don't think it's appropriate to expand the qualifications for being in the benchmarking to AVX2 just for a hash that isn't particularly fast... if it were actually going to be a leading hash it might make sense, but requiring AVX2 for a slow hash doesn't seem interesting?

- Casey

from meow_hash.

I agree it's justified to omit HWH because it's in a different class (aiming for robustness vs. malicious inputs).

we should be benchmarking only up through SSE AES-NI, since that is all that Meow requires.

Surprisingly, AESNI is only guaranteed for Skylake and later (https://reviews.llvm.org/rL341862). For example, here's a Haswell without AESNI: https://ark.intel.com/products/76294/Intel-Core-i3-4102E-Processor-3M-Cache-1_60-GHz

(FYI we also use AES in a 2048-bit cryptographic permutation serving as an RNG: http://github.com/google/randen)

from meow_hash.

Well, if it's unlikely that AES-NI would exist without AVX-2, then I'd be OK raising the benchmark to AVX2... the goal is just to compare apples to apples :)

- Casey

from meow_hash.

That is not quite accurate. There are a lot of Intel CPU's with AES-NI, but without AVX/AVX2. This is usually for lower end all-in-one box PC's or mobile/tablet ones. Whether this is target audience of Meow hash... not for me to say.

Example - I have small-box-pc with Pentium N4200 which is Goldmont microarchitecture (chronologically comes after Skylake). It has all SSE's up to 4.2, it also has AES-NI and SHA1/SHA256 instruction sets. But no AVX and no AVX2.

from meow_hash.

I added Highway Hash back in, and it is still excruciatingly slow even with /arch:AVX2, so I think the problem is maybe I have only the C implementation (there are no intrinsics anywhere in it :( ) I will look for an optimized version.

- Casey

from meow_hash.

Grab the official C++ code from https://github.com/google/highwayhash

from meow_hash.

@dgryski That is what I grabbed - I just took the "C" directory from there and compiled it. I'm guessing that is not what they intend, but I haven't looked through the giant other source directory to find out where the actual optimized hash lives.

If someone wants to send me what the proper include is to actually just compile the hash function, I'll stick it in place of the C one :)

- Casey

from meow_hash.

The C directory is a reference implementation with no vector instructions. You need the highwayhash directory with all the C++ code. The README lays out what you need to do. Basically, make, then use the header you want and link against libhighwayhash.

from meow_hash.

That's not going to work, then. Every other hash we use is ~4 files, tops. If someone wants to make a simple h/cpp pair of it, I'll add it to the benchmark, otherwise it's a no-go. I'm not going to quintuple (or more??) the size of the Meow benchmark build just for one (not particularly fast) hash.

- Casey

from meow_hash.

Fair enough.

from meow_hash.

Besides the aforementioned Highway Hash problem, v0.3 will come with the other hashes requested. I should note, however, that although I included CLHash, it really should be disqualified, because it cannot hash things with a seed at reasonable speeds. Each time you change the seed, you must go through a lengthy separate call that generates a table. So its performance is apples to oranges as opposed to all the other hashes in the suite, which are expected to take a different seed on every call.

- Casey

from meow_hash.