Skip to content

Instantly share code, notes, and snippets.

@vstakhov

vstakhov/seahash.cc

Last active December 3, 2016 18:47
Show Gist options
  • Save vstakhov/b58b855532a424cd634b6c7ea7baa1b9 to your computer and use it in GitHub Desktop.
Save vstakhov/b58b855532a424cd634b6c7ea7baa1b9 to your computer and use it in GitHub Desktop.
Download ZIP
Seahash in C(++)
Raw
seahash.cc
#include <stdint.h>
#include <string.h>
#include <assert.h>
static inline uint64_t
diffuse(uint64_t val)
{
uint64_t a, b;
val *= 0x6eed0e9da4d94a4fULL;
a = val >> 32;
b = val >> 60;
val ^= a >> b;
val *= 0x6eed0e9da4d94a4fULL;
return val;
}
void sea_hash_test(const void *key, int len, uint32_t seed, void *out) {
uint64_t a, b, c, d;
uint64_t s = seed;
uint64_t *p;
unsigned char pad[8] = {0};
a = 0x16f11fe89b0d677cULL ^ s;
b = 0xb480a793d8e6c86cULL;
c = 0x6fe2e5aaf078ebc9ULL;
d = 0x14f994a4c5259381ULL;
p = (uint64_t *)key;
while (len >= 32) {
a ^= *p++;
b ^= *p++;
c ^= *p++;
d ^= *p++;
a = diffuse(a);
b = diffuse(b);
c = diffuse(c);
d = diffuse(d);
len -= 32;
}
switch (len) {
case 25 ... 31:
a ^= *p++;
b ^= *p++;
c ^= *p++;
memcpy(pad, p, len - 24);
d ^= *(uint64_t *)pad;
a = diffuse(a);
b = diffuse(b);
c = diffuse(c);
d = diffuse(d);
break;
case 24:
a ^= *p++;
b ^= *p++;
c ^= *p++;
a = diffuse(a);
b = diffuse(b);
c = diffuse(c);
break;
case 17 ... 23:
a ^= *p++;
b ^= *p++;
memcpy(pad, p, len - 16);
c ^= *(uint64_t *)pad;
a = diffuse(a);
b = diffuse(b);
c = diffuse(c);
break;
case 16:
a ^= *p++;
b ^= *p++;
a = diffuse(a);
b = diffuse(b);
break;
case 9 ... 15:
a ^= *p++;
memcpy(pad, p, len - 8);
b ^= *(uint64_t *)pad;
a = diffuse(a);
b = diffuse(b);
break;
case 8:
a ^= *p++;
a = diffuse(a);
break;
case 1 ... 7:
memcpy(pad, p, len);
a ^= *(uint64_t *)pad;
a = diffuse(a);
break;
case 0:
break;
default:
assert(0);
}
a ^= b;
c ^= d;
a ^= c;
a ^= (uint64_t)len;
uint64_t r = diffuse(a);
memcpy(out, &r, 8);
}
@vstakhov
Copy link
Author

vstakhov commented Dec 3, 2016

--- Testing seahash "seahash"

[[[ Sanity Tests ]]]

Verification value 0x25AE1F61 : PASS
Running sanity check 1 ..........PASS
Running AppendedZeroesTest..........PASS

[[[ Speed Tests ]]]

Bulk speed test - 262144-byte keys
Alignment 7 - 3.181 bytes/cycle - 9102.09 MiB/sec @ 3 ghz
Alignment 6 - 3.277 bytes/cycle - 9376.04 MiB/sec @ 3 ghz
Alignment 5 - 3.290 bytes/cycle - 9412.64 MiB/sec @ 3 ghz
Alignment 4 - 3.320 bytes/cycle - 9498.83 MiB/sec @ 3 ghz
Alignment 3 - 3.415 bytes/cycle - 9770.01 MiB/sec @ 3 ghz
Alignment 2 - 3.448 bytes/cycle - 9864.58 MiB/sec @ 3 ghz
Alignment 1 - 3.448 bytes/cycle - 9864.70 MiB/sec @ 3 ghz
Alignment 0 - 3.487 bytes/cycle - 9976.74 MiB/sec @ 3 ghz
Average - 3.358 bytes/cycle - 9608.20 MiB/sec @ 3 ghz

Small key speed test - 1-byte keys - 36.00 cycles/hash
Small key speed test - 2-byte keys - 36.00 cycles/hash
Small key speed test - 3-byte keys - 37.00 cycles/hash
Small key speed test - 4-byte keys - 39.99 cycles/hash
Small key speed test - 5-byte keys - 41.00 cycles/hash
Small key speed test - 6-byte keys - 41.88 cycles/hash
Small key speed test - 7-byte keys - 41.93 cycles/hash
Small key speed test - 8-byte keys - 29.97 cycles/hash
Small key speed test - 9-byte keys - 41.99 cycles/hash
Small key speed test - 10-byte keys - 42.62 cycles/hash
Small key speed test - 11-byte keys - 43.00 cycles/hash
Small key speed test - 12-byte keys - 42.84 cycles/hash
Small key speed test - 13-byte keys - 46.00 cycles/hash
Small key speed test - 14-byte keys - 46.12 cycles/hash
Small key speed test - 15-byte keys - 47.00 cycles/hash
Small key speed test - 16-byte keys - 30.20 cycles/hash
Small key speed test - 17-byte keys - 40.21 cycles/hash
Small key speed test - 18-byte keys - 41.36 cycles/hash
Small key speed test - 19-byte keys - 42.09 cycles/hash
Small key speed test - 20-byte keys - 44.00 cycles/hash
Small key speed test - 21-byte keys - 45.13 cycles/hash
Small key speed test - 22-byte keys - 45.14 cycles/hash
Small key speed test - 23-byte keys - 46.00 cycles/hash
Small key speed test - 24-byte keys - 29.00 cycles/hash
Small key speed test - 25-byte keys - 39.99 cycles/hash
Small key speed test - 26-byte keys - 41.00 cycles/hash
Small key speed test - 27-byte keys - 41.00 cycles/hash
Small key speed test - 28-byte keys - 44.00 cycles/hash
Small key speed test - 29-byte keys - 44.00 cycles/hash
Small key speed test - 30-byte keys - 45.00 cycles/hash
Small key speed test - 31-byte keys - 46.35 cycles/hash
Average 41.220 cycles/hash

@vstakhov
Copy link
Author

vstakhov commented Dec 3, 2016

--- Testing xxHash64 "xxHash, 64-bit"

[[[ Sanity Tests ]]]

Verification value 0x024B7CF4 : PASS
Running sanity check 1 ..........PASS
Running AppendedZeroesTest..........PASS

[[[ Speed Tests ]]]

Bulk speed test - 262144-byte keys
Alignment 7 - 5.843 bytes/cycle - 16717.48 MiB/sec @ 3 ghz
Alignment 6 - 6.135 bytes/cycle - 17553.16 MiB/sec @ 3 ghz
Alignment 5 - 6.018 bytes/cycle - 17217.11 MiB/sec @ 3 ghz
Alignment 4 - 5.859 bytes/cycle - 16761.48 MiB/sec @ 3 ghz
Alignment 3 - 6.135 bytes/cycle - 17551.65 MiB/sec @ 3 ghz
Alignment 2 - 6.072 bytes/cycle - 17372.29 MiB/sec @ 3 ghz
Alignment 1 - 5.897 bytes/cycle - 16871.33 MiB/sec @ 3 ghz
Alignment 0 - 6.082 bytes/cycle - 17401.26 MiB/sec @ 3 ghz
Average - 6.005 bytes/cycle - 17180.72 MiB/sec @ 3 ghz

Small key speed test - 1-byte keys - 20.70 cycles/hash
Small key speed test - 2-byte keys - 24.00 cycles/hash
Small key speed test - 3-byte keys - 27.95 cycles/hash
Small key speed test - 4-byte keys - 21.80 cycles/hash
Small key speed test - 5-byte keys - 24.84 cycles/hash
Small key speed test - 6-byte keys - 27.23 cycles/hash
Small key speed test - 7-byte keys - 31.00 cycles/hash
Small key speed test - 8-byte keys - 30.81 cycles/hash
Small key speed test - 9-byte keys - 34.60 cycles/hash
Small key speed test - 10-byte keys - 37.00 cycles/hash
Small key speed test - 11-byte keys - 40.36 cycles/hash
Small key speed test - 12-byte keys - 34.16 cycles/hash
Small key speed test - 13-byte keys - 37.46 cycles/hash
Small key speed test - 14-byte keys - 40.94 cycles/hash
Small key speed test - 15-byte keys - 44.00 cycles/hash
Small key speed test - 16-byte keys - 34.65 cycles/hash
Small key speed test - 17-byte keys - 37.00 cycles/hash
Small key speed test - 18-byte keys - 40.85 cycles/hash
Small key speed test - 19-byte keys - 44.86 cycles/hash
Small key speed test - 20-byte keys - 38.00 cycles/hash
Small key speed test - 21-byte keys - 41.33 cycles/hash
Small key speed test - 22-byte keys - 44.00 cycles/hash
Small key speed test - 23-byte keys - 48.48 cycles/hash
Small key speed test - 24-byte keys - 38.00 cycles/hash
Small key speed test - 25-byte keys - 41.00 cycles/hash
Small key speed test - 26-byte keys - 47.42 cycles/hash
Small key speed test - 27-byte keys - 48.00 cycles/hash
Small key speed test - 28-byte keys - 42.54 cycles/hash
Small key speed test - 29-byte keys - 45.28 cycles/hash
Small key speed test - 30-byte keys - 49.22 cycles/hash
Small key speed test - 31-byte keys - 52.37 cycles/hash
Average 37.737 cycles/hash

@vstakhov
Copy link
Author

vstakhov commented Dec 3, 2016

--- Testing metrohash64_1 "MetroHash64_1 for 64-bit"

[[[ Sanity Tests ]]]

Verification value 0xEE88F7D2 : PASS
Running sanity check 1 ..........PASS
Running AppendedZeroesTest..........PASS

[[[ Speed Tests ]]]

Bulk speed test - 262144-byte keys
Alignment 7 - 6.466 bytes/cycle - 18498.28 MiB/sec @ 3 ghz
Alignment 6 - 6.436 bytes/cycle - 18414.10 MiB/sec @ 3 ghz
Alignment 5 - 6.218 bytes/cycle - 17791.07 MiB/sec @ 3 ghz
Alignment 4 - 6.446 bytes/cycle - 18440.76 MiB/sec @ 3 ghz
Alignment 3 - 6.516 bytes/cycle - 18643.62 MiB/sec @ 3 ghz
Alignment 2 - 6.476 bytes/cycle - 18528.83 MiB/sec @ 3 ghz
Alignment 1 - 6.511 bytes/cycle - 18629.38 MiB/sec @ 3 ghz
Alignment 0 - 6.676 bytes/cycle - 19099.58 MiB/sec @ 3 ghz
Average - 6.468 bytes/cycle - 18505.70 MiB/sec @ 3 ghz

Small key speed test - 1-byte keys - 19.00 cycles/hash
Small key speed test - 2-byte keys - 19.00 cycles/hash
Small key speed test - 3-byte keys - 22.80 cycles/hash
Small key speed test - 4-byte keys - 18.41 cycles/hash
Small key speed test - 5-byte keys - 23.99 cycles/hash
Small key speed test - 6-byte keys - 23.96 cycles/hash
Small key speed test - 7-byte keys - 28.92 cycles/hash
Small key speed test - 8-byte keys - 27.20 cycles/hash
Small key speed test - 9-byte keys - 29.08 cycles/hash
Small key speed test - 10-byte keys - 29.19 cycles/hash
Small key speed test - 11-byte keys - 33.10 cycles/hash
Small key speed test - 12-byte keys - 29.22 cycles/hash
Small key speed test - 13-byte keys - 37.50 cycles/hash
Small key speed test - 14-byte keys - 33.39 cycles/hash
Small key speed test - 15-byte keys - 37.92 cycles/hash
Small key speed test - 16-byte keys - 30.33 cycles/hash
Small key speed test - 17-byte keys - 34.00 cycles/hash
Small key speed test - 18-byte keys - 34.02 cycles/hash
Small key speed test - 19-byte keys - 37.92 cycles/hash
Small key speed test - 20-byte keys - 34.20 cycles/hash
Small key speed test - 21-byte keys - 37.80 cycles/hash
Small key speed test - 22-byte keys - 37.98 cycles/hash
Small key speed test - 23-byte keys - 42.58 cycles/hash
Small key speed test - 24-byte keys - 34.29 cycles/hash
Small key speed test - 25-byte keys - 38.74 cycles/hash
Small key speed test - 26-byte keys - 37.29 cycles/hash
Small key speed test - 27-byte keys - 41.00 cycles/hash
Small key speed test - 28-byte keys - 37.65 cycles/hash
Small key speed test - 29-byte keys - 41.00 cycles/hash
Small key speed test - 30-byte keys - 41.71 cycles/hash
Small key speed test - 31-byte keys - 45.84 cycles/hash
Average 32.871 cycles/hash

@vstakhov
Copy link
Author

vstakhov commented Dec 3, 2016

--- Testing metrohash64crc_1 "MetroHash64crc_1 for x64"

[[[ Sanity Tests ]]]

Verification value 0x29C68A50 : PASS
Running sanity check 1 ..........PASS
Running AppendedZeroesTest..........PASS

[[[ Speed Tests ]]]

Bulk speed test - 262144-byte keys
Alignment 7 - 10.785 bytes/cycle - 30857.32 MiB/sec @ 3 ghz
Alignment 6 - 7.986 bytes/cycle - 22848.70 MiB/sec @ 3 ghz
Alignment 5 - 9.084 bytes/cycle - 25990.22 MiB/sec @ 3 ghz
Alignment 4 - 8.705 bytes/cycle - 24904.86 MiB/sec @ 3 ghz
Alignment 3 - 9.312 bytes/cycle - 26641.40 MiB/sec @ 3 ghz
Alignment 2 - 9.567 bytes/cycle - 27372.12 MiB/sec @ 3 ghz
Alignment 1 - 10.151 bytes/cycle - 29042.75 MiB/sec @ 3 ghz
Alignment 0 - 9.258 bytes/cycle - 26486.22 MiB/sec @ 3 ghz
Average - 9.356 bytes/cycle - 26767.95 MiB/sec @ 3 ghz

Small key speed test - 1-byte keys - 18.80 cycles/hash
Small key speed test - 2-byte keys - 19.63 cycles/hash
Small key speed test - 3-byte keys - 25.01 cycles/hash
Small key speed test - 4-byte keys - 19.15 cycles/hash
Small key speed test - 5-byte keys - 24.92 cycles/hash
Small key speed test - 6-byte keys - 24.00 cycles/hash
Small key speed test - 7-byte keys - 30.76 cycles/hash
Small key speed test - 8-byte keys - 25.38 cycles/hash
Small key speed test - 9-byte keys - 34.20 cycles/hash
Small key speed test - 10-byte keys - 30.89 cycles/hash
Small key speed test - 11-byte keys - 36.45 cycles/hash
Small key speed test - 12-byte keys - 30.68 cycles/hash
Small key speed test - 13-byte keys - 36.88 cycles/hash
Small key speed test - 14-byte keys - 44.51 cycles/hash
Small key speed test - 15-byte keys - 42.52 cycles/hash
Small key speed test - 16-byte keys - 29.52 cycles/hash
Small key speed test - 17-byte keys - 35.43 cycles/hash
Small key speed test - 18-byte keys - 35.57 cycles/hash
Small key speed test - 19-byte keys - 42.90 cycles/hash
Small key speed test - 20-byte keys - 35.00 cycles/hash
Small key speed test - 21-byte keys - 41.88 cycles/hash
Small key speed test - 22-byte keys - 47.02 cycles/hash
Small key speed test - 23-byte keys - 47.26 cycles/hash
Small key speed test - 24-byte keys - 33.50 cycles/hash
Small key speed test - 25-byte keys - 39.33 cycles/hash
Small key speed test - 26-byte keys - 39.16 cycles/hash
Small key speed test - 27-byte keys - 46.94 cycles/hash
Small key speed test - 28-byte keys - 40.27 cycles/hash
Small key speed test - 29-byte keys - 45.88 cycles/hash
Small key speed test - 30-byte keys - 45.00 cycles/hash
Small key speed test - 31-byte keys - 51.64 cycles/hash
Average 35.487 cycles/hash

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment