This is going to be a tracker for discussion, questions, feedback, and analyses about the new XXH3 hashes, found in the xxh3 branch.
@Cyan4973's comments (from xxhash.h):
XXH3 is a new hash algorithm, featuring vastly improved speed performance for both small and large inputs.
A full speed analysis will be published, it requires a lot more space than this comment can handle.
In general, expect XXH3 to run about ~2x faster on large inputs, and >3x faster on small ones, though exact difference depend on platform.
The algorithm is portable, will generate the same hash on all platforms. It benefits greatly from vectorization units, but does not require it.
XXH3 offers 2 variants, _64bits and _128bits.
The first 64-bits field of the _128bits variant is the same as _64bits result. However, if only 64-bits are needed, prefer calling the _64bits variant. It reduces the amount of mixing, resulting in faster speed on small inputs.
The XXH3 algorithm is still considered experimental. It's possible to use it for ephemeral data, but avoid storing long-term values for later re-use. While labelled experimental, the produced result can still change between versions.
The API currently supports one-shot hashing only. The full version will include streaming capability, and canonical representation Long term optional feature may include custom secret keys, and secret key generation.
There are still a number of opened questions that community can influence during the experimental period. I'm trying to list a few of them below, though don't consider this list as complete.
XXH64() (aka big-endian).XXH32/XXH64, but may be more natural for little-endian platforms.XXH128_hash_t ?XXH128_hash_t which would be desirable ?_128bits variant is the same as the result of _64bits.XXH128_hash_t, in ways which may block other possibilities.doubleSeed).XXH128?len==0 : Currently, the result of hashing a zero-length input is the seed.XXH32/XXH64).Canonical representation : for the 64-bit variant, canonical representation is the same as XXH64() (aka big-endian).
Nothing is wrong with big endian output. I suggest for XXH3_64b, it will look like this (big endian):
0123456789abcdef-3 file.c
and XXH3_128b, this:
00112233445566778899aabbccddeeff-3 file.c
I say 2x big endian. That would be easiest to parse (in the case of being in a text file),
fscanf(hashfile, "%016llx%016llx-3", &hashLo, &hashHi);
and the easiest to output:
printf("%016llx%016llx-3\n", hashLo, hashHi);
Similar to how my XXH32a's canonical representation ended in -a, I think it makes sense for XXH3 to end in -3.
/* pointer or value? also, should we perhaps give a saturated subtraction for sorting
* functions that check values? */
XXH_PUBLIC_API int
XXH128_hash_cmp(const XXH128_hash_t *a, const XXH128_hash_t *b)
{
if (a->ll2 == b->ll2) {
if (a->ll1 == b->ll1) {
return 0;
} else if (a->ll1 < b->ll1) {
return -1;
} else {
return 1;
}
}
if (a->ll2 < b->ll2) {
return -1;
} else {
return 1;
}
}
/* xxhash.h */
#ifdef __cplusplus
static inline bool operator==(const XXH128_hash_t &a, const XXH128_hash_t &b) {
return XXH128_hash_cmp(&a, &b) == 0;
}
static inline bool operator!=(const XXH128_hash_t &a, const XXH128_hash_t &b) {
return XXH128_hash_cmp(&a, &b) != 0;
}
static inline bool operator>(const XXH128_hash_t &a, const XXH128_hash_t &b) {
return XXH128_hash_cmp(&a, &b) > 0;
}
static inline bool operator<(const XXH128_hash_t &a, const XXH128_hash_t &b) {
return XXH128_hash_cmp(&a, &b) < 0;
}
static inline bool operator<=(const XXH128_hash_t &a, const XXH128_hash_t &b) {
return XXH128_hash_cmp(&a, &b) <= 0;
}
static inline bool operator>=(const XXH128_hash_t &a, const XXH128_hash_t &b) {
return XXH128_hash_cmp(&a, &b) >= 0;
}
#endif /* __cplusplus */
should we perhaps give a saturated subtraction for sorting
That's a great idea !
pointer or value?
I prefer by value when structure is of limited size.
That's the case here : XXH128_hash_t is just 16-bytes long.
Regarding length == 0 return: I'd go for returning the seed (even if it is 0) instead of always returning 0. If one likes to differ the hashes of the same input data by providing a seed, you get still different hashes even if length == 0.
Pointer or value
I'd vote for passing by pointer the XXH128_hash_t structure. Using value will imply copying for 32bit systems. Even on 64bit systems, passing 2 structs might not be done in registers.
BTW: Why "ll1" and "ll2", IMHO it should be suffixed by "h" and "l".
regarding static U64 XXH3_mul128(U64 ll1, U64 ll2)
The Aarch32 code seems to be over-complicated for returning only the lower 64 bits.
GCC produces elegant and as as it looks like, correct code:
mul r3, r0, r3
mla r3, r2, r1, r3
umull r0, r1, r0, r2
add r1, r3, r1
It doesn't return the lower 64 bits, it adds the lower bits to the higher bits. This is pretty much the best way of doing it.
You can see it in the GCC extension code:
__uint128_t lll = (__uint128_t)ll1 * ll2;
return (U64)lll + (U64)(lll >> 64);
or if we break it up:
__uint128_t ll1_u128 = (__uint128_t) ll1; // cast to __uint128_t
__uint128_t ll2_u128 = (__uint128_t) ll2; // promoted
__uint128_t lll = ll1_u128 * ll2_u128; // long multiply
U64 lll_hi = (U64) (lll >> 64); // high bits
U64 lll_lo = (U64) (lll & 0xFFFFFFFFFFFFFFFFULL); // low bits
return lll_hi + lll_lo; // 64-bit add together
In x86_64 assembly, we get this:
_mul128:
mov rax, rsi
mul rdi # note: rax stores high bits now
add rax, rdx
ret
The reason I use inline assembly is because neither GCC nor Clang will emit the right code and prefer to spew out nonsense, and the __uint128_t type is not available on 32-bit.
The code is quite efficient:
umull r12, lr, r0, r2
mov r5, #0
mov r4, #0
umaal r5, lr, r1, r2
umaal r5, r4, r0, r3
umaal lr, r4, r1, r3
adds r0, lr, r12
adc r1, r4, r5
TBH XXH3_mul128 should be renamed to something like XXH3_foldedMult64to128 to match XXH_mult32to64 to make it clear that this is a "folding" multiply and not just a superoptimized 64->128-bit multiply.
I also kinda agree about the pointer thing. On 32-bit, those two structs will take up 8 registers. ARM for example can only pass up to 4 in a function call before it has to push to the stack. And x86 only has 7 registers.
Actually, I benchmarked it via qsort, and it seems like passing value is in fact better on both 32-bit and 64-bit (for x86, haven't tested ARM yet):
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <string.h>
typedef struct {
uint64_t ll1;
uint64_t ll2;
} XXH128_hash_t;
__attribute__((__noinline__)) int
XXH128_hash_cmp_ptr(const XXH128_hash_t *a, const XXH128_hash_t *b)
{
if (a->ll2 == b->ll2) {
if (a->ll1 == b->ll1) {
return 0;
} else if (a->ll1 < b->ll1) {
return -1;
} else {
return 1;
}
}
if (a->ll2 < b->ll2) {
return -1;
} else {
return 1;
}
}
__attribute__((__noinline__)) int
XXH128_hash_cmp(const XXH128_hash_t a, const XXH128_hash_t b)
{
if (a.ll2 == b.ll2) {
if (a.ll1 == b.ll1) {
return 0;
} else if (a.ll1 < b.ll1) {
return -1;
} else {
return 1;
}
}
if (a.ll2 < b.ll2) {
return -1;
} else {
return 1;
}
}
int XXH128_hash_cmp_ptr_qsort(const void *start, const void *end)
{
return XXH128_hash_cmp_ptr((const XXH128_hash_t *)start, (const XXH128_hash_t *)end);
}
int XXH128_hash_cmp_qsort(const void *start, const void *end)
{
return XXH128_hash_cmp(*(const XXH128_hash_t *)start, *(const XXH128_hash_t *)end);
}
#define ROUNDS 1000000
static XXH128_hash_t arr[ROUNDS];
static XXH128_hash_t *arr_p[ROUNDS];
int main()
{
srand(time(NULL));
printf("arch: %zu-bit\n", sizeof(void *) * 8);
for (int i = 0; i < ROUNDS; i++) {
arr[i].ll1 = rand() | (uint64_t)rand() << 32;
arr[i].ll2 = rand() | (uint64_t)rand() << 32;
arr_p[i] = malloc(sizeof(XXH128_hash_t));
memcpy(arr_p[i], &arr[i], sizeof(XXH128_hash_t));
}
double start, end;
start = (double)clock();
qsort(arr, ROUNDS, sizeof(XXH128_hash_t), XXH128_hash_cmp_qsort);
end = (double)clock();
printf("pass by value: %lf\n", (end - start) / CLOCKS_PER_SEC);
start = (double)clock();
qsort(arr_p, ROUNDS, sizeof(XXH128_hash_t *), XXH128_hash_cmp_ptr_qsort);
end = (double)clock();
printf("pass by pointer: %lf\n", (end - start) / CLOCKS_PER_SEC);
}
arch: 32-bit
pass by value: 0.352646
pass by pointer: 0.526951
arch: 64-bit
pass by value: 0.198776
pass by pointer: 0.449999
(note: compiled with clang 7.0.1 on a 2.0 GHz 2nd Gen Core i7, -O3)
GCC 8.3:
arch: 32-bit
pass by value: 0.442356
pass by pointer: 0.547503
arch: 64-bit
pass by value: 0.175436
pass by pointer: 0.360158
On ARM64 there are enough registers for ABI to pass it as value (r0..r7), but for 32Bit ARM the pointer-version is better as there are only 4 registers.
So it highly depends on the CPU and the ABI.
Edit: I checked, x64-GCC ABI uses four registers, so just enough to pass the two structs as value.
Nevermind that, this is the way to do it:
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <string.h>
typedef struct {
uint64_t ll1;
uint64_t ll2;
} XXH128_hash_t;
__attribute__((__noinline__)) int
XXH128_hash_cmp_ptr(const XXH128_hash_t *a, const XXH128_hash_t *b)
{
if (a->ll2 == b->ll2) {
if (a->ll1 == b->ll1) {
return 0;
} else if (a->ll1 < b->ll1) {
return -1;
} else {
return 1;
}
}
if (a->ll2 < b->ll2) {
return -1;
} else {
return 1;
}
}
__attribute__((__noinline__)) int
XXH128_hash_cmp(const XXH128_hash_t a, const XXH128_hash_t b)
{
if (a.ll2 == b.ll2) {
if (a.ll1 == b.ll1) {
return 0;
} else if (a.ll1 < b.ll1) {
return -1;
} else {
return 1;
}
}
if (a.ll2 < b.ll2) {
return -1;
} else {
return 1;
}
}
int XXH128_hash_cmp_ptr_qsort(const void *start, const void *end)
{
return XXH128_hash_cmp_ptr(*(const XXH128_hash_t **)start, *(const XXH128_hash_t **)end);
}
int XXH128_hash_cmp_qsort(const void *start, const void *end)
{
return XXH128_hash_cmp(*(const XXH128_hash_t *)start, *(const XXH128_hash_t *)end);
}
#define ROUNDS 10000000
static XXH128_hash_t arr[ROUNDS];
static XXH128_hash_t *arr_p[ROUNDS];
static XXH128_hash_t arr_p_alt[ROUNDS];
int main()
{
srand(time(NULL));
printf("arch: %zu-bit\n", sizeof(void *) * 8);
for (int i = 0; i < ROUNDS; i++) {
arr[i].ll1 = rand() | (uint64_t)rand() << 32;
arr[i].ll2 = rand() | (uint64_t)rand() << 32;
arr_p[i] = malloc(sizeof(XXH128_hash_t));
memcpy(arr_p[i], &arr[i], sizeof(XXH128_hash_t));
memcpy(&arr_p_alt[i], &arr[i], sizeof(XXH128_hash_t));
}
double start, end;
start = (double)clock();
qsort(arr, ROUNDS, sizeof(XXH128_hash_t), XXH128_hash_cmp_qsort);
end = (double)clock();
printf("pass by value: %lf\n", (end - start) / CLOCKS_PER_SEC);
start = (double)clock();
qsort(arr_p, ROUNDS, sizeof(XXH128_hash_t *), XXH128_hash_cmp_ptr_qsort);
end = (double)clock();
printf("pass by pointer: %lf\n", (end - start) / CLOCKS_PER_SEC);
start = (double)clock();
qsort(arr_p_alt, ROUNDS, sizeof(XXH128_hash_t), (int (*)(const void *, const void *)) XXH128_hash_cmp_ptr);
end = (double)clock();
printf("direct pass to qsort: %lf\n", (end - start) / CLOCKS_PER_SEC);
}
(I increased the count to make it more noticable)
arch: 32-bit
pass by value: 4.095442
pass by pointer: 5.924909
direct pass to qsort: 3.096856
arch: 64-bit
pass by value: 2.489569
pass by pointer: 4.165021
direct pass to qsort: 2.178582
Use the pointer, and to use it for qsort, say
/* To use it as a comparator for qsort, bsearch, or the like, the recommended way to use this is to
* cast to int (*)(const void*, const void*). This has the best performance.
* qsort(array, size, sizeof(XXH128_hash_t), (int (*)(const void*, const void*)) XXH128_hash_cmp)
* This assumes an array of XXH128_hash_t values. */
Because a compare function for pointers is going to be the most important usage of this, as I presume it will be used in stuff like qsort and bsearch.
As for the C++ version, we are going to want to inline the comparisons, as it makes std::sort blazing fast:
static inline bool operator ==(const XXH128_hash_t &a, const XXH128_hash_t &b)
{
return (a.ll1 == b.ll1) && (a.ll2 == b.ll2);
}
static inline bool operator <(const XXH128_hash_t &a, const XXH128_hash_t &b)
{
if (a.ll2 == b.ll2) {
return a.ll1 < b.ll1;
} else {
return a.ll2 < b.ll2;
}
}
static inline bool operator !=(const XXH128_hash_t &a, const XXH128_hash_t &b)
{
return !(a == b);
}
static inline bool operator >(const XXH128_hash_t& a, const XXH128_hash_t& b)
{
return b < a;
}
static inline bool operator <=(const XXH128_hash_t& a, const XXH128_hash_t& b)
{
return !(a > b);
}
static inline bool operator >=(const XXH128_hash_t& a, const XXH128_hash_t& b)
{
return !(a < b);
}
And by passing by &, we are also passing by pointer. It is just syntax sugar.
arch: 32-bit
pass by value: 4.056218
pass by pointer: 5.928958
direct pass to qsort: 3.117807
std::sort: 2.620486
std::sort inlined: 2.486056
arch: 64-bit
pass by value: 2.375233
pass by pointer: 4.089312
direct pass to qsort: 2.440806
std::sort: 1.826079
std::sort inlined: 1.583563
Edit: the first std::sort uses this:
static inline bool operator<(const XXH128_hash_t &a, const XXH128_hash_t &b) {
return XXH128_hash_cmp_ptr(&a, &b) < 0;
}
Even better, and this is all C++11 compatible constexpr which while it isn't that important, it seems to help optimization a bit.
int
XXH128_hash_cmp_ptr(const XXH128_hash_t *a, const XXH128_hash_t *b)
{
if (a->ll2 == b->ll2) {
return (a->ll1 < b->ll1) ? -1 : (a->ll1 > b->ll1);
}
if (a->ll2 < b->ll2) {
return -1;
} else {
return 1;
}
}
static inline constexpr bool
operator ==(const XXH128_hash_t &a, const XXH128_hash_t &b)
{
return (a.ll1 == b.ll1) && (a.ll2 == b.ll2);
}
static inline constexpr bool
operator<(const XXH128_hash_t &a, const XXH128_hash_t &b)
{
#if (defined(_WIN32) || defined(__LITTLE_ENDIAN__)) && (defined(__SIZEOF_INT128__) || (defined(_INTEGRAL_MAX_BITS) && _INTEGRAL_MAX_BITS >= 128))
/* convert to uint128_t and compare */
return (a.ll1 | (static_cast<__uint128_t>(a.ll2) << 64))
< (b.ll1 | (static_cast<__uint128_t>(b.ll2) << 64));
#else
return (a.ll2 == b.ll2) ? (a.ll1 < b.ll1) : (a.ll2 < b.ll2);
#endif
}
static inline constexpr bool
operator !=(const XXH128_hash_t &a, const XXH128_hash_t &b)
{
return !(a == b);
}
static inline constexpr bool
operator >(const XXH128_hash_t& a, const XXH128_hash_t& b)
{
return b < a;
}
static inline constexpr bool
operator <=(const XXH128_hash_t& a, const XXH128_hash_t& b)
{
return !(a > b);
}
static inline constexpr bool
operator >=(const XXH128_hash_t& a, const XXH128_hash_t& b)
{
return !(a < b);
}
It is incredibly fast. Unfortunately, the uint128_t compare for the C-style sorting isn't as good as the other method.
arch: 32-bit
pass by value: 4.012220
direct pass to qsort: 3.027623
std::sort: 2.359985
std::sort by value: 2.335475
std::sort new: 2.096199
arch: 64-bit
pass by value: 2.185738
pass to qsort, u128_t compare: 2.127638
direct pass to qsort: 2.044731
std::sort: 1.629353
std::sort by value: 1.629171
std::sort new: 1.201221
On x86_64 with clang, operator < compiles to this:
__ZltRK13XXH128_hash_tS1_: ## @operator<(XXH128_hash_t const&, XXH128_hash_t const&)
mov rax, qword ptr [rdi]
mov rcx, qword ptr [rdi + 8]
cmp rax, qword ptr [rsi]
sbb rcx, qword ptr [rsi + 8]
setb al
ret
and on i386 it compiles to this:
__ZltRK13XXH128_hash_tS1_: ## @operator<(XXH128_hash_t const&, XXH128_hash_t const&)
push ebp
push ebx
push edi
push esi
mov esi, dword ptr [esp + 24]
mov ecx, dword ptr [esp + 20]
mov eax, dword ptr [ecx + 8]
mov edx, dword ptr [ecx + 12]
mov ebx, dword ptr [esi + 8]
mov edi, dword ptr [esi + 12]
mov ebp, edx
xor ebp, edi
mov esi, eax
xor esi, ebx
or esi, ebp
jne LBB5_2
mov eax, dword ptr [ecx]
mov ecx, dword ptr [ecx + 4]
mov edx, dword ptr [esp + 24]
cmp eax, dword ptr [edx]
sbb ecx, dword ptr [edx + 4]
jmp LBB5_3
LBB5_2:
cmp eax, ebx
sbb edx, edi
LBB5_3:
setb al
pop esi
pop edi
pop ebx
pop ebp
ret
Edit: GCC 8.3
arch: 32-bit
pass by value: 4.906234
direct pass to qsort: 3.260699
std::sort: 2.868732
std::sort by value: 2.862184
pass by pointer: 1.626228
arch: 64-bit
pass by value: 2.009833
pass to qsort, u128_t compare: 2.098546
direct pass to qsort: 1.861579
std::sort: 1.432066
std::sort by value: 1.489022
pass by pointer: 1.113134
Regarding static U64 XXH3_mul128(U64 ll1, U64 ll2)
The Aarch32 code seems to be over-complicated for returning only the lower 64 bits.
As mentioned by @easyaspi314 , it's bit a more than just returning the lower bits.
As the high bits get folded into the low bits, it _might_ be possible to write this operation more compactly, and not need a "real" 128-bits multiplication.
However, I did not figure out the math so far.
I'm fine with a rewrite of the function if it can lead to better performance.
If some gcc assembly can help reach this purpose, it's all fine.
XXH3_mul128 should be renamed to something like XXH3_foldedMult64to128
Good point
Consequences of implementing a comparator :
In saying that one hash value is "bigger" than the other one, it makes XXH128_hash_t more than a bit field. It is now necessary to distinguish its components, as they are no longer equal : one must be "high", and the other "low".
And now the order matters. Which one is high, which one is low ?
Possible answer :
In keeping the convention that internal components of XXH128_hash_t are XXH64_hash_t, for which the convention is big-endian, it feels consistent to continue using the same convention, making the first component "high", and the second "low".
Thoughts ?
Why "ll1" and "ll2", IMHO it should be suffixed by "h" and "l".
Yes, I agree.
If we are implementing a comparator function, components must be distinguished as "high" or "low".
In keeping the convention that internal components of
XXH128_hash_tareXXH64_hash_t, for which the convention is big-endian, it feels consistent to continue using the same convention, making the first component "high", and the second "low".
Thoughts ?
I'd go for this. This would be compatible with a natural uint128_t if it exists.
Why "ll1" and "ll2", IMHO it should be suffixed by "h" and "l".
Yes, I agree.
If we are implementing a comparator function, components must be distinguished as "high" or "low".
Also if you consider the struct as replacement for uint128_t
a natural
uint128_tif it exists
// 0x00112233445566778899AABBCCDDEEFF
const __uint128_t x = ((__uint128_t)0x0011223344556677ULL<< 64) | 0x8899AABBCCDDEEFFULL;
```
$ clang -O3 -c test.c
$ hexdump -C test.o
...
00000180 ff ee dd cc bb aa 99 88 77 66 55 44 33 22 11 00 |........wfUD3"..|
...
For uint128_t `0x00112233445566778899AABBCCDDEEFF`, the "natural" layout for most machines would be `0xFFEEDDCCBBAA99887766554433221100`.
Doing it this way would allow someone to theoretically do this on a 64-bit little endian machine:
```c
XXH128_hash_t hash = XXH3_128b(...);
__uint128_t val;
memcpy(&val, &hash, sizeof(__uint128_t));
Also if you consider the struct as replacement for uint128_t
It is supposed to be like one, and if the C standard had 128-bit integers, we would definitely use them. But it doesn't, and the only platforms that have it are 64-bit.
Yes, that's indeed the problem. At a binary level :
{ hi, lo } would have same byte order as __uint128_t on a big endian machine.{ lo, hi } would have same byte order as __uint128_t on a little endian machine.At a canonical level, I believe it makes sense to preserve the "natural" byte order, as if a __uint128_t could be displayed directly on screen. It makes "big endian" a natural choice. It follows the convention already established by XXH64_hash_t.
But binary and canonical levels do not have to match. Later on, a pair of conversion functions, such as XXH128_canonicalFromHash() will ensure that representation is always correct, whatever the platform.
So let's concentrate on binary level now, It would seem a matter to select which platform is more important, little or big endian. And these days, little endian is pretty much a winner.
That being said, even that does not matter much : __uint128_t is not an official type, and it's doubtful if it will ever be in the foreseeable future. So a binary compatibility (which would be limited to little endian platforms) seems of doubtful usefulness.
Consistency is also a topic.
{ hi, lo } feels to match the "natural" order expect by humans. That's how we write numbers !
I'm not opposed to { lo, hi }, I just suspect a few people will find it strange to read low before high.
But at the end of the day, both solutions work. As long as low and high are clearly expressed, it should be usable.
It's mostly a matter of picking one and sticking to it.
I'm fine with both.
Just trying to find a reason to "prefer" one over the other.
I went ahead and proceeded with renaming XXH128_hash_t members into low64 and high64.
This will hopefully makes it clearer for comparison purposes.
I used the little-endian binary convention, hence low first. I still don't have a strong reason to prefer one over the other, so I went with the easiest one.
I also believe it's not opposed to using big-endian for the canonical representation.
"by value" vs "by reference" :
I would really not feel too much concerned by a memcpy(,,16) operation. From a performance perspective, this should be unnoticeable. I have actually read reports that it's better from a cache locality perspective, as pointers into different memory areas will maintain active more cache lines, thus degrading system performance.
Moreover, whenever the comparator function can be inlined, it all becomes moot. One can expect the comparison to be performed directly on source data. Btw, maybe it's important to offer an inlinable comparator.
In contrast, I would feel more concerned by branches, which can be costly when they mispredict.
Hopefully, in this case, since 64-bit fields are compared, the likelihood of finding hashes with equal high64 fields becomes very low, making the branch extremely predictable.
If we do not constrain the comparator to return { -1, 0, 1 }, but more generally { <0, ==0, >0 }, we may be able to reduce the nb of branches in the comparator.
In this godbolt example, there is a comparison between a classical "branchy" comparator and a branchless one.
On 64-bit, the branchless variant looks good. It uses less instructions than the "branchy" one and avoids a cmov. I would expect it to run faster.
There is also a fully branchless comparator proposed at compare128_1(). It uses the same idea.
However, as mentioned before, it's unlikely that the high 64 bits of XXH128_hash_t are identical.
If that happens, it probably means that hashed object was effectively identical.
As predictable branches are extremely cheap, adding one to reduce amount of work is probably a good idea.
compare128_2() uses that fact to introduce a single branch, between high and low comparisons.
Now it's a matter of comparing these implementations...
I've used @easyaspi314 qsort benchmark script, and adapted it to measure differences between comparators. Here is the modified source code : https://gist.github.com/Cyan4973/e1baa1a9a32b690508df76be64b34082
Some conclusions :
I couldn't find any significant difference between the comparators. They all end up "within noise margin". I guess the comparator is only a small part of the sorting operation itself, so it doesn't matter much.
One indirection vs 2 indirections make a difference, though a moderate one (~10%).
Indeed, invoking the byPtr comparator directly is faster than invoking a wrapper using ptr arguments which itself calls the byValue comparator while ensuring this one is not inlined.
If it sounds like a win for byPtr, it's only because the test case mandates the use of byPtr. And when the byValue function can be inlined into the wrapper, it erases all differences.
So, the byPtr variant is a better fit for qsort, but is that an isolated example ?
I still believe that passing arguments by value feel more natural,
and that inlining is actually the most important key to performance.
There's an argument though for providing a comparator function "ready to use" with qsort. Even if isolated, it's still an important use case by itself.
typedef union {
struct {
uint64_t ll1;
uint64_t ll2;
};
struct {
/* don't use it directly! */
size_t __val[(sizeof(uint64_t)*2)/sizeof(size_t)];
};
} XXH128_hash_t;
int
XXH128_hash_cmp_ptr(const XXH128_hash_t *a, const XXH128_hash_t *b)
{
#if defined(__LITTLE_ENDIAN__) || defined(_WIN32)
/* Only compare the word sizes. This only works on little endian. */
int cmp;
size_t i = (sizeof(a->__val)/sizeof(a->__val[0]));
while (i-- > 0) {
cmp = (a->__val[i] > b->__val[i]) - (a->__val[i] < b->__val[i]);
if (cmp) {
return cmp;
}
}
return cmp;
#else
/* normal comparison, don't really care */
#endif
}
That has the best performance on 32-bit.
XXH128_hash_cmp_ptr_alt:
mov rax, qword ptr [rsi+0x8]
cmp qword ptr [rdi+0x8], rax
je L7
sbb eax, eax
or eax, 0x1
L1:
ret
L7:
mov rdx, QWORD PTR [rsi]
mov eax, 0x1
cmp QWORD PTR [rdi], rdx
ja L1
sbb eax, eax
ret
That clever bit of assembly has the best I've seen on 64-bit, and it is what GCC emits with the naive implementation:
__attribute__((__noinline__)) int
XXH128_hash_cmp_ptr(const XXH128_hash_t *a, const XXH128_hash_t *b)
{
if (a->high64 == b->high64) {
if (a->low64 > b->low64) {
return 1;
} else if (a->low64 < b->low64) {
return -1;
} else {
return 0;
}
}
if (a->high64 < b->high64) {
return -1;
} else {
return 1;
}
}
As for qsort: I guess the most impact comes from swaping the 128bit values if sorting does not use an array of pointers.
So for machines which have enough memory to hold thousands of hashes, the advantage of the one or the other way to call the compare function disappears in the noise.
Will there be createState/update/freeState APIs for XXH3?
Will there be createState/update/freeState APIs for XXH3?
Yes, that's basically next step.
Have you compared it with SeaHash
I wasn't aware of this hash, thanks for the link !
From its description, it says that it's a bit faster than XXH64, and that it's aimed at checksumming. Hence it's probably not optimized for small inputs. Also, 10% faster than XXH64 seems not enough to compete on speed with XXH3 on large inputs.
https://github.com/Cyan4973/xxHash/issues/180
There is currently a huge bug in the implementation, so some parts need to be redesigned.
I have to disagree with the mention of "huge bug" here.
I think we do not share the same view of the scope of a non-cryptographic hash function.
I maintain that a non-cryptographic hash should not even try to "resist" an attack, by adding layers of obfuscations that will just be defeated later on. In the meantime, there will always be a temptation to think "I don't understand what's going on in this algorithm; sure, it's labelled non-cryptographic, but (wink) it seems it's almost as good ", then it gets used in places where it should not, and a bit later, we've got an effective attack ready to roll on all these brittle implementations.
A non cryptographic algorithm should not hide the fact that it's non cryptographic, not even in its implementations. In the case of XXH3, it's trivial to figure out how to intentionally generate collisions, on condition of knowing the secret key and the seed. So sure, if one targets the default key and the default seed, it's just plain simple. For other algorithms, it may take a study to get there, but once the method is known, it's only a few clicks away, and infinite collision generation is a matter of a simple script.
The objective of a non-cryptographic hash algorithm is just to quickly generate a bunch of bits, to be used in a hash table, bloom filter, etc. The changes I'm implementing are aimed at the space reduction problem, which is far from severe. They will, as a side effect, make it a bit more difficult to generate intentional collisions, but it certainly does not make the algorithm any more secure, and is not the goal.
From a user perspective, the impact of this space reduction improvement is going to be minimal, if not completely unnoticeable.
The way I see it, we are tuning (and hopefully improving) the quality / performance trade-off. Which is precisely the point of this test period.
I commented on the announcement blog post, but this seems a more appropriate place to put this... I'm attempting a C# port here: https://github.com/Zhentar/xxHash3.NET/
I'm unfortunately finding it unexpectedly difficult just to match the performance of xxHash64 for large keys - even the SSE2 version is only on par with xxHash32
Unfortunately, C# is not my strong point. So I can't provide straightforward hints.
I wouldn't be surprised if there is a need to use some kind of "unsafe" interface, in order to remove a bunch of automated silent checks, which end up being quite significant in a hot loop.
How to do it is outside of my sphere of competence.
Maybe looking at the source code of a few other xxHash projects in C# might help.
Figured out how to get MSVC to spit out an optimized build of xxHash... maybe it's my hardware (i7-6600U), not my implementation:
XXH32 : 1000000 -> 5928 it/s ( 5653.5 MB/s)
XXH32 unaligned : 1000000 -> 6058 it/s ( 5777.1 MB/s)
XXH64 : 1000000 -> 11924 it/s (11372.1 MB/s)
XXH64 unaligned : 1000000 -> 11917 it/s (11365.2 MB/s)
XXH3_64bits : 1000000 -> 4778 it/s ( 4556.4 MB/s)
XXH3_64b unaligned : 1000000 -> 4082 it/s ( 3892.5 MB/s)
Just my 2cents: I come from safety not security, so I am looking for non-cryptographic hashes which at best outperform CRC32 in both speed and collision-freenes. It does not matter if one can generate collisions by knowing the seed or the key. But I want to be sure, that a bunch of changed bits will not lead to a good hash.
Replacing CRC32(C) which is currently used to verify files integrity is my goal too.
@Zhentar : I my experience, clang is _way_ better at optimizing vectorized code,
gcc is a distance second, generally not bad at SSE2 but definitively worse for AVX2 and NEON,
then msvc, which is lagging by a lot.
I don't have an i7-6600u platform to test on these days. If there is a possibility of a remote access, I'll be glad to investigate. In the meantime, I would recommend you to test clang. On Windows platform, the way I would proceed is to install the msys2 + mingw64 subsystem, then use the integrated package manager to install clang.
I will try to post a Windows binary of xxhsum in the release tab. With regards to XXH3, the only thing this Windows binary will offer is the benchmark module. Hopefully, it might be enough to get a sense of the target performance.
A known good reference build would be very helpful (even if it's a Linux build, though I would prefer Windows).
Unfortunately, the other C# xxHash ports did not have much to offer me in regards to optimization tips...
| Method | ByteLength | Mean | Throughput |
|----------------------- |----------- |----------------:|--------------:|
| Zhent_xxHash32 | 15 | 10.61 ns | 1,348.5 MB/s |
| xxHashSharp_xxHash32 | 15 | 10.96 ns | 1,305.1 MB/s |
| Zhent_xxHash64 | 15 | 13.55 ns | 1,056.1 MB/s |
| NeoSmart_xxHash64 | 15 | 114.19 ns | 125.3 MB/s |
| yyproj_xxHash64 | 15 | 199.12 ns | 71.8 MB/s |
| HashFunctions_xxHash64 | 15 | 317.77 ns | 45.0 MB/s |
| core20_xxHash64 | 15 | 531.48 ns | 26.9 MB/s |
| Zhent_xxHash64 | 1000000 | 82,298.71 ns | 11,588.0 MB/s |
| Zhent_xxHash32 | 1000000 | 144,697.68 ns | 6,590.8 MB/s |
| yyproj_xxHash64 | 1000000 | 587,337.64 ns | 1,623.7 MB/s |
| HashFunctions_xxHash64 | 1000000 | 1,093,433.89 ns | 872.2 MB/s |
| xxHashSharp_xxHash32 | 1000000 | 1,118,007.87 ns | 853.0 MB/s |
| NeoSmart_xxHash64 | 1000000 | 2,135,509.68 ns | 446.6 MB/s |
| core20_xxHash64 | 1000000 | 5,708,470.65 ns | 167.1 MB/s |
(note that this is a different machine than my previous post, I don't think my xxHash32 is actually meaningfully faster than yours)
I added 2 Windows binaries to the release tab,
one gcc + SSE2, and one clang + AVX2.
XXH3 is accessible through the benchmark module -b,
it will only provide speed numbers, not the hash value itself.
Thanks! That definitely helps. My initial impression is that clang's speed (at least with AVX2) comes from completely unrolling & inlining the block stripe accumulation loops, so that all of the key indexing can use immediate offsets.
I wonder, how does reducing the keyset size to 32 influence things for you? 8 stripes per block instead of 16 seems like it could be more friendly to less aggressive compilers.
I tried this suggestion of reducing the key size to reduce the loop size,
in the experience it made gcc-8 slightly better when using -march=native (but not -mavx2),
but clang became worse.
As a side-effect , both versions had similar performance, though clang was still leading by a small margin.
So it's not entirely win-win nor lose-lose, but since it reduces top performance by ~7%, I guess current key size and associated loop size still seem preferable.
clang's speed (at least with AVX2) comes from completely unrolling & inlining the block stripe accumulation loops, so that all of the key indexing can use immediate offsets.
did you checked that in the assembly ?
Yep. It's pretty impressive - all of XXH3_hashLong has just two dozen scalar instructions, with only three in the block loop.
But I managed to get my loop pretty close, with just six!
| Method | ByteLength | Mean | Throughput |
|------------ |----------- |---------:|--------------:|
| XxHash3AVX2 | 524288 | 16.25 us | 30,772.7 MB/s |
(clang's: XXH3_64b unaligned : 102400 -> 385931 it/s (37688.5 MB/s))
I think I know how to shrink that gap a touch, but it's going to make some already hideous code look even worse 😩
Build FAILED.
"/Users/user/xxHash3.NET/xxHash3.NET.sln" (default target) (1) ->
"/Users/user/xxHash3.NET/xxHash3/xxHash3.csproj" (default target) (2) ->
"/Users/user/xxHash3.NET/xxHash3/xxHash3.csproj" (Build target) (2:2) ->
(CoreCompile target) ->
xxHash3_SSE2.cs(3,22): error CS0234: The type or namespace name 'Intrinsics' does not exist in the namespace 'System.Runtime' (are you missing an assembly reference?) [/Users/user/xxHash3.NET/xxHash3/xxHash3.csproj]
xxHash3_SSE2.cs(4,22): error CS0234: The type or namespace name 'Intrinsics' does not exist in the namespace 'System.Runtime' (are you missing an assembly reference?) [/Users/user/xxHash3.NET/xxHash3/xxHash3.csproj]
Well, TIL, Mono doesn't have System.Runtime.Intrinsics.
😡
Hah, yeah, .NET Core 3.0-preview only at present. Did I screw up my #if define checks?
I had to fiddle with the config files so idk
either way, doesn't look like I'm trying it on my Mac today…
.NET Core is cross platform, macOS included 😃 You can grab the 3.0 preview here: https://dotnet.microsoft.com/download/dotnet-core/3.0 and then it should just be dotnet build -c Release to run a CLI build.
~/xxHash3.NET/xxHash3.Benchmarks/bin/Release/netcoreapp3.0 $ sudo ./xxHash3.Benchmarks
Password:
// Validating benchmarks:
// ***** BenchmarkRunner: Start *****
// ***** Found 1 benchmark(s) in total *****
// ***** Building 1 exe(s) in Parallel: Start *****
// ***** Done, took 00:00:00 (0.05 sec) *****
// Found 1 benchmarks:
// LongKeyTests.XxHash3AVX2: InProcess(MaxRelativeError=0.05, EnvironmentVariables=COMPlus_TieredCompilation=0, Toolchain=InProcessToolchain) [ByteLength=524288]
// **************************
// Benchmark: LongKeyTests.XxHash3AVX2: InProcess(MaxRelativeError=0.05, EnvironmentVariables=COMPlus_TieredCompilation=0, Toolchain=InProcessToolchain) [ByteLength=524288]
// *** Execute ***
// Launch: 1 / 1
// Benchmark Process Environment Information:
// Runtime=.NET Core 3.0.0-preview-27122-01 (CoreCLR 4.6.27121.03, CoreFX 4.7.18.57103), 64bit RyuJIT
// GC=Concurrent Workstation
// Job: InProcess(MaxRelativeError=0.05, EnvironmentVariables=COMPlus_TieredCompilation=0, Toolchain=InProcessToolchain)
OverheadJitting 1: 1 op, 415857.00 ns, 415.8570 us/op
Unhandled Exception: System.InvalidOperationException: Benchmark LongKeyTests.XxHash3AVX2: InProcess(MaxRelativeError=0.05, EnvironmentVariables=COMPlus_TieredCompilation=0, Toolchain=InProcessToolchain) [ByteLength=524288] takes to long to run. Prefer to use out-of-process toolchains for long-running benchmarks.
at BenchmarkDotNet.Toolchains.InProcess.InProcessExecutor.Execute(ExecuteParameters executeParameters)
at BenchmarkDotNet.Running.BenchmarkRunnerClean.RunExecute(ILogger logger, BenchmarkCase benchmarkCase, BenchmarkId benchmarkId, IToolchain toolchain, BuildResult buildResult, IResolver resolver, IDiagnoser diagnoser, Boolean& success)
at BenchmarkDotNet.Running.BenchmarkRunnerClean.Execute(ILogger logger, BenchmarkCase benchmarkCase, BenchmarkId benchmarkId, IToolchain toolchain, BuildResult buildResult, IResolver resolver)
at BenchmarkDotNet.Running.BenchmarkRunnerClean.RunCore(BenchmarkCase benchmarkCase, BenchmarkId benchmarkId, ILogger logger, IResolver resolver, BuildResult buildResult)
at BenchmarkDotNet.Running.BenchmarkRunnerClean.Run(BenchmarkRunInfo benchmarkRunInfo, Dictionary`2 buildResults, IResolver resolver, ILogger logger, List`1 artifactsToCleanup, String rootArtifactsFolderPath, StartedClock& runChronometer)
at BenchmarkDotNet.Running.BenchmarkRunnerClean.Run(BenchmarkRunInfo[] benchmarkRunInfos)
at BenchmarkDotNet.Running.BenchmarkRunner.RunWithDirtyAssemblyResolveHelper(Type type, IConfig config)
at BenchmarkDotNet.Running.BenchmarkRunner.Run[T](IConfig config)
at xxHash3.Program.Main() in /Users/user/xxHash3.NET/xxHash3.Benchmarks/Program.cs:line 31
Abort trap: 6
🤔
I don't have AVX2 (I have Sandy Bridge), but I changed it to UseSse2…
It's not like it's doing anything, it only is doing about 3% CPU.
Managed to close the gap quite a bit! Manually mimicked some of the optimizations clang made, along with realizing that using a 512kb test buffer on a processor with a 512kb L2 cache was maybe not without downsides.
| Method | ByteLength | Mean | Error | StdDev | Throughput |
|------------ |----------- |----------:|----------:|----------:|--------------:|
| XxHash3AVX2 | 102400 | 2.686 us | 0.0337 us | 0.0281 us | 36,354.0 MB/s |
| XxHash3AVX2 | 524288 | 15.269 us | 0.2233 us | 0.2089 us | 32,745.5 MB/s |
I also realized Clang did a bit more than I realized - it also completely de-shingled the keys array to get all the keys loads aligned, and even pre-computed the key shuffle in the accumulator scramble.
@easyaspi314
Hmmm. The next line you're supposed to see is this:
OverheadJitting 1: 1 op, 314000.00 ns, 314.0000 us/op
WorkloadJitting 1: 1 op, 14012400.00 ns, 14.0124 ms/op
Which means it's freezing while trying to JIT compile the code 😬 I haven't transferred any of my AVX2 learnings to the SSE2 code yet though, so that part isn't so fast yet anyway.
Clang is pretty clever. Usually.
GCC too (although it has its weaknesses).
MSVC stands true to its name:
MSVC
Sucks at
Vectorizing
Code
A lot of the times when I am optimizing SIMD code, I use the compiler output from GCC and Clang targeting different arches, and apply them back and forth. So, I get it.
314000.00 ns, 314.0000 us/op
I see what you did there 😆
I'm no C# developer, so I don't know how much help I can be.
Any news?
I'm completing a 64-bit collision analyzer.
It's able to generate and detect collisions using enough hashes to provide meaningful results and therefore judge the quality of any 64-bit hash algorithm.
The default test generates 24 billions hashes, and needs at least 64 GB of RAM to run properly.
The tool will make it possible to check that XXH3_64bits() has indeed the collision resistance of an "ideal" 64-bit hash algorithm.
It will be also used later in the refactoring of XXH3_128bits(), to prove that it has _better_ collision resistance than 64-bits variants.
Unfortunately, it will not be able to directly measure the collision rate for 128 bits hashes, as the amount of resources needed is, well, unreasonable.
Translating my AVX2 optimizations to SSE2 got it nice and performant for me. Unfortunately scalar continues to kick my ass. Think I'll call it good enough for now & wait for the updated algorithm to be a bit more finalized before evaluating & optimizing short keys.
| Method | ByteLength | Mean | Throughput |
|---------------- |----------- |----------:|--------------:|
| xxHash64_Scalar | 102400 | 8.390 us | 11,639.8 MB/s |
| xxHash3_AVX2 | 102400 | 2.444 us | 39,959.6 MB/s |
| xxHash3_SSE2 | 102400 | 4.917 us | 19,859.1 MB/s |
| xxHash3_Scalar | 102400 | 23.433 us | 4,167.5 MB/s |
( @easyaspi314 - it's effectively a completely new set of SSE2 code, so there's a fair chance whatever caused your hang has resolved itself )
Huh. Apparently, System.Runtime.Intrinsics.X86.Bmi2.X64.MultiplyNoFlags will cause a hang on the first preview. I had to find that out the hard way because apparently the debugger hates me and won't let me pause.
I updated to preview3, and it worked fine. I honestly didn't even realize I was on the wrong preview.
// * Summary *
BenchmarkDotNet=v0.11.4, OS=macOS Mojave 10.14.2 (18C54) [Darwin 18.2.0]
Intel Core i7-2635QM CPU 2.00GHz (Sandy Bridge), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.0.100-preview3-010431
[Host] : .NET Core 3.0.0-preview3-27503-5 (CoreCLR 4.6.27422.72, CoreFX 4.7.19.12807), 64bit RyuJIT
Job-RNHJPJ : .NET Core 3.0.0-preview3-27503-5 (CoreCLR 4.6.27422.72, CoreFX 4.7.19.12807), 64bit RyuJIT
MaxRelativeError=0.05 EnvironmentVariables=COMPlus_TieredCompilation=0
| Method | ByteLength | Mean | Error | StdDev | Throughput |
|---------------- |----------- |----------:|----------:|----------:|--------------:|
| xxHash64_Scalar | 102400 | 16.766 us | 0.1894 us | 0.1772 us | 5,824.8 MB/s |
| xxHash3_AVX2 | 102400 | 6.826 us | 0.0369 us | 0.0345 us | 14,306.4 MB/s |
| xxHash3_SSE2 | 102400 | 6.831 us | 0.0400 us | 0.0355 us | 14,296.1 MB/s |
| xxHash3_Scalar | 102400 | 34.039 us | 0.3778 us | 0.3534 us | 2,868.9 MB/s |
For the reference, I made this change, which I highly suggest you do:
#if NETCOREAPP3_0
if (System.Runtime.Intrinsics.X86.Avx2.IsSupported && UseAvx2)
{
LongSequenceHash_AVX2(ref acc2, data);
}
// fall back to SSE2 if we request AVX2 on an unsupported machine.
else if (System.Runtime.Intrinsics.X86.Sse2.IsSupported && (UseSse2 || UseAvx2))
{
LongSequenceHash_SSE2(ref acc2, data);
}
else
#endif
{
LongSequenceHash_Scalar(ref acc2, data);
}
Unrolling XXH64 8 times seems to help a little bit, although it could just be fluctuations.
Here are the results compared with native.
| Method | ByteLength | Mean | Error | StdDev | Throughput |
|---------------- |----------- |----------:|----------:|----------:|--------------:|
| xxHash64_Scalar | 102400 | 15.441 us | 0.1430 us | 0.1268 us | 6,324.4 MB/s |
| xxHash3_SSE2 | 102400 | 6.912 us | 0.0885 us | 0.0785 us | 14,129.3 MB/s |
| xxHash3_Scalar | 102400 | 33.865 us | 0.1445 us | 0.1207 us | 2,883.7 MB/s |
| XXH64_Native (clang -march=sandybridge, inline asm hack) | 102400 | 12.470 us | 0.0742 us | 0.0694 us | 7,831.0 MB/s |
| XXH3_Native (clang -march=sandybridge) | 102400 | 6.185 us | 0.0356 us | 0.0315 us | 15,789.8 MB/s |
| XXH64_Native (clang -march=x86-64, no inline asm) | 102400 | 14.538 us | 0.1167 us | 0.1092 us | 6,717.1 MB/s |
| XXH3_Native (clang -march=x86-64) | 102400 | 6.323 us | 0.0391 us | 0.0347 us | 15,444.9 MB/s |
Note: The inline assembly hack was this:
static U64 XXH64_round(U64 acc, U64 input)
{
__asm__(
"imulq %[PRIME64_2], %[input]\n"
"addq %[input], %[acc]\n"
"shldq $31, %[acc], %[acc]\n"
"imulq %[PRIME64_1], %[acc]"
: [acc] "+r" (acc), [input] "+r" (input)
: [PRIME64_1] "r" (PRIME64_1), [PRIME64_2] "r" (PRIME64_2)
);
return acc;
}
This is because while Clang will properly tune to use shld on Sandy Bridge (it has better throughput than rol for some reason), it improperly generates 4 excess mov instructions at the bottom of the loop for no reason.
Either way, that is very nice performance, good job!
Edit: How I interfaced with native:
[DllImport("/Users/user/xxh3-fix/libxxhash.dylib", CallingConvention = CallingConvention.Cdecl)]
internal extern static ulong XXH64(byte[] data, UIntPtr length, ulong seed);
[DllImport("/Users/user/xxh3-fix/libxxhash.dylib", CallingConvention = CallingConvention.Cdecl)]
internal extern static ulong XXH3_64bits(byte[] data, UIntPtr length);
[Benchmark]
public unsafe ulong XXH64_Native()
{
return XXH64(_bytes, (UIntPtr)_bytes.Length, 0);
}
[Benchmark]
public unsafe ulong XXH3_Native()
{
return XXH3_64bits(_bytes, (UIntPtr)_bytes.Length);
}
internal extern :thinking:
Scalar isn't that fast, tbh.
The reason XXH3 is so fast is because it takes advantage of SSE2 and NEON which are guaranteed to be supported in all modern desktop and mobile CPUs.
The scalar version was made to be decent, and it is pretty decent in most scenarios.
But, yeah, for perspective, this is what XXH3 looks like on the native one with no SSE2:
clang -march=x86-64 -O3 -DXXH_VECTORIZE=0 -mno-sse # had to remove for xxhsum
./xxhsum 0.7.0 (64-bits x86_64 + SSE2 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 42755 it/s ( 4175.3 MB/s)
XXH32 unaligned : 102400 -> 42980 it/s ( 4197.3 MB/s)
XXH64 : 102400 -> 69066 it/s ( 6744.8 MB/s)
XXH64 unaligned : 102400 -> 67172 it/s ( 6559.7 MB/s)
XXH3_64bits : 102400 -> 47720 it/s ( 4660.1 MB/s)
XXH3_64b unaligned : 102400 -> 45991 it/s ( 4491.3 MB/s)
clang -m32 -O3 -DXXH_VECTORIZE=0 -mno-sse
./xxhsum 0.7.0 (32-bits i386 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 35037 it/s ( 3421.6 MB/s)
XXH32 unaligned : 102400 -> 34626 it/s ( 3381.4 MB/s)
XXH64 : 102400 -> 13667 it/s ( 1334.6 MB/s)
XXH64 unaligned : 102400 -> 13618 it/s ( 1329.9 MB/s)
XXH3_64bits : 102400 -> 24640 it/s ( 2406.2 MB/s)
XXH3_64b unaligned : 102400 -> 24091 it/s ( 2352.7 MB/s)
Considering that it is C#, I wouldn't be too worried about it, because most people are going to be running on x86_64.
Thanks, that is a helpful point of comparison; glad to see the gap between my version and the native version is a fair bit smaller than I had thought. But unfortunately since the SSE2 & AVX2 code requires .NET Core 3.0, C# executed by Mono or the plain old .NET Framework (i.e. the vast majority it today) will be using the scalar version, so I am still going to concern myself with optimizing it as much as possible.
@Cyan4973 @42Bastian @Zhentar @sergeevabc @ifduyue
Wanna try this snippet and make sure it detects features properly on x86/x86_64? Try as many compilers as possible.
#include <stdio.h>
#include <string.h>
#if defined(_MSC_VER) && (defined(_M_IX86) || defined(_M_AMD64) || defined(_M_X64))
# include <intrin.h>
# define CPUIDEX __cpuidex
# define CPUID __cpuid
#elif (defined(__GNUC__) || defined(__TINYC__)) && (defined(__i386__) || defined(__x86_64__))
static void CPUIDEX(int *cpuInfo, int function_id, int subfunction_id)
{
int eax, ecx;
eax = function_id;
ecx = subfunction_id;
__asm__ __volatile__("cpuid"
: "+a" (eax), "=b" (cpuInfo[1]), "=c" (ecx), "=d" (cpuInfo[3]));
cpuInfo[0] = eax;
cpuInfo[2] = ecx;
}
static void CPUID(int *cpuInfo, int function_id)
{
CPUIDEX(cpuInfo, function_id, 0);
}
#else
# warning "x86 or x86_64 please, add your compiler to the macros if needed and tell me"
static void CPUIDEX(int *cpuInfo, int function_id, int subfunction_id)
{
memset(cpuInfo, 0, 4 * sizeof(int));
}
static void CPUID(int *cpuInfo, int function_id)
{
memset(cpuInfo, 0, 4 * sizeof(int));
}
#endif
int main() {
int max, data[4];
CPUID(data, 0);
max = data[0];
if (max >= 1) {
CPUID(data, 1);
printf("sse2: %d\n", !!(data[3] & (1 << 26)));
printf("avx: %d\n", !!(data[2] & (1 << 28)));
}
if (max >= 7) {
CPUID(data, 7);
printf("avx2: %d\n", !!(data[1] & (1 << 5)));
}
return 0;
}
The collision analyzer has been put to good use during the week end.
It's a very precise tool, which makes it possible to observe subtle difference which are otherwise impossible to notice with "standard" test tools (aka smhasher and al.).
This leads to several small but key modifications in the algorithm, bringing it in line with maximal theoretical collision rate.
As part of the changes, the function mul128_fold64 has been slightly modified, to use ^ for folding instead of +. I could update most variants except the aarch64 one :
https://github.com/Cyan4973/xxHash/blob/xxh3/xxh3.h#L163
@easyaspi314 , would you mind having a look at it ? Thanks !
I have inserted a WIP CPU dispatcher into xxhsum. I have binaries for macOS and Linux here for both 32-bit and 64-bit. I am too lazy to start up my Windows PC, so lmk if you actually want a build.
The Linux binaries are static, and they should work in WSL.
xxhsum-binaries-linux-darwin.zip
If you run the benchmark, it should tell you what version of xxh3 it runs:
./xxhsum-darwin-i686 0.7.0 (32-bits i386 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 34108 it/s ( 3330.8 MB/s)
XXH32 unaligned : 102400 -> 33667 it/s ( 3287.8 MB/s)
XXH64 : 102400 -> 13455 it/s ( 1314.0 MB/s)
XXH64 unaligned : 102400 -> 13527 it/s ( 1321.0 MB/s)
1-XXH3_64bits : 102400 ->
Using HashLong version __XXH3_HASH_LONG_SSE2
XXH3_64bits : 102400 -> 158898 it/s (15517.4 MB/s)
XXH3_64b unaligned : 102400 -> 158204 it/s (15449.6 MB/s)
If you have a CPU with AVX2, it should say __XXH3_HASH_LONG_AVX2.
Edit: It is to be noted that these were compiled for generic i686 and generic x86-64. These all work on my system.
Also, sure I'll take a look at the multiply code.
I don't know if it is worth it to do the inline assembly for that. Pretty much the only aarch64 compilers are GCC or LLVM-based, and therefore it should have the __uint128_t.
MSVC for ARM/aarch64 is pretty much dead (was it ever alive 😛?), and besides, msvc uses a different syntax.
Tested Windows binaries I cross-compiled with mingw. (Cross compiling _for_ Windows? 🤯)
xxhsum-windows-binaries.zip reuploaded
Please test so I know that my dispatcher is working correctly; I currently have no idea if it is because I only have Sandy Bridge.
I'll test when I get home if my sister will ever give up her laptop. :joy:
Actually, works fine in wine.
It's picking SSE2 rather than AVX2 for me
Oh, I think I know the problem, it isn't clearing ecx. Here's a new one with Windows, Mac, and Linux binaries.
When I get home, I might see if I can find and boot my dinosaur Pentium III laptop with Windows 2000 to see if it chooses the scalar version just because.
Heh, the virtual desktop at my college has AVX2.

I can run a Windows 10 VM from a Mac laptop at work.
Here are some results :
.\xxhsum-windows-i686.exe -b5
xxhsum-windows-i686.exe 0.7.0 (32-bits i386 little endian), GCC 8.3.0, by Yann Collet
Sample of 100 KB...
1-XXH3_64bits : 102400 ->
Using HashLong version __XXH3_HASH_LONG_AVX2
XXH3_64bits : 102400 -> 512000 it/s (50000.0 MB/s)
.\xxhsum-windows-x86_64.exe -b5
xxhsum-windows-x86_64.exe 0.7.0 (64-bits x86_64 + SSE2 little endian), GCC 8.3.0, by Yann Collet
Sample of 100 KB...
1-XXH3_64bits : 102400 ->
Using HashLong version __XXH3_HASH_LONG_AVX2
XXH3_64bits : 102400 -> 513542 it/s (50150.5 MB/s)
So both versions correctly detect and use the AVX2 code path.
Cool. I'll make a branch.
By the way, I also made it so we only have to write the x86 code once with the power of…
( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( (M) (A) (C) (R) (O) (S) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )
#define XXH_CONCAT_2(x, y) x##y
#define XXH_CONCAT(x, y) XXH_CONCAT_2(x, y)
/* These macros and typedefs make it so we only have to write the x86 code once.
* SSE2 AVX2
* XXH_vec = __m128i __m256i
* XXH_MM(add_epi32) = _mm_add_epi32 _mm256_add_epi32
* XXH_MM_SI(loadu) = _mm_loadu_si128 _mm256_loadu_si256 */
#if XXH_VECTOR == XXH_AVX2
typedef __m256i XXH_vec;
# define XXH_MM(x) XXH_CONCAT(_mm256_, x)
# define XXH_MM_SI(x) XXH_MM(XXH_CONCAT(x, _si256))
#elif XXH_VECTOR == XXH_SSE2
typedef __m128i XXH_vec;
# define XXH_MM(x) XXH_CONCAT(_mm_, x)
# define XXH_MM_SI(x) XXH_MM(XXH_CONCAT(x, _si128))
#endif
/* lame, I know */
#define VEC_SIZE sizeof(XXH_vec)
XXH_FORCE_INLINE void
XXH3_accumulate_512(void *restrict acc, const void *restrict data, const void *restrict key)
{
#if (XXH_VECTOR == XXH_AVX2) || (XXH_VECTOR == XXH_SSE2)
assert(((size_t)acc) & (VEC_SIZE - 1) == 0);
{
ALIGN(VEC_SIZE) XXH_vec* const xacc = (XXH_vec *) acc;
const XXH_vec* const xdata = (const XXH_vec *) data;
const XXH_vec* const xkey = (const XXH_vec *) key;
size_t i;
for (i=0; i < STRIPE_LEN / VEC_SIZE; i++) {
XXH_vec const d = XXH_MM_SI(loadu) (xdata+i);
XXH_vec const k = XXH_MM_SI(loadu) (xkey+i);
XXH_vec const dk = XXH_MM_SI(xor) (d,k); /* uint32 dk[8] = {d0+k0, d1+k1, d2+k2, d3+k3, ...} */
XXH_vec const res = XXH_MM(mul_epu32) (dk, XXH_MM(shuffle_epi32) (dk, 0x31)); /* uint64 res[4] = {dk0*dk1, dk2*dk3, ...} */
XXH_vec const add = XXH_MM(add_epi64) (d, xacc[i]);
xacc[i] = XXH_MM(add_epi64) (res, add);
}
}
#else ...
}
XXH_FORCE_INLINE void
XXH3_scrambleAcc(void* restrict acc, const void* restrict key)
{
#if (XXH_VECTOR == XXH_AVX2) || (XXH_VECTOR == XXH_SSE2)
assert(((size_t)acc) & (VEC_SIZE - 1) == 0);
{
ALIGN(VEC_SIZE) XXH_vec* const xacc = (XXH_vec*) acc;
const XXH_vec* const xkey = (const XXH_vec*) key;
const XXH_vec k1 = XXH_MM(set1_epi32) ((int)PRIME32_1);
const XXH_vec k2 = XXH_MM(set1_epi32) ((int)PRIME32_2);
size_t i;
for (i=0; i < STRIPE_LEN / VEC_SIZE; i++) {
XXH_vec data = xacc[i];
XXH_vec const shifted = XXH_MM(srli_epi64) (data, 47);
data = XXH_MM_SI(xor) (data, shifted);
{
XXH_vec const k = XXH_MM_SI(loadu) (xkey+i);
XXH_vec const dk = XXH_MM_SI(xor) (data,k); /* U32 dk[4] = {d0+k0, d1+k1, d2+k2, d3+k3} */
XXH_vec const dk1 = XXH_MM(mul_epu32) (dk,k1);
XXH_vec const d2 = XXH_MM(shuffle_epi32) (dk, 0x31);
XXH_vec const dk2 = XXH_MM(mul_epu32) (d2,k2);
xacc[i] = XXH_MM_SI(xor) (dk1, dk2);
}
}
}
#else // ...
}
(I know I need to realign)
As for my Makefile logic, I have it so it will compile the multiple code paths if you add MULTI_TARGET=1 to make. IDK if we should do it by default or not, so for now it is optional.
Basically, the hashLong code is now in xxh3-target.c. If XXH_MULTI_TARGET is not defined, it will just be #included in xxh3.h, otherwise, it will be compiled 3 times to make xxh3-scalar.o, xxh3-avx,o, and xxh3-sse2.o.
# XXX: enable by default?
ifndef MULTI_TARGET
TARGET_OBJS :=
else
# Multi targeting only works for x86 and x86_64 right now.
ifneq (,$(filter __i386__ __x86_64__ _M_IX86 _M_X64 _M_AMD64,$(shell $(CC) -E -dM -xc /dev/null)))
TARGET_OBJS := xxh3-avx2.o xxh3-sse2.o xxh3-scalar.o
CFLAGS += -DXXH_MULTI_TARGET
else
TARGET_OBJS :=
endif
endif
xxhsum: xxhash.o xxhsum.o $(TARGET_OBJS)
xxh3-avx2.o: xxh3-target.c xxhash.h
$(CC) -c $(FLAGS) $< -mavx2 -o $@
xxh3-sse2.o: xxh3-target.c xxhash.h
$(CC) -c $(FLAGS) $< -msse2 -mno-sse3 -o $@
xxh3-scalar.o: xxh3-target.c xxhash.h
$(CC) -c $(FLAGS) $< -mno-sse2 -o $@
I was checking Agner Fog's timing tables and I think we should change pshufd to psrlq.
There is little to no difference on modern processors, but pshufd tends to be slower than psrlq on older chips:
| CPU | pshufd cycles | pshufd latency | psrlq cycles | psrlq latency |
|---------|---------|-------|------|------|
| AMD K8 | 3 | 3 | 2 | 2 |
| AMD K10 | 1 | 3 | 1 | 3 |
| AMD Big Rigs | 1 | 2 | 1 | 2 |
| AMD Ryzen+ | 2 | 1 | 2 | 1 |
| AMD Bobcat | 3 | 2 | 2 | 1 |
| AMD Jaguar | 1 | 2 | 1 | 1 |
| Intel Pentium 4 | 1 | 5 | 1 | 5 |
| Intel Pentium M | 3 | 2 | 2 | 2 |
| Intel Merom | 3 | 1 | 1 | 1 |
| Intel Penryn+ | 1 | 1 | 1 | 1 |
Wait, scratch that. Duh. pshufd is gonna be faster because it doesn't overwrite the source operand. SSE2 would need an extra movdqa with psrlq.
@Cyan4973 would this be a correct implementation of the (updated) scalar loops? Because even when compiled without SSE2 (I checked the assembly, all scalar instructions), I get about 6.6-7.0 GB/s this way on 64-bit compared to 5.3 with the previous method. The reason for this is this makes clang use 64-bit xor instructions instead of pairs of 32-bit xors.
Since this has nothing to bother 32-bit with (it will be doing everything with two registers anyways), it doesn't slow it down.
It only works with the XXH_readLE64 though, two XXH_readLE32s and an shift+or don't work.
XXH_FORCE_INLINE void
XXH3_accumulate_512(void *restrict acc, const void *restrict data, const void *restrict key)
{
U64* const xacc = (U64*) acc; /* presumed aligned */
const U32* const xdata = (const U32*) data;
const U32* const xkey = (const U32*) key;
size_t i;
for (i=0; i < ACC_NB; i++) {
U64 const data_val = XXH_readLE64(xdata + 2 * i);
U64 const key_val = XXH3_readKey64(xkey + 2 * i);
U64 const data_key = key_val ^ data_val;
xacc[i] += XXH_mult32to64(data_key & 0xFFFFFFFF, data_key >> 32);
xacc[i] += data_val;
}
}
XXH_FORCE_INLINE void
XXH3_scrambleAcc(void* restrict acc, const void* restrict key)
{
U64* const xacc = (U64*) acc;
const U32* const xkey = (const U32*) key;
size_t i;
for (i = 0; i < ACC_NB; i++) {
U64 const acc_val = xacc[i];
U64 const shifted = acc_val >> 47;
U64 const data = acc_val ^ shifted;
U64 const key_val = XXH3_readKey64(xkey + 2 * i);
U64 const data_key = key_val ^ data;
U64 const product1 = XXH_mult32to64(PRIME32_1, (data_key & 0xFFFFFFFF));
U64 const product2 = XXH_mult32to64(PRIME32_2, (data_key >> 32));
xacc[i] = product1 ^ product2;
}
}
@Zhentar this might be useful in your quest to optimize your C# implementation.
Looks great @easyaspi314 ,
the accumulate_512 function looks very good to me.
Sidenote : I'm modifying (again!) the scramble function, in a way which should be more friendly to scalar (though it's a side effect, the main objective is to nullify space reduction, which the new version seems to tackle completely). I'll update xxh3 branch later today.
_note_ : OK, I've got 2 possibilities for the scrambler.
I selected one which is slightly more friendly to the scalar version. It adds one operation in the vectorial version, but also saves one const register.
I've uploaded the new version, even though it's still undergoing quality testing. Collision rate is perfect, but I'm not yet sure of dispersion / bias.
_note 2_ : I tested your scalar variant of accumulate_512, and it's way better. 50% faster for gcc, and 2x faster for clang, which was already much faster than gcc to begin with. I suspect clang might autovectorize something in the new scalar path, because its resulting level of performance is better XXH64 (though not at the level of manual SSE2 variant).
You're killin' me, Smalls! :joy:
As for scalar, . And like I said, with the fixed version, it gets pretty nice performance; it is actually faster than XXH64 (although it is just a ruse, Clang generates 4 erroneous movs in the XXH64 loop bringing it down from 10.1 GB/s).
From what I saw, that full 64-bit multiply would be terrible for 32-bit. Full 64-bit multiplies were what slowed down XXH64.
U64 mult64(U64 a, U64 b)
{
return a * b;
}
mult64: # @mult64
push esi
mov ecx, dword ptr [esp + 16]
mov esi, dword ptr [esp + 8]
mov eax, ecx
imul ecx, dword ptr [esp + 12]
mul esi
imul esi, dword ptr [esp + 20]
add edx, ecx
add edx, esi
pop esi
ret
mult64:
push {r11, lr}
umull r12, lr, r2, r0
mla r1, r2, r1, lr
mla r1, r3, r0, r1
mov r0, r12
pop {r11, pc}
(That is two 32-bit multiplies, one 32->64-bit multiply, and two 32-bit adds).
With my version, code gen doesn't seem to be that bad on all platforms.
All x86_64 chips have SSE2 and all aarch64 chips have NEON, and with my fixes, XXH3 is very fast even without SSE2.
By the way, what do you think about my current version? I made a few (mostly aesthetic) changes:
static U64 XXH3_mul128_fold64(U64 ll1, U64 ll2)
{
__uint128_t lll = (__uint128_t)ll1 * ll2;
return (U64)lll ^ (U64)(lll >> 64);
}
Code:
XXH_FORCE_INLINE void
XXH3_accumulate_512(void *restrict acc, const void *restrict data, const void *restrict key)
{
#if (XXH_VECTOR == XXH_AVX2) || (XXH_VECTOR == XXH_SSE2)
assert(((size_t)acc) & (VEC_SIZE - 1) == 0);
{
ALIGN(VEC_SIZE) XXH_vec* const xacc = (XXH_vec *) acc;
const XXH_vec* const xdata = (const XXH_vec *) data;
const XXH_vec* const xkey = (const XXH_vec *) key;
size_t i;
for (i=0; i < STRIPE_LEN / VEC_SIZE; i++) {
/* data_vec = xdata[i]; */
XXH_vec const data_vec = XXH_MM_SI(loadu) (xdata + i);
/* key_vec = xkey[i]; */
XXH_vec const key_vec = XXH_MM_SI(loadu) (xkey + i);
/* data_key = data_vec ^ key_vec; */
XXH_vec const data_key = XXH_MM_SI(xor) (data_vec, key_vec);
/* shuffled = data_key[1, undef, 3, undef]; // essentially data_key >> 32; */
XXH_vec const shuffled = XXH_MM(shuffle_epi32) (data_key, 0x31);
/* product = (shuffled & 0xFFFFFFFF) * (data_key & 0xFFFFFFFF); */
XXH_vec const product = XXH_MM(mul_epu32) (shuffled, data_key);
/* xacc[i] += data_vec; */
xacc[i] = XXH_MM(add_epi64) (xacc[i], data_vec);
/* xacc[i] += product; */
xacc[i] = XXH_MM(add_epi64) (xacc[i], product);
}
}
#elif (XXH_VECTOR == XXH_NEON) /* to be updated, no longer with latest sse/avx updates */
assert(((size_t)acc) & 15 == 0);
{
uint64x2_t* const xacc = (uint64x2_t *) acc;
/* We don't use a uint32x4_t pointer because it causes bus errors on ARMv7. */
uint32_t const* const xdata = (const uint32_t *) data;
uint32_t const* const xkey = (const uint32_t *) key;
size_t i;
for (i=0; i < STRIPE_LEN / sizeof(uint64x2_t); i++) {
#if !defined(__aarch64__) && !defined(__arm64__) /* ARM32-specific hack */
/* vzip on ARMv7 Clang generates a lot of vmovs (technically vorrs) without this.
* vzip on 32-bit ARM NEON will overwrite the original register, and I think that Clang
* assumes I don't want to destroy it and tries to make a copy. This slows down the code
* a lot.
* aarch64 not only uses an entirely different syntax, but it requires three
* instructions...
* ext v1.16B, v0.16B, #8 // select high bits because aarch64 can't address them directly
* zip1 v3.2s, v0.2s, v1.2s // first zip
* zip2 v2.2s, v0.2s, v1.2s // second zip
* ...to do what ARM does in one:
* vzip.32 d0, d1 // Interleave high and low bits and overwrite. */
/* data_vec = xdata[i]; */
uint32x4_t const data_vec = vld1q_u32(xdata + (i * 4));
/* key_vec = xkey[i]; */
uint32x4_t const key_vec = vld1q_u32(xkey + (i * 4));
/* data_key = data_vec ^ key_vec; */
uint32x4_t data_key = veorq_u32(data_vec, key_vec);
/* Here's the magic. We use the quirkiness of vzip to shuffle data_key in place.
* shuffle: data_key[0, 1, 2, 3] = data_key[0, 2, 1, 3] */
__asm__("vzip.32 %e0, %f0" : "+w" (data_key));
/* xacc[i] += data_vec; */
xacc[i] = vaddq_u64(xacc[i], vreinterpretq_u64_u32(data_vec));
/* xacc[i] += (uint64x2_t) data_key[0, 1] * (uint64x2_t) data_key[2, 3]; */
xacc[i] = vmlal_u32(xacc[i], vget_low_u32(data_key), vget_high_u32(data_key));
#else
/* On aarch64, vshrn/vmovn seems to be equivalent to, if not faster than, the vzip method. */
/* data_vec = xdata[i]; */
uint32x4_t const data_vec = vld1q_u32(xdata + (i * 4));
/* key_vec = xkey[i]; */
uint32x4_t const key_vec = vld1q_u32(xkey + (i * 4));
/* data_key = data_vec ^ key_vec; */
uint32x4_t const data_key = veorq_u32(data_vec, key_vec);
/* data_key_lo = (uint32x2_t) (data_key & 0xFFFFFFFF); */
uint32x2_t const data_key_lo = vmovn_u64 (vreinterpretq_u64_u32(data_key));
/* data_key_hi = (uint32x2_t) (data_key >> 32); */
uint32x2_t const data_key_hi = vshrn_n_u64 (vreinterpretq_u64_u32(data_key), 32);
/* xacc[i] += data_vec; */
xacc[i] = vaddq_u64 (xacc[i], vreinterpretq_u64_u32(data_vec));
/* xacc[i] += (uint64x2_t) data_key_lo * (uint64x2_t) data_key_hi; */
xacc[i] = vmlal_u32 (xacc[i], data_key_lo, data_key_hi);
#endif
}
}
#else /* scalar variant - universal */
U64* const xacc = (U64*) acc; /* presumed aligned */
const U32* const xdata = (const U32*) data;
const U32* const xkey = (const U32*) key;
size_t i;
for (i=0; i < ACC_NB; i++) {
U64 const data_val = XXH_readLE64(xdata + 2 * i);
U64 const key_val = XXH3_readKey64(xkey + 2 * i);
U64 const data_key = key_val ^ data_val;
xacc[i] += XXH_mult32to64(data_key & 0xFFFFFFFF, data_key >> 32);
xacc[i] += data_val;
}
#endif
}
XXH_FORCE_INLINE void
XXH3_scrambleAcc(void* restrict acc, const void* restrict key)
{
#if (XXH_VECTOR == XXH_AVX2) || (XXH_VECTOR == XXH_SSE2)
assert(((size_t)acc) & (VEC_SIZE - 1) == 0);
{
ALIGN(VEC_SIZE)
XXH_vec * const xacc = (XXH_vec*) acc;
XXH_vec const* const xkey = (const XXH_vec*) key;
XXH_vec const prime1 = XXH_MM(set1_epi32) ((int) PRIME32_1);
XXH_vec const prime2 = XXH_MM(set1_epi32) ((int) PRIME32_2);
size_t i;
for (i=0; i < STRIPE_LEN / VEC_SIZE; i++) {
/* data_vec = xacc[i] ^ (xacc[i] >> 47); */
XXH_vec const acc_vec = xacc[i];
XXH_vec const shifted = XXH_MM(srli_epi64) (acc_vec, 47);
XXH_vec const data_vec = XXH_MM_SI(xor) (acc_vec, shifted);
/* key_vec = xkey[i]; */
XXH_vec const key_vec = XXH_MM_SI(loadu) (xkey + i);
/* data_key = data_vec ^ key_vec; */
XXH_vec const data_key = XXH_MM_SI(xor) (data_vec, key_vec);
/* shuffled = data_key[1, undef, 3, undef]; // essentially data_key >> 32; */
XXH_vec const shuffled = XXH_MM(shuffle_epi32) (data_key, 0x31);
/* product1 = (data_key & 0xFFFFFFFF) * (uint64x2_t) PRIME32_1; */
XXH_vec const product1 = XXH_MM(mul_epu32) (data_key, prime1);
/* product2 = (shuffled & 0xFFFFFFFF) * (uint64x2_t) PRIME32_2; */
XXH_vec const product2 = XXH_MM(mul_epu32) (shuffled, prime2);
/* xacc[i] = product1 ^ product2; */
xacc[i] = XXH_MM_SI(xor) (product1, product2);
}
}
#elif (XXH_VECTOR == XXH_NEON)
assert(((size_t)acc) & 15 == 0);
{
uint64x2_t* const xacc = (uint64x2_t*) acc;
uint32_t const* const xkey = (uint32_t const*) key;
uint32x2_t const prime1 = vdup_n_u32 (PRIME32_1);
uint32x2_t const prime2 = vdup_n_u32 (PRIME32_2);
size_t i;
for (i=0; i < STRIPE_LEN/sizeof(uint64x2_t); i++) {
/* data_vec = xacc[i] ^ (xacc[i] >> 47); */
uint64x2_t const acc_vec = xacc[i];
uint64x2_t const shifted = vshrq_n_u64 (acc_vec, 47);
uint64x2_t const data_vec = veorq_u64 (acc_vec, shifted);
/* key_vec = xkey[i]; */
uint32x4_t const key_vec = vld1q_u32 (xkey + (i * 4));
/* data_key = data_vec ^ key_vec; */
uint32x4_t const data_key = veorq_u32 (vreinterpretq_u32_u64(data_vec), key_vec);
/* shuffled = { data_key[0, 2], data_key[1, 3] }; */
uint32x2x2_t const shuffled = vzip_u32 (vget_low_u32(data_key), vget_high_u32(data_key));
/* product1 = (uint64x2_t) shuffled[0] * (uint64x2_t) PRIME32_1; */
uint64x2_t const product1 = vmull_u32 (shuffled.val[0], prime1);
/* product2 = (uint64x2_t) shuffled[1] * (uint64x2_t) PRIME32_2; */
uint64x2_t const product2 = vmull_u32 (shuffled.val[1], prime2);
/* xacc[i] = product1 ^ product2; */
xacc[i] = veorq_u64(product1, product2);
}
}
#else /* scalar variant - universal */
U64* const xacc = (U64*) acc;
const U32* const xkey = (const U32*) key;
size_t i;
for (i = 0; i < ACC_NB; i++) {
U64 const acc_val = xacc[i];
U64 const shifted = acc_val >> 47;
U64 const data = acc_val ^ shifted;
U64 const key_val = XXH3_readKey64(xkey + 2 * i);
U64 const data_key = key_val ^ data;
U64 const product1 = XXH_mult32to64(PRIME32_1, (data_key & 0xFFFFFFFF));
U64 const product2 = XXH_mult32to64(PRIME32_2, (data_key >> 32));
xacc[i] = product1 ^ product2;
}
#endif
}
Yes, I like your changes @easyaspi314, they help readability, it's a great positive.
Oh wait, I saw, you did a 64 by 32 multiply.
As for your code, x86_64 and aarch64 are much smaller, but 32-bit doesn't see as much of a difference.
However, the one I was using was faster on both i386 and x86_64-scalar:
32-bit:
My version: (clang -m32 -O3 -mno-sse2)
./xxhsum 0.7.0 (32-bits i386 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 34976 it/s ( 3415.6 MB/s)
XXH32 unaligned : 102400 -> 34427 it/s ( 3362.0 MB/s)
XXH64 : 102400 -> 13591 it/s ( 1327.2 MB/s)
XXH64 unaligned : 102400 -> 13418 it/s ( 1310.3 MB/s)
XXH3_64bits : 102400 -> 29382 it/s ( 2869.4 MB/s)
XXH3_64b unaligned : 102400 -> 29458 it/s ( 2876.7 MB/s)
Your new version:
./xxhsum 0.7.0 (32-bits i386 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 34746 it/s ( 3393.2 MB/s)
XXH32 unaligned : 102400 -> 34149 it/s ( 3334.9 MB/s)
XXH64 : 102400 -> 13632 it/s ( 1331.3 MB/s)
XXH64 unaligned : 102400 -> 13470 it/s ( 1315.4 MB/s)
XXH3_64bits : 102400 -> 25121 it/s ( 2453.2 MB/s)
XXH3_64b unaligned : 102400 -> 24559 it/s ( 2398.4 MB/s)
64-bit
My version: (clang -mno-sse2, it says SSE2 because clang messes up the benchmark without it)
./xxhsum 0.7.0 (64-bits x86_64 + SSE2 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 42382 it/s ( 4138.9 MB/s)
XXH32 unaligned : 102400 -> 42508 it/s ( 4151.1 MB/s)
XXH64 : 102400 -> 68385 it/s ( 6678.3 MB/s)
XXH64 unaligned : 102400 -> 67336 it/s ( 6575.8 MB/s)
XXH3_64bits : 102400 -> 60443 it/s ( 5902.6 MB/s)
XXH3_64b unaligned : 102400 -> 59623 it/s ( 5822.5 MB/s)
Your version:
./xxhsum 0.7.0 (64-bits x86_64 + SSE2 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 41963 it/s ( 4098.0 MB/s)
XXH32 unaligned : 102400 -> 42648 it/s ( 4164.9 MB/s)
XXH64 : 102400 -> 68673 it/s ( 6706.3 MB/s)
XXH64 unaligned : 102400 -> 67688 it/s ( 6610.1 MB/s)
XXH3_64bits : 102400 -> 48290 it/s ( 4715.8 MB/s)
XXH3_64b unaligned : 102400 -> 46441 it/s ( 4535.3 MB/s)
((My laptop was a little warm so it wasn't going into Turbo Boost)
Wait, clang was just not unrolling the loop. The result is a tiny bit faster.
32-bit:
XXH3_64bits : 102400 -> 30095 it/s ( 2939.0 MB/s)
XXH3_64b unaligned : 102400 -> 30123 it/s ( 2941.7 MB/s)
64-bit
XXH3_64bits : 102400 -> 63576 it/s ( 6208.6 MB/s)
XXH3_64b unaligned : 102400 -> 62257 it/s ( 6079.7 MB/s)
What are the differences between the versions tested ?
Is it limited to the scrambler ?
I'm not completely sure what is being measured.
I would expect most of the speed difference to come from the new accumulator, which I already acknowledged is a much faster variant.
But that doesn't tell us much about the scrambler. I would expect the speed difference attributed to the scrambler to be pretty small, if measurable at all.
_P.S_ : I made some tests by integrating your new accumulator, comparing the new and the old scrambler. Differences are small but measurable
|variant | old | new | diff |
| --- | --- | --- | --- |
| clang x64 | 17100 MB/s | 17700 MB/s | + |
| clang -m32 | 17100 MB/s | 17000 MB/s | - |
| clang -m32 -no-sse2 | 4900 MB/s | 5050 MB/s | + |
| gcc x64 | 9550 MB/s | 9650 MB/s | + |
| gcc -m32 | 3650 MB/s | 3600 MB/s | - |
| gcc -m32 -no-sse2 | 3600 MB/s | 3600 MB/s | = |
Yeah, the first version was my working tree vs your tree, but that last one was on my tree, differing only in the scrambler.
Clang was notably bitching about not being able to unroll the loop…
Yes, the same Clang that does this (it will unroll thousands of times, it has no limit)
Also, for some reason, my laptop was warm because there were rogue dotnet benchmarks running in the background and the processes were locking my CPU into Turbo Boost.
why
Also, does GCC have SSE2 enabled? Try -msse2. I knew GCC was bad, but I didn't know it was that bad.
Well, turning on -msse2 with -m32 on gcc is actually even worse :
speed goes down to 1100 MB/s
Whaaaaat?
~/xxh3 $ gcc-8 -m32 -mno-sse3 -msse2 -DXXH_VECTOR=0 -c -O3 xxhash.c
~/xxh3 $ gcc-8 -m32 -mno-sse3 -msse2 -DXXH_VECTOR=0 -c -O3 xxhsum.c
~/xxh3 $ clang *.o -m32 -o xxhsum
ld: warning: The i386 architecture is deprecated for macOS (remove from the Xcode build setting: ARCHS)
ld: warning: ignoring file /usr/local/Cellar/llvm/8.0.0/lib/clang/8.0.0/lib/darwin/libclang_rt.osx.a, missing required architecture i386 in file /usr/local/Cellar/llvm/8.0.0/lib/clang/8.0.0/lib/darwin/libclang_rt.osx.a (2 slices)
~/xxh3 $ ./xxhsum -b
./xxhsum 0.7.0 (32-bits i386 + SSE2 little endian), GCC 8.3.0, by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 53042 it/s ( 5179.9 MB/s)
XXH32 unaligned : 102400 -> 52267 it/s ( 5104.2 MB/s)
XXH64 : 102400 -> 16333 it/s ( 1595.0 MB/s)
XXH64 unaligned : 102400 -> 16407 it/s ( 1602.2 MB/s)
XXH3_64bits : 102400 -> 8526 it/s ( 832.6 MB/s)
XXH3_64b unaligned : 102400 -> 8584 it/s ( 838.3 MB/s)
oh god, what the actual f*, GCC?
.text
.align 4,0x90
_XXH3_hashLong:
LFB5372:
pushl %ebp
LCFI0:
pushl %edi
LCFI1:
call ___x86.get_pc_thunk.di
L1$pb:
pushl %esi
LCFI2:
pushl %ebx
LCFI3:
movl %eax, %ebx
movl %ecx, %eax
subl $412, %esp
LCFI4:
shrl $10, %eax
movl %edx, 392(%esp)
movl %ecx, 388(%esp)
movl %edi, 396(%esp)
testl %eax, %eax
je L7
movl %edi, %ecx
movl 128+_kKey-L1$pb(%edi), %edi
sall $10, %eax
movl 132+_kKey-L1$pb(%ecx), %ebp
movl %edi, 312(%esp)
movl 136+_kKey-L1$pb(%ecx), %edi
movl %ebp, 316(%esp)
movl 140+_kKey-L1$pb(%ecx), %ebp
movl %edi, 320(%esp)
movl 144+_kKey-L1$pb(%ecx), %edi
movl %ebp, 324(%esp)
movl 148+_kKey-L1$pb(%ecx), %ebp
movl %edi, 328(%esp)
movl 152+_kKey-L1$pb(%ecx), %edi
movl %ebp, 332(%esp)
movl 156+_kKey-L1$pb(%ecx), %ebp
movl %edi, 336(%esp)
movl 160+_kKey-L1$pb(%ecx), %edi
movl %ebp, 340(%esp)
movl 164+_kKey-L1$pb(%ecx), %ebp
movl %edi, 344(%esp)
movl 168+_kKey-L1$pb(%ecx), %edi
movl %ebp, 348(%esp)
movl 172+_kKey-L1$pb(%ecx), %ebp
movl %edi, 352(%esp)
movl 176+_kKey-L1$pb(%ecx), %edi
movl %ebp, 356(%esp)
movl 180+_kKey-L1$pb(%ecx), %ebp
movl %edi, 360(%esp)
movl 184+_kKey-L1$pb(%ecx), %edi
movl %ebp, 364(%esp)
movl 188+_kKey-L1$pb(%ecx), %ebp
movl %edi, 368(%esp)
movl %ebp, 372(%esp)
movl (%ebx), %edi
movl 4(%ebx), %ebp
movl %edi, 152(%esp)
movl 8(%ebx), %edi
movl %ebp, 156(%esp)
movl 12(%ebx), %ebp
movl %edi, 160(%esp)
movl 16(%ebx), %edi
movl %ebp, 164(%esp)
movl 20(%ebx), %ebp
movl %edi, 168(%esp)
movl 24(%ebx), %edi
movl %ebp, 172(%esp)
movl 28(%ebx), %ebp
movl %edi, 176(%esp)
movl 32(%ebx), %edi
movl %ebp, 180(%esp)
movl 36(%ebx), %ebp
movl %edi, 184(%esp)
movl 40(%ebx), %edi
movl %ebp, 188(%esp)
movl 44(%ebx), %ebp
movl %edi, 192(%esp)
movl 48(%ebx), %edi
movl %ebp, 196(%esp)
movl 52(%ebx), %ebp
movl %edi, 200(%esp)
movl 56(%ebx), %edi
movl %ebp, 204(%esp)
movl 60(%ebx), %ebp
movl %edi, (%esp)
movl %ebp, 4(%esp)
movl 392(%esp), %edi
movl 36+_kKey-L1$pb(%ecx), %edx
addl %edi, %eax
movl %edi, %ebp
movl %eax, 380(%esp)
movl 32+_kKey-L1$pb(%ecx), %eax
movl %edx, 228(%esp)
movl 44+_kKey-L1$pb(%ecx), %edx
movl %eax, 224(%esp)
movl 40+_kKey-L1$pb(%ecx), %eax
movl %edx, 212(%esp)
movl 52+_kKey-L1$pb(%ecx), %edx
movl %eax, 208(%esp)
movl 48+_kKey-L1$pb(%ecx), %eax
movl %edx, 292(%esp)
movl 4+_kKey-L1$pb(%ecx), %edx
movl %eax, 288(%esp)
movl _kKey-L1$pb(%ecx), %eax
movl %edx, 244(%esp)
movl 12+_kKey-L1$pb(%ecx), %edx
movl %eax, 240(%esp)
movl 8+_kKey-L1$pb(%ecx), %eax
movl %edx, 260(%esp)
movl 20+_kKey-L1$pb(%ecx), %edx
movl %eax, 256(%esp)
movl 16+_kKey-L1$pb(%ecx), %eax
movl %edx, 276(%esp)
movl %eax, 272(%esp)
leal _kKey-L1$pb(%ecx), %eax
movl %eax, 384(%esp)
.align 4,0x90
L6:
movl 384(%esp), %eax
movl %ebp, %ecx
movl %ebp, 308(%esp)
movl (%esp), %esi
movdqa 272(%esp), %xmm4
movdqa 256(%esp), %xmm3
leal 128(%eax), %edi
movl %eax, %ebp
movdqa 240(%esp), %xmm1
movdqa 288(%esp), %xmm5
movl %edi, 304(%esp)
movl 4(%esp), %edi
movdqa 208(%esp), %xmm2
movdqa 224(%esp), %xmm0
.align 4,0x90
L5:
movq (%ecx), %xmm6
pxor %xmm6, %xmm1
movd %xmm1, %edx
psrlq $32, %xmm1
movd %xmm1, %eax
mull %edx
movd %edx, %xmm7
movd %eax, %xmm1
punpckldq %xmm7, %xmm1
paddq %xmm1, %xmm6
movd %xmm6, 80(%esp)
psrlq $32, %xmm6
movl 80(%esp), %eax
addl %eax, 152(%esp)
movd %xmm6, 84(%esp)
movdqa %xmm3, %xmm6
movl 84(%esp), %edx
adcl %edx, 156(%esp)
movq 152(%esp), %xmm7
movq %xmm7, (%ebx)
movq 8(%ecx), %xmm7
pxor %xmm7, %xmm6
movd %xmm6, %edx
psrlq $32, %xmm6
movd %xmm6, %eax
mull %edx
movd %edx, %xmm6
movd %eax, %xmm1
punpckldq %xmm6, %xmm1
paddq %xmm7, %xmm1
movdqa %xmm4, %xmm6
movd %xmm1, 96(%esp)
psrlq $32, %xmm1
movl 96(%esp), %eax
addl %eax, 160(%esp)
movd %xmm1, 100(%esp)
movl 100(%esp), %edx
adcl %edx, 164(%esp)
movq 160(%esp), %xmm7
movq %xmm7, 8(%ebx)
movq 16(%ecx), %xmm7
pxor %xmm7, %xmm6
movd %xmm6, %edx
psrlq $32, %xmm6
movd %xmm6, %eax
mull %edx
movd %edx, %xmm6
movd %eax, %xmm1
punpckldq %xmm6, %xmm1
paddq %xmm7, %xmm1
movd %xmm1, 112(%esp)
psrlq $32, %xmm1
movl 112(%esp), %eax
movd %xmm1, 116(%esp)
movl 116(%esp), %edx
addl %eax, 168(%esp)
adcl %edx, 172(%esp)
movq 168(%esp), %xmm7
movq %xmm7, 16(%ebx)
movl 24(%ebp), %eax
movl 28(%ebp), %edx
movq 24(%ecx), %xmm6
movl %eax, (%esp)
movl %edx, 4(%esp)
movdqa (%esp), %xmm7
pxor %xmm6, %xmm7
movdqa %xmm7, %xmm1
movd %xmm7, %edx
psrlq $32, %xmm1
movd %xmm1, %eax
mull %edx
movd %edx, %xmm7
movd %eax, %xmm1
punpckldq %xmm7, %xmm1
paddq %xmm6, %xmm1
movd %xmm1, 128(%esp)
psrlq $32, %xmm1
movl 128(%esp), %eax
movd %xmm1, 132(%esp)
movl 132(%esp), %edx
addl %eax, 176(%esp)
adcl %edx, 180(%esp)
movq 176(%esp), %xmm7
movq %xmm7, 24(%ebx)
movq 32(%ecx), %xmm1
pxor %xmm1, %xmm0
movd %xmm0, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm6
movd %eax, %xmm0
punpckldq %xmm6, %xmm0
paddq %xmm1, %xmm0
movd %xmm0, 16(%esp)
psrlq $32, %xmm0
movl 16(%esp), %eax
movd %xmm0, 20(%esp)
movl 20(%esp), %edx
addl %eax, 184(%esp)
adcl %edx, 188(%esp)
movq 184(%esp), %xmm7
movq %xmm7, 32(%ebx)
movq 40(%ecx), %xmm6
movdqa %xmm2, %xmm7
pxor %xmm6, %xmm7
movdqa %xmm7, %xmm1
movd %xmm7, %edx
psrlq $32, %xmm1
movd %xmm1, %eax
mull %edx
movd %edx, %xmm1
movd %eax, %xmm0
punpckldq %xmm1, %xmm0
paddq %xmm6, %xmm0
movd %xmm0, 32(%esp)
psrlq $32, %xmm0
movl 32(%esp), %eax
addl %eax, 192(%esp)
movd %xmm0, 36(%esp)
movl 36(%esp), %edx
adcl %edx, 196(%esp)
movq 192(%esp), %xmm7
movq %xmm7, 40(%ebx)
movq 48(%ecx), %xmm6
movdqa %xmm5, %xmm7
pxor %xmm6, %xmm7
movdqa %xmm7, %xmm1
movd %xmm7, %edx
psrlq $32, %xmm1
movd %xmm1, %eax
mull %edx
movd %edx, %xmm1
movd %eax, %xmm0
punpckldq %xmm1, %xmm0
paddq %xmm6, %xmm0
movd %xmm0, 48(%esp)
psrlq $32, %xmm0
movl 48(%esp), %eax
addl %eax, 200(%esp)
movd %xmm0, 52(%esp)
movl 52(%esp), %edx
adcl %edx, 204(%esp)
movq 200(%esp), %xmm7
movq %xmm7, 48(%ebx)
movq 56(%ecx), %xmm6
movq 56(%ebp), %xmm1
movdqa %xmm6, %xmm7
pxor %xmm1, %xmm7
movdqa %xmm7, %xmm0
movd %xmm7, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %eax, %xmm0
movd %edx, %xmm7
punpckldq %xmm7, %xmm0
paddq %xmm6, %xmm0
movd %xmm0, 64(%esp)
psrlq $32, %xmm0
addl 64(%esp), %esi
movd %xmm0, 68(%esp)
adcl 68(%esp), %edi
addl $8, %ebp
addl $64, %ecx
movdqa %xmm2, %xmm0
movdqa %xmm5, %xmm2
movdqa %xmm1, %xmm5
movdqa %xmm3, %xmm1
movdqa %xmm4, %xmm3
movdqa (%esp), %xmm4
movl %esi, 56(%ebx)
movl %edi, 60(%ebx)
cmpl 304(%esp), %ebp
jne L5
movl %esi, (%esp)
movl 312(%esp), %eax
movl $-1640531535, %ecx
movl 152(%esp), %esi
movl %edi, 4(%esp)
movl 156(%esp), %edi
movl 316(%esp), %edx
movl 308(%esp), %ebp
xorl %esi, %eax
movl %edi, %esi
xorl %edi, %edx
shrl $15, %esi
xorl %edi, %edi
xorl %esi, %eax
xorl %edi, %edx
movl 160(%esp), %esi
imull $-1640531535, %edx, %edi
mull %ecx
movl %edx, 156(%esp)
movl 324(%esp), %edx
addl %edi, 156(%esp)
movl %eax, 152(%esp)
movl 164(%esp), %edi
movl 320(%esp), %eax
movq 152(%esp), %xmm5
xorl %edi, %edx
movq %xmm5, (%ebx)
xorl %esi, %eax
movl %edi, %esi
xorl %edi, %edi
shrl $15, %esi
xorl %edi, %edx
xorl %esi, %eax
imull $-1640531535, %edx, %edi
movl 168(%esp), %esi
mull %ecx
movl %edx, 164(%esp)
movl 332(%esp), %edx
addl %edi, 164(%esp)
movl %eax, 160(%esp)
movl 172(%esp), %edi
movl 328(%esp), %eax
movq 160(%esp), %xmm4
xorl %edi, %edx
movq %xmm4, 8(%ebx)
xorl %esi, %eax
movl %edi, %esi
xorl %edi, %edi
shrl $15, %esi
xorl %edi, %edx
xorl %esi, %eax
imull $-1640531535, %edx, %edi
mull %ecx
movl %edx, 172(%esp)
addl %edi, 172(%esp)
movl %eax, 168(%esp)
movq 168(%esp), %xmm2
movq %xmm2, 16(%ebx)
movl 180(%esp), %edi
movl 176(%esp), %esi
movl 336(%esp), %eax
movl 340(%esp), %edx
xorl %esi, %eax
movl %edi, %esi
shrl $15, %esi
xorl %edi, %edx
xorl %edi, %edi
xorl %esi, %eax
xorl %edi, %edx
movl 184(%esp), %esi
imull $-1640531535, %edx, %edi
mull %ecx
movl %edx, 180(%esp)
movl 348(%esp), %edx
addl %edi, 180(%esp)
movl %eax, 176(%esp)
movl 188(%esp), %edi
movl 344(%esp), %eax
movq 176(%esp), %xmm3
xorl %edi, %edx
movq %xmm3, 24(%ebx)
xorl %esi, %eax
movl %edi, %esi
xorl %edi, %edi
shrl $15, %esi
xorl %edi, %edx
xorl %esi, %eax
imull $-1640531535, %edx, %edi
movl 192(%esp), %esi
mull %ecx
movl %edx, 188(%esp)
movl 356(%esp), %edx
addl %edi, 188(%esp)
movl %eax, 184(%esp)
movl 196(%esp), %edi
movl 352(%esp), %eax
movq 184(%esp), %xmm5
xorl %edi, %edx
movq %xmm5, 32(%ebx)
xorl %esi, %eax
movl %edi, %esi
xorl %edi, %edi
shrl $15, %esi
xorl %edi, %edx
xorl %esi, %eax
imull $-1640531535, %edx, %edi
mull %ecx
movl %edx, 196(%esp)
movl 364(%esp), %edx
addl %edi, 196(%esp)
movl %eax, 192(%esp)
movq 192(%esp), %xmm4
movl 360(%esp), %eax
movq %xmm4, 40(%ebx)
movl 200(%esp), %esi
movl 204(%esp), %edi
xorl %esi, %eax
movl %edi, %esi
xorl %edi, %edx
xorl %edi, %edi
shrl $15, %esi
xorl %edi, %edx
xorl %esi, %eax
imull $-1640531535, %edx, %edi
movl (%esp), %esi
mull %ecx
movl %edx, 204(%esp)
movl 372(%esp), %edx
addl %edi, 204(%esp)
movl %eax, 200(%esp)
movl 4(%esp), %edi
movl 368(%esp), %eax
movq 200(%esp), %xmm2
movq %xmm2, 48(%ebx)
xorl %esi, %eax
movl %edi, %esi
xorl %edi, %edx
xorl %edi, %edi
shrl $15, %esi
addl $1024, %ebp
xorl %edi, %edx
xorl %esi, %eax
imull $-1640531535, %edx, %edi
mull %ecx
movl %edx, 4(%esp)
addl %edi, 4(%esp)
movl %eax, (%esp)
movq (%esp), %xmm3
movq %xmm3, 56(%ebx)
cmpl 380(%esp), %ebp
jne L6
L7:
movl 388(%esp), %eax
movl 392(%esp), %ecx
movl %eax, %ebp
andl $-1024, %eax
shrl $6, %ebp
addl %eax, %ecx
andl $15, %ebp
je L4
movl (%ebx), %eax
movl 4(%ebx), %edx
movl 396(%esp), %edi
movq 40(%ebx), %xmm4
movl %eax, 80(%esp)
movl 8(%ebx), %eax
movl %edx, 84(%esp)
movl 12(%ebx), %edx
movq 32+_kKey-L1$pb(%edi), %xmm0
leal _kKey-L1$pb(%edi), %esi
movq 48(%ebx), %xmm3
movl %eax, (%esp)
movl 16(%ebx), %eax
movl %edx, 4(%esp)
movl 20(%ebx), %edx
movq (%esp), %xmm5
movq 56(%ebx), %xmm2
movl %eax, 96(%esp)
movl 24(%ebx), %eax
movl %edx, 100(%esp)
movl 28(%ebx), %edx
movl %eax, 112(%esp)
movl 32(%ebx), %eax
movl %edx, 116(%esp)
movl 36(%ebx), %edx
movl %eax, 128(%esp)
movl 40+_kKey-L1$pb(%edi), %eax
movl %edx, 132(%esp)
movl 44+_kKey-L1$pb(%edi), %edx
movl %eax, (%esp)
movl 48+_kKey-L1$pb(%edi), %eax
movl %edx, 4(%esp)
movl 52+_kKey-L1$pb(%edi), %edx
movl %eax, 32(%esp)
movl 8+_kKey-L1$pb(%edi), %eax
movl %edx, 36(%esp)
movl 12+_kKey-L1$pb(%edi), %edx
movq _kKey-L1$pb(%edi), %xmm1
movl %eax, 48(%esp)
movl 16+_kKey-L1$pb(%edi), %eax
movl %edx, 52(%esp)
movl 20+_kKey-L1$pb(%edi), %edx
leal (%esi,%ebp,8), %edi
movl %eax, 16(%esp)
movl %edx, 20(%esp)
.align 4,0x90
L10:
movq (%ecx), %xmm6
addl $8, %esi
addl $64, %ecx
pxor %xmm6, %xmm1
movd %xmm1, %edx
psrlq $32, %xmm1
movd %xmm1, %eax
mull %edx
movd %edx, %xmm7
movd %eax, %xmm1
punpckldq %xmm7, %xmm1
movdqa 80(%esp), %xmm7
paddq %xmm6, %xmm1
paddq %xmm1, %xmm7
movq %xmm7, (%ebx)
movq -56(%ecx), %xmm6
movq %xmm7, 80(%esp)
movdqa 48(%esp), %xmm7
pxor %xmm6, %xmm7
movdqa %xmm7, %xmm1
movd %xmm7, %edx
psrlq $32, %xmm1
movd %xmm1, %eax
mull %edx
movd %edx, %xmm7
movd %eax, %xmm1
punpckldq %xmm7, %xmm1
paddq %xmm6, %xmm1
movdqa 16(%esp), %xmm7
paddq %xmm1, %xmm5
movq %xmm5, 8(%ebx)
movq -48(%ecx), %xmm6
pxor %xmm6, %xmm7
movdqa %xmm7, %xmm1
movd %xmm7, %edx
psrlq $32, %xmm1
movd %xmm1, %eax
mull %edx
movd %edx, %xmm7
movd %eax, %xmm1
punpckldq %xmm7, %xmm1
movdqa 96(%esp), %xmm7
paddq %xmm6, %xmm1
paddq %xmm1, %xmm7
movq %xmm7, 16(%ebx)
movl 16(%esi), %eax
movl 20(%esi), %edx
movq %xmm7, 96(%esp)
movq -40(%ecx), %xmm6
movl %eax, 64(%esp)
movl %edx, 68(%esp)
movdqa 64(%esp), %xmm7
pxor %xmm6, %xmm7
movdqa %xmm7, %xmm1
movd %xmm7, %edx
psrlq $32, %xmm1
movd %xmm1, %eax
mull %edx
movd %edx, %xmm7
movd %eax, %xmm1
punpckldq %xmm7, %xmm1
movdqa 112(%esp), %xmm7
paddq %xmm6, %xmm1
paddq %xmm1, %xmm7
movq %xmm7, 24(%ebx)
movq -32(%ecx), %xmm1
movq %xmm7, 112(%esp)
movdqa 128(%esp), %xmm7
pxor %xmm1, %xmm0
movd %xmm0, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm6
movd %eax, %xmm0
punpckldq %xmm6, %xmm0
paddq %xmm1, %xmm0
paddq %xmm0, %xmm7
movq %xmm7, 32(%ebx)
movq -24(%ecx), %xmm1
movq %xmm7, 128(%esp)
movdqa (%esp), %xmm7
pxor %xmm1, %xmm7
movdqa %xmm7, %xmm0
movd %xmm7, %edx
movdqa 32(%esp), %xmm7
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm6
movd %eax, %xmm0
punpckldq %xmm6, %xmm0
paddq %xmm1, %xmm0
paddq %xmm0, %xmm4
movq %xmm4, 40(%ebx)
movq -16(%ecx), %xmm1
pxor %xmm1, %xmm7
movdqa %xmm7, %xmm0
movd %xmm7, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm6
movd %eax, %xmm0
punpckldq %xmm6, %xmm0
paddq %xmm1, %xmm0
paddq %xmm0, %xmm3
movq %xmm3, 48(%ebx)
movq -8(%ecx), %xmm6
movq 48(%esi), %xmm1
movdqa %xmm6, %xmm7
pxor %xmm1, %xmm7
movdqa %xmm7, %xmm0
movd %xmm7, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm7
movd %eax, %xmm0
punpckldq %xmm7, %xmm0
movdqa 32(%esp), %xmm7
paddq %xmm6, %xmm0
movaps %xmm1, 32(%esp)
paddq %xmm0, %xmm2
movdqa (%esp), %xmm0
movaps %xmm7, (%esp)
movdqa 16(%esp), %xmm7
movdqa 48(%esp), %xmm1
movq %xmm2, 56(%ebx)
movaps %xmm7, 48(%esp)
movdqa 64(%esp), %xmm7
movaps %xmm7, 16(%esp)
cmpl %edi, %esi
jne L10
L4:
testb $63, 388(%esp)
je L1
movl 392(%esp), %edi
sall $3, %ebp
movl 388(%esp), %ecx
leal -48(%edi,%ecx), %edx
leal -64(%edi,%ecx), %eax
cmpl %edx, %ebx
jnb L14
leal 16(%ebx), %edx
cmpl %edx, %eax
jb L11
L14:
movl 396(%esp), %edi
movdqu (%eax), %xmm2
leal _kKey-L1$pb(%edi,%ebp), %edx
movdqu (%edx), %xmm1
pxor %xmm2, %xmm1
movdqa lC0-L1$pb(%edi), %xmm2
movdqa %xmm1, %xmm5
psrlq $32, %xmm1
movdqa %xmm1, %xmm4
pand %xmm2, %xmm5
movdqa %xmm5, %xmm0
movdqa %xmm5, %xmm3
psrlq $32, %xmm0
psrlq $32, %xmm4
pmuludq %xmm1, %xmm3
pmuludq %xmm0, %xmm1
movdqa %xmm4, %xmm0
pmuludq %xmm5, %xmm0
paddq %xmm0, %xmm1
movdqu (%eax), %xmm0
paddq (%ebx), %xmm0
psllq $32, %xmm1
paddq %xmm3, %xmm1
paddq %xmm0, %xmm1
movaps %xmm1, (%ebx)
movdqu 16(%edx), %xmm1
movdqu 16(%eax), %xmm4
pxor %xmm4, %xmm1
movdqa %xmm1, %xmm5
psrlq $32, %xmm1
pand %xmm2, %xmm5
movdqa %xmm1, %xmm4
movdqa %xmm5, %xmm0
movdqa %xmm5, %xmm3
psrlq $32, %xmm0
psrlq $32, %xmm4
pmuludq %xmm1, %xmm3
pmuludq %xmm0, %xmm1
movdqa %xmm4, %xmm0
pmuludq %xmm5, %xmm0
paddq %xmm0, %xmm1
movdqu 16(%eax), %xmm0
paddq 16(%ebx), %xmm0
psllq $32, %xmm1
paddq %xmm3, %xmm1
paddq %xmm0, %xmm1
movaps %xmm1, 16(%ebx)
movdqu 32(%edx), %xmm1
movdqu 32(%eax), %xmm4
pxor %xmm4, %xmm1
movdqa %xmm1, %xmm5
psrlq $32, %xmm1
pand %xmm2, %xmm5
movdqa %xmm1, %xmm4
movdqa %xmm5, %xmm0
movdqa %xmm5, %xmm3
psrlq $32, %xmm0
psrlq $32, %xmm4
pmuludq %xmm1, %xmm3
pmuludq %xmm0, %xmm1
movdqa %xmm4, %xmm0
pmuludq %xmm5, %xmm0
paddq %xmm0, %xmm1
movdqu 32(%eax), %xmm0
paddq 32(%ebx), %xmm0
psllq $32, %xmm1
paddq %xmm3, %xmm1
paddq %xmm0, %xmm1
movdqu 48(%edx), %xmm0
movaps %xmm1, 32(%ebx)
movdqu 48(%eax), %xmm3
pxor %xmm3, %xmm0
movdqa %xmm0, %xmm4
pand %xmm2, %xmm0
movdqa %xmm0, %xmm5
psrlq $32, %xmm4
paddq 48(%ebx), %xmm3
movdqa %xmm4, %xmm1
psrlq $32, %xmm5
movdqa %xmm4, %xmm2
psrlq $32, %xmm1
pmuludq %xmm0, %xmm2
pmuludq %xmm1, %xmm0
movdqa %xmm5, %xmm1
pmuludq %xmm4, %xmm1
paddq %xmm1, %xmm0
psllq $32, %xmm0
paddq %xmm2, %xmm0
paddq %xmm3, %xmm0
movaps %xmm0, 48(%ebx)
L1:
addl $412, %esp
LCFI5:
popl %ebx
LCFI6:
popl %esi
LCFI7:
popl %edi
LCFI8:
popl %ebp
LCFI9:
ret
L11:
LCFI10:
movq (%eax), %xmm1
movl %ecx, %esi
movl 396(%esp), %eax
movq _kKey-L1$pb(%eax,%ebp), %xmm0
leal _kKey-L1$pb(%eax), %ecx
pxor %xmm1, %xmm0
movd %xmm0, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm2
movd %eax, %xmm0
punpckldq %xmm2, %xmm0
paddq %xmm1, %xmm0
movq (%ebx), %xmm1
paddq %xmm1, %xmm0
movq %xmm0, (%ebx)
movq 8(%ecx,%ebp), %xmm0
movq -56(%edi,%esi), %xmm1
pxor %xmm1, %xmm0
movd %xmm0, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm2
movd %eax, %xmm0
punpckldq %xmm2, %xmm0
paddq %xmm1, %xmm0
movq 8(%ebx), %xmm1
paddq %xmm1, %xmm0
movq %xmm0, 8(%ebx)
movq 16(%ecx,%ebp), %xmm0
movq -48(%edi,%esi), %xmm1
pxor %xmm1, %xmm0
movd %xmm0, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm2
movd %eax, %xmm0
punpckldq %xmm2, %xmm0
paddq %xmm1, %xmm0
movq 16(%ebx), %xmm1
paddq %xmm1, %xmm0
movq %xmm0, 16(%ebx)
movq 24(%ecx,%ebp), %xmm0
movq -40(%edi,%esi), %xmm1
pxor %xmm1, %xmm0
movd %xmm0, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm2
movd %eax, %xmm0
punpckldq %xmm2, %xmm0
paddq %xmm1, %xmm0
movq 24(%ebx), %xmm1
paddq %xmm1, %xmm0
movq %xmm0, 24(%ebx)
movq 32(%ecx,%ebp), %xmm0
movq -32(%edi,%esi), %xmm1
pxor %xmm1, %xmm0
movd %xmm0, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm2
movd %eax, %xmm0
punpckldq %xmm2, %xmm0
paddq %xmm1, %xmm0
movq 32(%ebx), %xmm1
paddq %xmm1, %xmm0
movq %xmm0, 32(%ebx)
movq 40(%ecx,%ebp), %xmm0
movq -24(%edi,%esi), %xmm1
pxor %xmm1, %xmm0
movd %xmm0, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm2
movd %eax, %xmm0
punpckldq %xmm2, %xmm0
paddq %xmm1, %xmm0
movq 40(%ebx), %xmm1
paddq %xmm1, %xmm0
movq %xmm0, 40(%ebx)
movq 48(%ecx,%ebp), %xmm0
movq -16(%edi,%esi), %xmm1
pxor %xmm1, %xmm0
movd %xmm0, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %edx, %xmm2
movd %eax, %xmm0
punpckldq %xmm2, %xmm0
paddq %xmm1, %xmm0
movq 48(%ebx), %xmm1
paddq %xmm1, %xmm0
movq %xmm0, 48(%ebx)
movq 56(%ecx,%ebp), %xmm0
movq -8(%edi,%esi), %xmm1
pxor %xmm1, %xmm0
movd %xmm0, %edx
psrlq $32, %xmm0
movd %xmm0, %eax
mull %edx
movd %eax, %xmm0
movd %edx, %xmm2
punpckldq %xmm2, %xmm0
paddq %xmm1, %xmm0
movq 56(%ebx), %xmm1
paddq %xmm1, %xmm0
movq %xmm0, 56(%ebx)
addl $412, %esp
LCFI11:
popl %ebx
LCFI12:
popl %esi
LCFI13:
popl %edi
LCFI14:
popl %ebp
LCFI15:
ret
LFE5372:
(sorry about the AT&T syntax, GCC for macOS doesn't support Intel syntax)
Not a huge deal because GCC will be using the SSE2 path in that case, so this isn't too much to worry about.
Wait, I figured out the difference, I passed kKey as a pointer to XXH3_hashLong (so I didn't have duped keys). Passing kKey as a pointer to XXH3_hashLong gets 3.2 GB/s.
Also, I found my ancient P3 laptop, but I can't seem to find the power cord. It's one of those things where you find it when you are looking for something else but not when you are looking for it. 😒
I guess this is the case I had before with GCC for Thumb. GCC figures out it can optimize a constant and does it in the absolute worst way possible.
I think I'm gonna call it "constant propagurgitation".
https://github.com/easyaspi314/xxhash/tree/multitarget
I uploaded my changes. I have some of the updated algorithm, the dispatcher, updated scalar code, and a few other goodies. I'm not opening a PR until you tell me how that new code works out.
Also, I need to fix these god damn ugly merge conflicts. 😒
#if !defined(XXH3_TARGET_C) && defined(__GNUC__)
__attribute__((__constructor__))
#endif
static void
XXH3_featureTest(void)
{
int max, data[4];
/* First, get how many CPUID function parameters there are by calling CPUID with eax = 0. */
XXH_CPUID(data, /* eax */ 0);
max = data[0];
/* AVX2 is on the Extended Features page (eax = 7, ecx = 0), on bit 5 of ebx. */
if (max >= 7) {
XXH_CPUIDEX(data, /* eax */ 7, /* ecx */ 0);
if (data[1] & (1 << 5)) {
cpu_mode = XXH_CPU_MODE_AVX2;
return;
}
}
<<<<<<< HEAD
/* SSE2 is on the Processor Info and Feature Bits page (eax = 1), on bit 26 of edx. */
if (max >= 1) {
XXH_CPUID(data, /* eax */ 1);
if (data[3] & (1 << 26)) {
cpu_mode = XXH_CPU_MODE_SSE2;
return;
}
=======
#else /* scalar variant of Accumulator - universal */
U64* const xacc = (U64*) acc; /* presumed aligned */
const U32* const xdata = (const U32*) data;
const U32* const xkey = (const U32*) key;
int i;
for (i=0; i < (int)ACC_NB; i++) {
int const left = 2*i;
int const right= 2*i + 1;
U32 const dataLeft = XXH_readLE32(xdata + left);
U32 const dataRight = XXH_readLE32(xdata + right);
xacc[i] += XXH_mult32to64(dataLeft ^ xkey[left], dataRight ^ xkey[right]);
xacc[i] += dataLeft + ((U64)dataRight << 32);
>>>>>>> 7efa77614832b96eb78a286b3607a97bfa188276
}
/* Must be scalar. */
cpu_mode = XXH_CPU_MODE_SCALAR;
}
~/xxh3-fix $ ./xxhsum -b -m2
./xxhsum 0.7.0 (64-bits x86_64 + SSE2 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 49052 it/s ( 4790.3 MB/s)
XXH32 unaligned : 102400 -> 52240 it/s ( 5101.5 MB/s)
XXH64 : 102400 -> 72225 it/s ( 7053.2 MB/s)
XXH64 unaligned : 102400 -> 72505 it/s ( 7080.6 MB/s)
Illegal instruction: 4 102400 ->
~/xxh3-fix $ ./xxhsum -b -m1
./xxhsum 0.7.0 (64-bits x86_64 + SSE2 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 50042 it/s ( 4886.9 MB/s)
XXH32 unaligned : 102400 -> 49664 it/s ( 4850.0 MB/s)
XXH64 : 102400 -> 75342 it/s ( 7357.6 MB/s)
XXH64 unaligned : 102400 -> 72363 it/s ( 7066.7 MB/s)
XXH3_64bits : 102400 -> 168694 it/s (16474.0 MB/s)
XXH3_64b unaligned : 102400 -> 172788 it/s (16873.8 MB/s)
~/xxh3-fix $ ./xxhsum -b -m0
./xxhsum 0.7.0 (64-bits x86_64 + SSE2 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 50954 it/s ( 4976.0 MB/s)
XXH32 unaligned : 102400 -> 49851 it/s ( 4868.3 MB/s)
XXH64 : 102400 -> 75145 it/s ( 7338.4 MB/s)
XXH64 unaligned : 102400 -> 71043 it/s ( 6937.8 MB/s)
XXH3_64bits : 102400 -> 87310 it/s ( 8526.4 MB/s)
XXH3_64b unaligned : 102400 -> 85418 it/s ( 8341.6 MB/s)
I added the -m switch to xxhsum which will select scalar, sse2 or avx2 code paths depending on if it is 0, 1, or 2 respectively
As you can see, -m2 crashes because it tries to use AVX2, -m1 gives me the best performance, which in my case is the SSE2 version, and -m0 only gives me decent performance (no, it's not faster than XXH64, that is a clang bug) because it is the scalar code.
EDIT: In order to use the dispatching, you need to do make MULTI_TARGET=1.
For MSVC, if someone could try the multitargeting code, this should compile it:
> cl.exe -O2 -c xxhash.c -DXXH_MULTI_TARGET
> cl.exe -O2 -c xxh3-target.c -DXXH_MULTI_TARGET -DXXH_VECTOR=0 -o xxh3-scalar.obj
> cl.exe -O2 -c xxh3-target.c -DXXH_MULTI_TARGET -DXXH_VECTOR=1 -arch:SSE2 -o xxh3-sse2.obj
> cl.exe -O2 -c xxh3-target.c -DXXH_MULTI_TARGET -DXXH_VECTOR=2 -arch:AVX2 -o xxh3-avx2.obj
> cl.exe -O2 -c xxhsum.c -DXXH_MULTI_TARGET
> cl.exe xxhash.obj xxhsum.obj xxh3-scalar.obj xxh3-sse2.obj xxh3-avx2.obj -o xxhsum.exe
Untested for now, my sister had the laptop all day.
I fixed the code for MSVC, and here are the correct commands:
> cl.exe -O2 -c xxhash.c -DXXH_MULTI_TARGET=1
> cl.exe -O2 -c xxh3-target.c -DXXH_MULTI_TARGET=1 -DXXH_VECTOR=0 -Foxxh3-scalar.obj
> cl.exe -O2 -c xxh3-target.c -DXXH_MULTI_TARGET=1 -DXXH_VECTOR=1 -arch:SSE2 -Foxxh3-sse2.obj
> cl.exe -O2 -c xxh3-target.c -DXXH_MULTI_TARGET=1 -DXXH_VECTOR=2 -arch:AVX2 -Foxxh3-avx2.obj
> cl.exe -O2 -c xxhsum.c -DXXH_MULTI_TARGET=1
> cl.exe -O2 xxhsum.obj xxhash.obj xxh3-scalar.obj xxh3-sse2.obj xxh3-avx2.obj
MSVC stands true to its name: MSVC Sucks at Vectorizing Code. The AVX2 code is not much faster than the SSE2 code, while even GCC's version had a notable speedup with AVX2. I think it is not unrolling the loop.
Edit: MSVC for x64 will warn with -arch:SSE2 on non-x86. You can ignore it though.
FYI, regarding the scrambler : we'll keep the new scrambler formula, as it has higher quality.
The new scrambler is fully bijective, while the previous one incurred a little space reduction, for both variants (^ and +, + was sensibly better, but not fully bijective).
Note that XXH3 nonetheless met 64-bits collision rate objectives even with the old scrambler, likely because the scrambler stage is "rare" (once per KB), and the final stage involves mixing 8 accumulators (512 bits -> 64 bits), so even if space reduction was started a bit before, it's no longer a big deal after that final mixing.
But I nonetheless value bijective property for the scrambler stage, from a collision rate perspective, it carries a higher quality tag.
When you're done tuning, could you update the test values for me so I know we are on the right page?
Sure, I will.
branch xxh3 will be merged when XXH3_64bits() get ready,
it will contain all associated test codes.
There will still be some work to do on XXH128(), but that part can be done separately.
Update on NEON32: Yeah, pragma clang loop unroll is not good on ARM.
I think it has to do with the tiny 64 byte L1 cache line. (And 32 KB instruction cache total)
unroll_count(2) gives me the best performance.
unroll_count(1) (no unroll): 7.4
unroll_count(2): 8.1
unroll_count(4): 6.2
unroll(enable): 5.2
How about we hand unroll the main loop twice and tell Clang to completely unroll on x86?
#if defined(__clang__) && !defined(__OPTIMIZE_SIZE__) && (defined(__i386__) || defined(__x86_64__))
# pragma clang loop unroll(enable)
#endif
for (i = 0; i < NB_KEYS / 2; i++) {
XXH3_accumulate512(...);
XXH3_accumulate512(...);
}
Wait, I think it is because XXH3 might entirely fit in cache that way.
My MacBook also has a 64 byte cache line. :thinking:


As for scalar ARM (thumbv6t2) I am getting 2.1 GB/s right now.
I had to use inline assembly because Clang assumed that the pointer was aligned and caused a bus error.
[termux ~/xxh3] $ ./xxhsum -b
./xxhsum 0.7.0 (32-bits arm little endian), Clang 7.0.1 (tags/RELEASE_701/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 20235 it/s ( 1976.1 MB/s)
XXH32 unaligned : 102400 -> 18670 it/s ( 1823.2 MB/s)
XXH64 : 102400 -> 8646 it/s ( 844.3 MB/s)
XXH64 unaligned : 102400 -> 8363 it/s ( 816.7 MB/s)
XXH3_64bits : 102400 -> 21500 it/s ( 2099.6 MB/s)
XXH3_64b unaligned : 102400 -> 21515 it/s ( 2101.0 MB/s)
(Edit: This is on my G3)
Clang assumed that the pointer was aligned and caused a bus error
Does that mean the scalar code path needs to be fixed ?
It shouldn't give the compiler a chance to make that mistake.
How about we hand unroll the main loop twice
A side effect is that it would add a restriction on custom vector key size.
That's likely an acceptable side effect.
Does that mean the scalar code path needs to be fixed ?
It shouldn't give the compiler a chance to make that mistake.
XXH_read32 and XXH_read64 need to be fixed when targeting ARMv6. The scalar code itself appears to be fine.
Clang (edit: and GCC) are adding ldmib instructions to XXH32 when targeting ARMv6t2, which requires a 32-bit aligned address.
.LBB1_3:
ldr r1, [r6]
ldmib r6, {r0, r7} // <- aaaaaa
ldr r4, [r6, #12]
mla r0, r0, r9, r3
mla r2, r7, r9, r2
mla r4, r4, r9, lr
ror r12, r0, #19
mla r0, r1, r9, r5
ror r7, r2, #19
ror r4, r4, #19
ror r1, r0, #19
mul lr, r4, r10
mul r2, r7, r10
mul r3, r12, r10
mul r5, r1, r10
add r6, r6, #16
cmp r6, r8
blo .LBB1_3
I'm trying to figure out how to fix this without inline assembly right now, as if I use inline assembly, it generates extra add instructions.
.LBB1_3:
ldr r1, [r0]
mla r1, r1, r10, r7
ror r12, r1, #19
add r1, r0, #12 @ <-
ldr r1, [r1]
mul r7, r12, r3
mla r1, r1, r10, r4
ror r6, r1, #19
add r1, r0, #8 @ <-
ldr r1, [r1]
mul r4, r6, r3
mla r1, r1, r10, r2
ror lr, r1, #19
add r1, r0, #4 @ <-
ldr r1, [r1]
mul r2, lr, r3
mla r1, r1, r10, r5
add r0, r0, #16
cmp r0, r9
ror r8, r1, #19
mul r5, r8, r3
blo .LBB1_3
What does seem to work is to use memcpy with the compiler flag -munaligned-access. That reliably disables the evil ldmib instructions. However, without -munaligned-access, it will always do byte-by-byte access.
I'll figure it out, don't hurt your head with it.
The alignment memes strike again. 🤦♂️
By the way, does this look correct so far?
XXH_read32 and XXH_read64 need to be fixed when targeting ARMv6.
xxhash is supposed to make the right choice automatically, depending on target.
It could be that the set of macros is not correct for ARMv6.
One way to "help" it is to define XXH_FORCE_MEMORY_ACCESS at compilation time. If one of them work, then it becomes a matter of finding the right set of macros for the automatic detection to work properly on this target.
does this look correct so far?
There are minor changes that happened in the last 2 weeks.
I would prefer to leave comments directly in the code, that would make it simpler for you to follow.
But that doesn't work on the link provided directly.
I guess I'll have to chase the corresponding commit.
Side note: This:
( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) \
|| defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) \
|| defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) \
|| defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) \
|| defined(__ARM_ARCH_7S__) )
could easily be simplified to this:
(defined(__ARM_ARCH) && __ARM_ARCH == 6)
(defined(__ARM_ARCH) && __ARM_ARCH >= 7)
That would pick up on ARMv7VE (Cortex-A15) and aarch64, and it would look a lot nicer.
Anyways, I'll see what I can do about the memory access. I'm thinking just memcpy. Once you add -munaligned-access to the flags, the code speeds up a lot, but without it, it is completely safe from alignment memes, as while it isn't perfect, it is going to be good enough at least for now.
The only common ARMv6 device which is actually being used (and sold!) is the Nintendo 3DS. Nintendo just has a hardcore fetish for obsolete hardware and not giving up on dead consoles, and they have always been a pain.
By the way, I cleaned up my previous attempt at the folded 128-bit multiply for my clean version, this is it.
It is slightly faster than yours on Clang and significantly faster on GCC.
uint64_t mult_hd(uint64_t const lhs, uint64_t const rhs)
{
uint64_t const lo_lo = (lhs & 0xFFFFFFFF) * (rhs & 0xFFFFFFFF);
uint64_t const hi_lo = ((lhs >> 32) * (rhs & 0xFFFFFFFF)) + (lo_lo >> 32);
uint64_t const lo_hi = ((lhs & 0xFFFFFFFF) * (rhs >> 32)) + (hi_lo & 0xFFFFFFFF);
uint64_t const product_hi = ((lhs >> 32) * (rhs >> 32)) + (lo_hi >> 32) + (hi_lo >> 32);
uint64_t const product_lo = (lo_lo & 0xFFFFFFFF) | (lo_hi << 32);
return product_hi ^ product_lo;
}
gcc 8.3.0 -m32 -O3 -march=i686
mult_yann: 3.083638 5278c6468d75cb00
mult_hd: 2.321105 5278c6468d75cb00
mult_njuffa: 2.559749 5278c6468d75cb00
mult_accu: 2.511064 5278c6468d75cb00
mult_code_project: 2.418673 5278c6468d75cb00
mul_botan: 2.533887 5278c6468d75cb00
clang 8.0.0 -O3 -m32 -march=i686
mult_yann: 2.124179 7be8a9a01751f680
mult_hd: 2.022154 7be8a9a01751f680
mult_njuffa: 2.300277 7be8a9a01751f680
mult_accu: 1.980426 7be8a9a01751f680
mult_code_project: 1.974299 7be8a9a01751f680
mul_botan: 2.270755 7be8a9a01751f680
Note: mult_code_project, mult_accu, and mult_hd all generate the same assembly from Clang, mainly because they are all based on the same code:
_mult_hd: ## @mult_hd
## %bb.0:
push ebp
push ebx
push edi
push esi
push eax
mov ecx, dword ptr [esp + 32]
mov ebx, dword ptr [esp + 36]
mov esi, dword ptr [esp + 24]
mov eax, ecx
mul esi
mov edi, edx
mov dword ptr [esp], eax ## 4-byte Spill
mov eax, ecx
mul dword ptr [esp + 28]
mov ecx, edx
mov ebp, eax
mov eax, ebx
mul esi
mov esi, edx
mov ebx, eax
mov eax, dword ptr [esp + 36]
mul dword ptr [esp + 28]
add ebp, edi
adc eax, ecx
adc edx, 0
add ebp, ebx
adc eax, esi
adc edx, 0
xor eax, dword ptr [esp] ## 4-byte Folded Reload
xor edx, ebp
add esp, 4
pop esi
pop edi
pop ebx
pop ebp
ret
Unfortunately, GCC generates considerably worse code on all of them, but this remains the best version:
_mult_hd:
sub esp, 44
mov dword ptr [esp + 28], ebx
mov ecx, dword ptr [esp + 48]
mov dword ptr [esp + 40], ebp
mov ebx, dword ptr [esp + 56]
mov dword ptr [esp + 36], edi
mov ebp, dword ptr [esp + 52]
mov dword ptr [esp + 32], esi
mov eax, ecx
mul ebx
mov dword ptr [esp + 4], edx
mov dword ptr [esp], eax
mov edi, dword ptr [esp + 4]
mov eax, ebx
mul ebp
mov esi, edi
xor edi, edi
add esi, eax
mov eax, ecx
adc edi, edx
mul dword ptr [esp + 60]
mov ecx, eax
mov ebx, edx
mov eax, ebp
xor edx, edx
add ecx, esi
mov dword ptr [esp + 8], ecx
adc ebx, edx
xor esi, esi
mul dword ptr [esp + 60]
mov dword ptr [esp + 12], ebx
mov ebx, dword ptr [esp]
mov ebp, dword ptr [esp + 12]
mov ecx, dword ptr [esp + 8]
mov dword ptr [esp + 16], eax
mov eax, edi
add eax, dword ptr [esp + 16]
mov dword ptr [esp + 20], edx
mov edx, esi
mov edi, ebp
adc edx, dword ptr [esp + 20]
mov esi, edi
xor ebp, ebp
add eax, esi
mov esi, dword ptr [esp + 32]
mov edi, eax
mov eax, ebx
mov ebx, dword ptr [esp + 28]
adc edx, ebp
xor eax, edi
mov ebp, dword ptr [esp + 40]
xor edx, ecx
mov edi, dword ptr [esp + 36]
add esp, 44
ret
A lot of people from the GNU community ask why I dislike GCC a lot.
I personally believe I have some valid reasons.
We can certainly make those changes, they are nice improvements.
As for documentation, here is my idea for XXH3_accumulate_512.
/* This is the main mixer for large data blocks. This is written in SIMD code if possible.
*
* acc = ((data \oplus key) \mod 2 ^ {32} * \frac {data \oplus key} {2 ^ {32}}) + data + acc
*
* This is a modified version of the long multiply method used in UMAC and FARSH.
* The changes are that data and key are xored instead of added, and the original data
* is directly added to the mix after the multiply to prevent multiply-by-zero issues. */
What is your thoughts of putting LaTeX in the comments? Wikipedia has explained some of them that way.
It expands to this:

I think this is a good documentation.
I'm also opened to using latex in the comments.
While reading formula is not straightforward without a parser, it remains human-readable.
I don't know of any better counter-proposal. Even markdeep defers to LaTex for mathematical formulas.
Since I could not find any more improvement, I guess I'm done with the 64-bit variant.
I'm going to merge the xxh3 branch soon, after updating the self-tests, and verifying portability.
The 128-bits version still needs updating.
Yeah, I want to be sure the NEON code matches because I am a little worried that it isn't.
The 64-bit variant definitely looks good to me.
After that, should we work on that dispatcher? It is mostly complete, but I dunno how well it would work in the field. I presume most people who are distributing binaries would want the dispatcher.
I am also considering dispatching ARMv7a. There are some chips without NEON. However, detecting it is really difficult mainly because even though there is an instruction for it, you can't call it because it has a high privilege level. The Android NDK does have a function for that, and all iOS 5+ devices have it. It's low priority at the moment, though, as these devices are genuinely rare.
However, coming from someone who literally doesn't have a chip with AVX2, supporting both SSE2 and AVX2 in the same binary is far more important. I approximate that 80-90% of the people using x86 chips have no idea whether their chip supports AVX2 or not, so distributing separate builds would be confusing af to them.
Having a dispatcher seems like a good idea, but we'll have to be cautious on its potential runtime impact.
Say, someone just calls XXH3_64bits() on a small input, expecting low-latency performance,
what does the dispatcher do in this case ? Does it add a test to decide which variant is more appropriate ?
I guess the test is probably fine if the amount of data to process is large enough. Now, how much is "large enough" ?
Quick note : in the near future, I intend to introduce a streaming variant. The streaming variant will require the creation of a state. Such state might help, to store some test result, avoiding to probe the cpu every time.
I have a static variable, as well as a getter and a setter.
On GCC, the test is done __before__ main(), and other compilers check whether the test has been initialized in XXH3_hashLong, and do the check there.
#ifdef XXH_MULTI_TARGET /* verified beforehand */
/* Prototypes for our code */
#ifdef __cplusplus
extern "C" {
#endif
void _XXH3_hashLong_AVX2(U64* acc, const void* data, size_t len, const U32* key);
void _XXH3_hashLong_SSE2(U64* acc, const void* data, size_t len, const U32* key);
void _XXH3_hashLong_Scalar(U64* acc, const void* data, size_t len, const U32* key);
#ifdef __cplusplus
}
#endif
/* What hashLong version we decided on. cpuid is a SLOW instruction -- calling it takes anywhere
* from 30-40 to THOUSANDS of cycles, so we really don't want to call it more than once. */
static XXH_cpu_mode_t cpu_mode = XXH_CPU_MODE_AUTO;
/* xxh3-target.c will include this file. If we don't do this, the constructor will be called
* multiple times. We don't want that. */
#if !defined(XXH3_TARGET_C) && defined(__GNUC__)
__attribute__((__constructor__))
#endif
static void
XXH3_featureTest(void)
{
int max, data[4];
/* First, get how many CPUID function parameters there are by calling CPUID with eax = 0. */
XXH_CPUID(data, /* eax */ 0);
max = data[0];
/* AVX2 is on the Extended Features page (eax = 7, ecx = 0), on bit 5 of ebx. */
if (max >= 7) {
XXH_CPUIDEX(data, /* eax */ 7, /* ecx */ 0);
if (data[1] & (1 << 5)) {
cpu_mode = XXH_CPU_MODE_AVX2;
return;
}
}
/* SSE2 is on the Processor Info and Feature Bits page (eax = 1), on bit 26 of edx. */
if (max >= 1) {
XXH_CPUID(data, /* eax */ 1);
if (data[3] & (1 << 26)) {
cpu_mode = XXH_CPU_MODE_SSE2;
return;
}
}
/* Must be scalar. */
cpu_mode = XXH_CPU_MODE_SCALAR;
}
static void
XXH3_hashLong(U64* restrict acc, const void* restrict data, size_t len, const U32* restrict key)
{
/* We haven't checked CPUID yet, so we check it now. On GCC, we try to get this to run
* at program startup to hide our very dirty secret from the benchmarks. */
if (cpu_mode == XXH_CPU_MODE_AUTO) {
XXH3_featureTest();
}
switch (cpu_mode) {
case XXH_CPU_MODE_AVX2:
_XXH3_hashLong_AVX2(acc, data, len, key);
return;
case XXH_CPU_MODE_SSE2:
_XXH3_hashLong_SSE2(acc, data, len, key);
return;
default:
_XXH3_hashLong_Scalar(acc, data, len, key);
return;
}
}
#else /* !XXH_MULTI_TARGET */
/* Include the C file directly and let the compiler decide which implementation to use. */
# include "xxh3-target.c"
#endif /* XXH_MULTI_TARGET */
/* Should we keep this? */
XXH_PUBLIC_API void XXH3_forceCpuMode(XXH_cpu_mode_t mode)
{
#ifdef XXH_MULTI_TARGET
cpu_mode = mode;
#endif
}
/* Should we keep this? */
XXH_PUBLIC_API XXH_cpu_mode_t XXH3_getCpuMode(void)
{
#ifdef XXH_MULTI_TARGET
return cpu_mode;
#else
return (XXH_cpu_mode_t) XXH_VECTOR;
#endif
}
Unless you manually reset it, cpuid is never called more than three times.
As for how it works, xxh3-target.c has the implementation of XXH3_hashLong, but the actual symbol name is defined by a macro, which will just be XXH3_hashLong on non-multitargeting code.
#ifdef XXH_MULTI_TARGET
/* The use of reserved identifiers is intentional; these are not to be used directly. */
# if XXH_VECTOR == XXH_AVX2
# define hashLong _XXH3_hashLong_AVX2
# elif XXH_VECTOR == XXH_SSE2
# define hashLong _XXH3_hashLong_SSE2
# else
# define hashLong _XXH3_hashLong_Scalar
# endif
#else
# define hashLong XXH3_hashLong
#endif
So yeah, I tried to make it as cheap as possible.

I do want to mention that t1ha0 uses a function pointer instead of a jump table. IDK which is better.
#if T1HA_USE_INDIRECT_FUNCTIONS
/* Use IFUNC (GNU ELF indirect functions) to choice implementation at runtime.
* For more info please see
* https://en.wikipedia.org/wiki/Executable_and_Linkable_Format
* and https://sourceware.org/glibc/wiki/GNU_IFUNC */
#if __has_attribute(ifunc)
uint64_t t1ha0(const void *data, size_t len, uint64_t seed)
__attribute__((ifunc("t1ha0_resolve")));
#else
__asm("\t.globl\tt1ha0\n\t.type\tt1ha0, "
"%gnu_indirect_function\n\t.set\tt1ha0,t1ha0_resolve");
#endif /* __has_attribute(ifunc) */
#elif __GNUC_PREREQ(4, 0) || __has_attribute(constructor)
uint64_t (*t1ha0_funcptr)(const void *, size_t, uint64_t);
static __cold void __attribute__((constructor)) t1ha0_init(void) {
t1ha0_funcptr = t1ha0_resolve();
}
#else /* T1HA_USE_INDIRECT_FUNCTIONS */
static __cold uint64_t t1ha0_proxy(const void *data, size_t len,
uint64_t seed) {
t1ha0_funcptr = t1ha0_resolve();
return t1ha0_funcptr(data, len, seed);
}
uint64_t (*t1ha0_funcptr)(const void *, size_t, uint64_t) = t1ha0_proxy;
#endif /* !T1HA_USE_INDIRECT_FUNCTIONS */
#endif /* T1HA0_RUNTIME_SELECT */
For proof, I added a logger in XXH_CPUID which showed every time it was called.
CPUID called!
CPUID called!
CPUID called!
./xxhsum 0.7.0 (64-bits x86_64 + SSE2 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH3 mode: SSE2
XXH32 : 102400 -> 85294 it/s ( 8329.5 MB/s)
XXH32 unaligned : 102400 -> 49981 it/s ( 4880.9 MB/s)
XXH64 : 102400 -> 74702 it/s ( 7295.1 MB/s)
XXH64 unaligned : 102400 -> 72518 it/s ( 7081.8 MB/s)
XXH3_64bits : 102400 -> 173765 it/s (16969.3 MB/s)
XXH3_64b unaligned : 102400 -> 171794 it/s (16776.8 MB/s)
also, my processor randomly went into super-sayian mode for XXH32. Probably a misread :thinking:
wait, this is happening every time…

HOLD THE PHONE
I did this when I was testing ARMv6t2
if (((size_t)input & 3) == 0) {
const U32* p32 = (const U32*) __builtin_assume_aligned(p, 4);
do {
v1 = XXH32_round(v1, *p32++);
v2 = XXH32_round(v1, *p32++);
v3 = XXH32_round(v1, *p32++);
v4 = XXH32_round(v1, *p32++);
} while ((const BYTE*)p32 < limit);
p = (const BYTE*)p32;
} else {
do {
v1 = XXH32_round(v1, XXH_get32bits(p)); p+=4;
v2 = XXH32_round(v2, XXH_get32bits(p)); p+=4;
v3 = XXH32_round(v3, XXH_get32bits(p)); p+=4;
v4 = XXH32_round(v4, XXH_get32bits(p)); p+=4;
} while (p < limit);
}
wait, I stupid. v1 v1 v1 v1. noice one me.
v1 = XXH32_round(v1, *p32++);
v2 = XXH32_round(v1, *p32++);
v3 = XXH32_round(v1, *p32++);
v4 = XXH32_round(v1, *p32++);
nvm, my b.
OK, I think the multi-target looks good.
Of great importance :
XXH_MULTI_TARGET build macro.The second point is particularly important. You would be surprised : package managers actually dislike things which are runtime-decided. They are not end-users. Some of them might actually prefer a clear simple binary behavior, with less maintenance risks, even if it means forgiving performance for some targets.
One thing which is not too clear for me is if this mechanism enforces the existence of xxh3.h, as a way to generate multiple targets.
xxh3.h is a temporary file, which will disappear when the algorithm stabilizes : its code will be integrated into xxhash.c.
xxh3.h is not required, however, I did add xxh3-target.c, which is the file that is included or compiled three times.
This is the only clean way to do it. We could technically use macro hell, but that would be super ugly and confusing.
Basically, the build process is this when running make MULTI_TARGET=1 xxhsum
cc -O3 -DXXH_MULTI_TARGET -c -o xxhsum.o xxhsum.c
cc -O3 -DXXH_MULTI_TARGET -c -o xxhash.o xxhash.c
cc -c -O3 -DXXH_MULTI_TARGET xxh3-target.c -mavx2 -o xxh3-avx2.o
cc -c -O3 -DXXH_MULTI_TARGET xxh3-target.c -msse2 -mno-sse3 -o xxh3-sse2.o
cc -c -O3 -DXXH_MULTI_TARGET xxh3-target.c -mno-sse2 -o xxh3-scalar.o
cc xxhsum.o xxhash.o xxh3-avx2.o xxh3-sse2.o xxh3-scalar.o -o xxhsum
Without it, it is like this: (xxh3-target.c is included like a .h file)
cc -O3 -c -o xxhsum.o xxhsum.c
cc -O3 -c -o xxhash.o xxhash.c
cc xxhsum.o xxhash.o -o xxhsum
Also, I think I am liking the function pointer better. It skips the jump table.
#ifdef XXH_MULTI_TARGET
/* Prototypes for our code */
#ifdef __cplusplus
extern "C" {
#endif
void _XXH3_hashLong_AVX2(U64* acc, const void* data, size_t len, const U32* key);
void _XXH3_hashLong_SSE2(U64* acc, const void* data, size_t len, const U32* key);
void _XXH3_hashLong_Scalar(U64* acc, const void* data, size_t len, const U32* key);
#ifdef __cplusplus
}
#endif
/* What hashLong version we decided on. cpuid is a SLOW instruction -- calling it takes anywhere
* from 30-40 to THOUSANDS of cycles), so we really don't want to call it more than once. */
static XXH_cpu_mode_t cpu_mode = XXH_CPU_MODE_AUTO;
/* The best XXH3 version that is supported. This is used for verification on XXH_setCpuMode to prevent
* a SIGILL. It can be turned off with -DXXH_NO_VERIFY_MULTI_TARGET, in which the selected hash will
* be used unconditionally. */
static XXH_cpu_mode_t supported_cpu_mode = XXH_CPU_MODE_AUTO;
/* We also store this as a function pointer, so we can just jump to it at runtime.
* This matches the technique used by t1ha.
* XXX: Are ifuncs better for ELF? */
static void (*XXH3_hashLong)(U64* acc, const void* data, size_t len, const U32* key);
/* Tests features for x86 targets and sets the cpu_mode and the XXH3_hashLong function pointer
* to the correct value.
*
* On GCC compatible compilers, this will be run at program startup.
*
* xxh3-target.c will include this file. If we don't do this, the constructor will be called
* multiple times. We don't want that. */
#if !defined(XXH3_TARGET_C) && defined(__GNUC__)
__attribute__((__constructor__))
#endif
static void XXH3_featureTest(void)
{
int max, data[4];
/* First, get how many CPUID function parameters there are by calling CPUID with eax = 0. */
XXH_CPUID(data, /* eax */ 0);
max = data[0];
/* AVX2 is on the Extended Features page (eax = 7, ecx = 0), on bit 5 of ebx. */
if (max >= 7) {
XXH_CPUIDEX(data, /* eax */ 7, /* ecx */ 0);
if (data[1] & (1 << 5)) {
cpu_mode = supported_cpu_mode = XXH_CPU_MODE_AVX2;
XXH3_hashLong = &_XXH3_hashLong_AVX2;
return;
}
}
/* SSE2 is on the Processor Info and Feature Bits page (eax = 1), on bit 26 of edx. */
if (max >= 1) {
XXH_CPUID(data, /* eax */ 1);
if (data[3] & (1 << 26)) {
cpu_mode = supported_cpu_mode = XXH_CPU_MODE_SSE2;
XXH3_hashLong = &_XXH3_hashLong_SSE2;
return;
}
}
/* At this point, we fall back to scalar. */
cpu_mode = supported_cpu_mode = XXH_CPU_MODE_SCALAR;
XXH3_hashLong = &_XXH3_hashLong_Scalar;
}
/* Sets up the dispatcher and then calls the actual hash function. */
static void
XXH3_dispatcher(U64* restrict acc, const void* restrict data, size_t len, const U32* restrict key)
{
/* We haven't checked CPUID yet, so we check it now. On GCC, we try to get this to run
* at program startup to hide our very dirty secret from the benchmarks. */
XXH3_featureTest();
XXH3_hashLong(acc, data, len, key);
}
/* Default the function pointer to the dispatcher. */
static void (*XXH3_hashLong)(U64* acc, const void* data, size_t len, const U32* key) = &XXH3_dispatcher;
#else /* !XXH_MULTI_TARGET */
/* Include the C file directly and let the compiler decide which implementation to use. */
# include "xxh3-target.c"
#endif /* XXH_MULTI_TARGET */
/* Sets the XXH3_hashLong variant. When XXH_MULTI_TARGET is not defined, this
* does nothing.
*
* Unless XXH_NO_VERIFY_MULTI_TARGET is defined, this will automatically fall back
* to the next best XXH3 mode, so, for example, even if you set it to AVX2, the code
* will not crash even if it is run on, for example, a Core 2 Duo which doesn't support
* AVX2. */
XXH_PUBLIC_API void XXH3_forceCpuMode(XXH_cpu_mode_t mode)
{
#ifdef XXH_MULTI_TARGET
/* Defining XXH_NO_VERIFY_MULTI_TARGET will allow you to set the CPU mode to
* an unsupported mode. */
#ifndef XXH_NO_VERIFY_MULTI_TARGET
# define TRY_SET_MODE(mode, funcptr) \
if (supported_cpu_mode >= (mode)) { \
cpu_mode = (mode); \
XXH3_hashLong = &(funcptr); \
return; \
}
if (supported_cpu_mode == XXH_CPU_MODE_AUTO)
XXH3_featureTest();
#else
# define TRY_SET_MODE(mode, funcptr) \
cpu_mode = (mode); \
XXH3_hashLong = &(funcptr); \
return;
#endif
switch (mode) {
case XXH_CPU_MODE_AVX2:
TRY_SET_MODE(XXH_CPU_MODE_AVX2, _XXH3_hashLong_AVX2);
/* FALLTHROUGH */
case XXH_CPU_MODE_SSE2:
TRY_SET_MODE(XXH_CPU_MODE_SSE2, _XXH3_hashLong_SSE2);
/* FALLTHROUGH */
case XXH_CPU_MODE_SCALAR:
cpu_mode = XXH_CPU_MODE_SCALAR;
XXH3_hashLong = &_XXH3_hashLong_Scalar;
return;
case XXH_CPU_MODE_NEON: /* ignored */
case XXH_CPU_MODE_AUTO:
default:
cpu_mode = XXH_CPU_MODE_AUTO;
XXH3_hashLong = &XXH3_dispatcher;
return;
}
#undef TRY_SET_MODE
#endif
}
/* Returns which XXH3 mode we are using. */
XXH_PUBLIC_API XXH_cpu_mode_t XXH3_getCpuMode(void)
{
#ifdef XXH_MULTI_TARGET
return cpu_mode;
#else
return (XXH_cpu_mode_t) XXH_VECTOR;
#endif
}
A hidden requirement on this project is to keep it as a 2 files library if possible (xxhash.c and xxhash.h).
I think this is possible. Last year, I made a similar patch for zstd.
The idea was :
_internal function, which carries the code to be specialized. It's never call directly, and must be inlined.__attribute__ to specialize for a target, and calling the _internal function, which is now inlined, hence implemented, several times.In xxh3 case, I believe it's even simpler : since the SSE2, AVX2 and NEON implementations are already explicit, it's not even necessary to have this 2-stages. One can go straight to specialized functions. Just split accumulate512 and scramble into their respective variants. Exclude the unwanted ones from compilation. Then call the wanted one.
I'm fine with function pointer approach.
I did that for my XXH64 SSE2 implementation; I used __attribute__((__target__)).
However, it is not compatible with MSVC. MSVC is (unfortunately?) very popular among Windows users. The only way to do it for MSVC (unless I am mistaken) is to compile the file multiple times.
__attribute__((__target__)) also messed with conditionally enabled functions on older GCC/Clang versions iirc
The choices are:
Side note, unrelated to XXH3. I was messing with inline assembly for XXH64 and came up with this (pop it in XXH64_endian_align):
U64 inp1, inp2, inp3, inp4;
do {
#if defined(__GNUC__) && defined(__x86_64__)
__asm__(
"movq (%[p]), %[inp1]\n"
"movq 8(%[p]), %[inp2]\n"
"movq 16(%[p]), %[inp3]\n"
"movq 24(%[p]), %[inp4]\n"
"imulq %[prime2], %[inp1]\n"
"imulq %[prime2], %[inp2]\n"
"imulq %[prime2], %[inp3]\n"
"imulq %[prime2], %[inp4]\n"
"addq %[inp1], %[v1]\n"
"addq %[inp2], %[v2]\n"
"addq %[inp3], %[v3]\n"
"addq %[inp4], %[v4]\n"
#if defined(__BMI2__)
"rorxq $33, %[v1], %[v1]\n"
"rorxq $33, %[v2], %[v2]\n"
"rorxq $33, %[v3], %[v3]\n"
"rorxq $33, %[v4], %[v4]\n"
#elif defined(__AVX__)
"shldq $31, %[v1], %[v1]\n"
"shldq $31, %[v2], %[v2]\n"
"shldq $31, %[v3], %[v3]\n"
"shldq $31, %[v4], %[v4]\n"
#else
"rolq $31, %[v1]\n"
"rolq $31, %[v2]\n"
"rolq $31, %[v3]\n"
"rolq $31, %[v4]\n"
#endif
"imulq %[prime1], %[v1]\n"
"imulq %[prime1], %[v2]\n"
"leaq 32(%[p]), %[p]\n"
"imulq %[prime1], %[v3]\n"
"imulq %[prime1], %[v4]\n"
: [p] "+r" (p), [inp1] "=&r" (inp1), [inp2] "=&r" (inp2), [inp3] "=&r" (inp3), [inp4] "=&r" (inp4), [v1] "+r" (v1), [v2] "+r" (v2), [v3] "+r" (v3), [v4] "+r" (v4)
: [prime1] "r" (PRIME64_1), [prime2] "r" (PRIME64_2));
#else
v1 = XXH64_round(v1, XXH_get64bits(p)); p+=8;
v2 = XXH64_round(v2, XXH_get64bits(p)); p+=8;
v3 = XXH64_round(v3, XXH_get64bits(p)); p+=8;
v4 = XXH64_round(v4, XXH_get64bits(p)); p+=8;
#endif
} while (p<=limit);
Just curious, what do you get with -march=native on your chip (I'm assuming it has BMI2).
Toying with VSX on a ppc64le IBM POWER9 9006-22P machine on the GCC farm. (Which only has vim on it, my least favorite editor :rage:)
Naive VSX implementation I adapted from the terrible documentation and HighwayHash:
#include <altivec.h>
typedef __vector unsigned long long U64x2;
typedef __vector unsigned U32x4;
XXH_FORCE_INLINE U64x2 XXH_multEven(U32x4 a, U32x4 b) { // NOLINT
U64x2 result; // NOLINT
#ifdef __LITTLE_ENDIAN__
__asm__("vmulouw %0, %1, %2" : "=v"(result) : "v"(a), "v"(b));
#else
__asm__("vmuleuw %0, %1, %2" : "=v"(result) : "v"(a), "v"(b));
#endif
return result;
}
XXH_FORCE_INLINE U64x2 XXH_multOdd(U32x4 a, U32x4 b) { // NOLINT
U64x2 result; // NOLINT
#ifdef __LITTLE_ENDIAN__
__asm__("vmuleuw %0, %1, %2" : "=v"(result) : "v"(a), "v"(b));
#else
__asm__("vmuloww %0, %1, %2" : "=v"(result) : "v"(a), "v"(b));
#endif
return result;
}
XXH_FORCE_INLINE void
XXH3_accumulate_512(void *restrict acc, const void *restrict data, const void *restrict key)
{
U64x2 *const xacc = (U64x2*)acc;
U64x2 const *const xdata = (U64x2 const*)data;
U64x2 const *const xkey = (U64x2 const*)key;
U64x2 const thirtytwo = { 32, 32 };
size_t i;
for (i = 0; i < STRIPE_LEN / sizeof(U64x2); i++) {
U64x2 data_vec = vec_vsx_ld(0, xdata + i);
U64x2 key_vec = vec_vsx_ld(0, xkey + i);
U64x2 data_key = data_vec ^ key_vec;
U32x4 shuffled = (U32x4)vec_rl(data_key, thirtytwo);
U32x4 data_key32 = (U32x4)data_key;
U64x2 product = XXH_multEven(data_key32, shuffled);
xacc[i] += product;
xacc[i] += data_vec;
}
}
XXH_FORCE_INLINE void
XXH3_scrambleAcc(void* restrict acc, const void* restrict key)
{
U64x2*const xacc = (U64x2*)acc;
const U64x2 *const xkey = (const U64x2*)key;
U64x2 const thirtytwo = { 32, 32 };
U32x4 const prime1 = { PRIME32_1, PRIME32_1, PRIME32_1, PRIME32_1 };
size_t i;
for (i = 0; i < STRIPE_LEN / sizeof(U64x2); i++) {
U64x2 const acc_vec = xacc[i];
U64x2 const data_vec = acc_vec ^ (acc_vec >> 47);
U64x2 const key_vec = vec_vsx_ld(0, xkey);
U64x2 const data_key = data_vec ^ key_vec;
U64x2 const prod_lo = XXH_multEven((U32x4)data_key, prime1);
U64x2 const prod_hi = XXH_multOdd((U32x4)data_key, prime1);
xacc[i] = prod_lo + (prod_hi << 32);
}
}
VSX mode:
./xxhsum 0.7.0 (64-bits ppc64 little endian), GCC 4.8.5 20150623 (Red Hat 4.8.5-36), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 47231 it/s ( 4612.4 MB/s)
XXH32 unaligned : 102400 -> 51200 it/s ( 5000.0 MB/s)
XXH64 : 102400 -> 153600 it/s (15000.0 MB/s)
XXH64 unaligned : 102400 -> 153600 it/s (15000.0 MB/s)
XXH3_64bits : 102400 -> 61440 it/s ( 6000.0 MB/s)
XXH3_64b unaligned : 102400 -> 51200 it/s ( 5000.0 MB/s)
Scalar code:
./xxhsum 0.7.0 (64-bits ppc64 little endian), GCC 4.8.5 20150623 (Red Hat 4.8.5-36), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 46759 it/s ( 4566.3 MB/s)
XXH32 unaligned : 102400 -> 51200 it/s ( 5000.0 MB/s)
XXH64 : 102400 -> 153600 it/s (15000.0 MB/s)
XXH64 unaligned : 102400 -> 111306 it/s (10869.7 MB/s)
XXH3_64bits : 102400 -> 102400 it/s (10000.0 MB/s)
XXH3_64b unaligned : 102400 -> 76800 it/s ( 7500.0 MB/s)
However, apparently, since it has GCC 4.8.5, it is terrible code output. I generated some assembly with Clang and linked it together, and I got something much nicer.
./xxhsum 0.7.0 (64-bits ppc64 little endian), GCC 4.8.5 20150623 (Red Hat 4.8.5-36), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 47211 it/s ( 4610.5 MB/s)
XXH32 unaligned : 102400 -> 51200 it/s ( 5000.0 MB/s)
XXH64 : 102400 -> 153600 it/s (15000.0 MB/s)
XXH64 unaligned : 102400 -> 153600 it/s (15000.0 MB/s)
XXH3_64bits : 102400 -> 307200 it/s (30000.0 MB/s)
XXH3_64b unaligned : 102400 -> 307200 it/s (30000.0 MB/s)
Edit: Yeah, GCC is puking assembly. It doesn't help that the GCC version is so old that it doesn't fully support the chip it was running on.
$ gcc -mcpu=power9
gcc: error: unrecognized argument in option ‘-mcpu=power9’
gcc: note: valid arguments to ‘-mcpu=’ are: 401 403 405 405fp 440 440fp 464 464fp 476 476fp 505 601 602 603 603e 604 604e 620 630 740 7400 7450 750 801 821 823 8540 8548 860 970 G3 G4 G5 a2 cell e300c2 e300c3 e500mc e500mc64 e5500 e6500 ec603e native power3 power4 power5 power5+ power6 power6x power7 power8 powerpc powerpc64 powerpc64le rs64 titan
gcc: fatal error: no input files
compilation terminated.
Indeed, this is night and day difference
Tried downloading a clang release tarball
./clang: /lib64/ld64.so.2: version `GLIBC_2.22' not found (required by ./clang)
./clang: /usr/lib64/libstdc++.so.6: version `GLIBCXX_3.4.22' not found (required by ./clang)
./clang: /usr/lib64/libstdc++.so.6: version `GLIBCXX_3.4.20' not found (required by ./clang)
./clang: /usr/lib64/libstdc++.so.6: version `GLIBCXX_3.4.21' not found (required by ./clang)
Damn it. Worth a shot.
Eyy, I got Clang 8 to work.
I had to first compile GCC from source to get libstdc++, then I had to compile glibc from source, which needs Python 3 and a newer make, and then I had to patch Clang to use the correct ld.so and set a wrapper.
Worth it. Time to dump all my changes because it is only going to get more complicated.
But yay, we have VSX support! The server and supercomputer users which still use POWER will be happy.
OK. Scalar, NEON, VSX, and SSE2 are all failing test 52 (when I remove the first #if 0) with the same value, so I am not too concerned about it.
./xxhsum 0.7.0 (64-bits x86_64 + SSE2 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Error: 64-bit hash test 52: Internal sanity check failed!
Got 0x082520CD9A539D2AULL, expected 0x802EB54C97564FD7ULL.
Note: If you modified the hash functions, make sure to either update the values
or temporarily comment out the tests in BMK_sanityCheck.
PR is open now.
Dispatching, better intrinsic documentation, and VSX support is added.
Oof.
I managed to get GCC to emit some decent multiply code…
mult_hd_llvm:
push ebp
push edi
xor edi, edi
push esi
push ebx
sub esp, 12
mov ecx, dword ptr [esp + 32]
mov ebx, dword ptr [esp + 40]
mov ebp, dword ptr [esp + 36]
mov eax, ecx
mul ebx
mov dword ptr [esp], eax
mov eax, ebx
mov esi, edx
mov dword ptr [esp + 4], edx
mul ebp
add esi, eax
mov eax, ecx
adc edi, edx
mul dword ptr [esp + 44]
mov ecx, eax
mov ebx, edx
xor edx, edx
add ecx, esi
mov eax, ebp
mov esi, edi
adc ebx, edx
xor edi, edi
mul dword ptr [esp + 44]
add eax, esi
adc edx, edi
xor ebp, ebp
add eax, ebx
mov ebx, dword ptr [esp]
adc edx, ebp
mov edi, eax
add esp, 12
xor edx, ecx
mov eax, ebx
pop ebx
xor eax, edi
pop esi
pop edi
pop ebp
ret
only by translating LLVM's output…
define i64 @mult_hd(i64, i64) local_unnamed_addr #0 {
%3 = lshr i64 %0, 32
%4 = lshr i64 %1, 32
%5 = and i64 %0, 4294967295
%6 = and i64 %1, 4294967295
%7 = mul nuw i64 %6, %5
%8 = mul nuw i64 %6, %3
%9 = lshr i64 %7, 32
%10 = add i64 %9, %8
%11 = mul nuw i64 %4, %5
%12 = and i64 %10, 4294967295
%13 = add i64 %12, %11
%14 = mul nuw i64 %4, %3
%15 = lshr i64 %13, 32
%16 = lshr i64 %10, 32
%17 = add i64 %16, %14
%18 = add i64 %17, %15
%19 = and i64 %7, 4294967295
%20 = shl i64 %13, 32
%21 = or i64 %20, %19
%22 = xor i64 %18, %21
ret i64 %22
}
…directly to C.
__attribute__((__noinline__, __target__("no-sse2")))
uint64_t mult_hd_clang(uint64_t const p0, uint64_t const p1)
{
uint64_t p3 = p0 & 0xFFFFFFFF;
uint64_t p4 = p1 & 0xFFFFFFFF;
uint64_t p5 = p4 * p3;
uint64_t p6 = p5 >> 32;
uint64_t p7 = p0 >> 32;
uint64_t p8 = p4 * p7;
uint64_t p9 = p6 + p8;
uint64_t p10 = p9 >> 32;
uint64_t p11 = p1 >> 32;
uint64_t p12 = p11 * p3;
uint64_t p13 = p9 & 0xFFFFFFFF;
uint64_t p14 = p13 + p12;
uint64_t p15 = p14 >> 32;
uint64_t p16 = p11 * p7;
uint64_t p17 = p10 + p16;
uint64_t p18 = p17 + p15;
uint64_t p19 = p14 << 32;
uint64_t p20 = p5 & 0xFFFFFFFF;
uint64_t p21 = p19 | p20;
uint64_t p22 = p18 ^ p21;
return p22;
}
One instruction per line. The ELI5 for compilers.
diff --git a/README.md b/README.md
index 96ecfec..ed4f4ec 100644
--- a/README.md
+++ b/README.md
@@ -11,7 +11,7 @@ Code is highly portable, and hashes are identical on all platforms (little / big
|master | [](https://travis-ci.org/Cyan4973/xxHash?branch=master) |
|dev | [](https://travis-ci.org/Cyan4973/xxHash?branch=dev) |
-
+Compile this with Clang. GCC is a highly overrated compiler that can't generate fast code unless you write it like assembly or *in* assembly.
Benchmarks
-------------------------
smh
@Cyan4973
Would this be a proper state struct?
typedef struct {
U64 acc[8]; /* ACC_NB */
BYTE input[1024]; /* block_len */
U64 seed;
U64 length;
U16 input_size;
BYTE seen_large_len; /* >= 1024 */
BYTE seen_medium_len; /* >= 16 */
U32 reserved; /* take advantage of padding memes */
} XXH3_state_t;
A hefty struct compared to the 48/88 byte XXH32 and XXH64 states.
The XXH3 struct state will have to be larger than XXH32 and XXH64.
But I believe it will only need to preserve 128 bytes of input.
With the accumulator, and other information, it will need 200+ bytes.
So you are basically saying we should have it start halfway in XXH3_accumulate?
So something like this:
typedef struct {
U64 acc[8]; /* 0-64 */
BYTE input[128]; /* 64-192 */
U64 seed; /* 192-200 */
U64 total_len; /* 200-208 */
BYTE input_size; /* 208-209 */
BYTE round_num; /* 209-210 which accumulate step we are on */
BYTE seen_large_len; /* 210-211 */
BYTE seen_medium_len; /* 211-212 */
U32 reserved; /* 212-216 */
} XXH3_state_t;
This weighs in at a much more reasonable 216 bytes (instead of 1112 bytes), although if we use larger types instead of packing it like I did, it will be a little larger. (So if we use U32, it would be 224 minus the reserved bit, and U64 would be 240), however, since we basically access these once per update, I don't see a reason not to pack them. What do you think?
Yes, something like that.
Also, it's not useful to try to save a few bytes. Actually, it's better to keep a little margin, in order to preserve the ability to introduce new features without breaking ABI (aka, the structure size, once published, should never change).
Maybe add a version number, so you can add more elements later and old software can at least detect new structures.
And maybe keep it multiple of 32 (or even 64) for cache optimization.
Adding a version number introduces new initialization problems. I hope we will be able to avoid them. I've only little experience with it, and unfortunately, so far, I have not found that method to be protective enough, while it directly impacts API design.
Keeping the size on a multiple (32/64) is reasonable.
We may have issues though with variable-size fields, such as pointers, or size_t.
The question is, why to worry about. The state is something local. It is nothing exported from one system to another. So it should be reasonable for the machine it is used on.
Therefore, yes, no version is needed.
But aligning the elements to benefit from caches might give the one or another µs of performance gain.
But I think it is already good aligned.
#define XXH3_ACCUMULATE_512_X86(vec_t, _mm_, _si) /* generic macro for sse2 and avx2 */ \
do { \
assert(((size_t)acc) & (sizeof(vec_t) - 1) == 0); \
{ \
ALIGN(sizeof(vec_t)) vec_t* const xacc = (vec_t *) acc; \
const vec_t* const xdata = (const vec_t *) data; \
const vec_t* const xkey = (const vec_t *) key; \
\
size_t i; \
for (i = 0; i < STRIPE_LEN / sizeof(vec_t); i++) { \
/* data_vec = xdata[i]; */ \
vec_t const data_vec = _mm_##loadu##_si (xdata + i); \
/* key_vec = xkey[i]; */ \
vec_t const key_vec = _mm_##loadu##_si (xkey + i); \
/* data_key = data_vec ^ key_vec; */ \
vec_t const data_key = _mm_##xor##_si (data_vec, key_vec); \
/* shuffled = data_key[1, undef, 3, undef]; // or data_key >> 32; */ \
vec_t const shuffled = _mm_##shuffle_epi32 (data_key, 0x31); \
/* product = (shuffled & 0xFFFFFFFF) * (data_key & 0xFFFFFFFF); */ \
vec_t const product = _mm_##mul_epu32 (shuffled, data_key); \
\
/* xacc[i] += data_vec; */ \
xacc[i] = _mm_##add_epi64 (xacc[i], data_vec); \
/* xacc[i] += product; */ \
xacc[i] = _mm_##add_epi64 (xacc[i], product); \
} \
} \
} while (0)
```c
#define XXH3_SCRAMBLE_ACC_X86(vec_t, _mm_, _si) /* generic macro for sse2 and avx2 / \
do { \
assert(((size_t)acc) & (sizeof(vec_t) - 1) == 0); \
{ \
ALIGN(sizeof(vec_t)) vec_t const xacc = (vec_t ) acc; \
const vec_t const xkey = (const vec_t ) key; \
const vec_t prime = _mm_##set1_epi32 ((int) PRIME32_1); \
size_t i; \
for (i = 0; i < STRIPE_LEN / sizeof(vec_t); i++) { \
/ data_vec = xacc[i] ^ (xacc[i] >> 47); / \
vec_t const acc_vec = xacc[i]; \
vec_t const shifted = _mm_##srli_epi64 (acc_vec, 47); \
vec_t const data_vec = _mm_##xor##_si (acc_vec, shifted); \
\
/ key_vec = xkey[i]; / \
vec_t const key_vec = _mm_##loadu##_si (xkey + i); \
/ data_key = data_vec ^ key_vec; / \
vec_t const data_key = _mm_##xor##_si (data_vec, key_vec); \
/ shuffled = data_key[1, undef, 3, undef]; // data_key >> 32; / \
vec_t const shuffled = _mm_##shuffle_epi32 (data_key, 0x31); \
\
/ data_key = PRIME32_1; // 32-bit * 64-bit */ \
\
/ prod_hi = data_key >> 32 * PRIME32_1; / \
vec_t const prod_hi = _mm_##mul_epu32 (shuffled, prime); \
/ prod_hi_top = prod_hi << 32; / \
vec_t const prod_hi_top = _mm_##slli_epi64 (prod_hi, 32); \
/ prod_lo = (data_key & 0xFFFFFFFF) * PRIME32_1; / \
vec_t const prod_lo = _mm_##mul_epu32 (data_key, prime); \
/ xacc[i] = prod_hi_top + prod_lo; */ \
xacc[i] = _mm_##add_epi64 (prod_hi_top, prod_lo); \
} \
} \
} while (0)
@Cyan4973 like this? If we are gonna do the GCC dispatch, this is better for it.
```c
__attribute__((__target__("avx2")))
void XXH3_accumulate_512_AVX2(void *restrict acc, const void *restrict key, const void *restrict data)
{
XXH3_ACCUMULATE_512_X86(__m256i, _mm256_, _si256);
}
__attribute__((__target__("avx2")))
void XXH3_scrambleAcc_AVX2(void *restrict acc, const void *restrict key)
{
XXH3_SCRAMBLE_ACC_X86(__m256i, _mm256_, _si256);
}
__attribute__((__target__("sse2")))
void XXH3_accumulate_512_SSE2(void *restrict acc, const void *restrict key, const void *restrict data)
{
XXH3_ACCUMULATE_512_X86(__m128i, _mm_, _si128);
}
__attribute__((__target__("sse2")))
void XXH3_scrambleAcc_SSE2(void *restrict acc, const void *restrict key)
{
XXH3_SCRAMBLE_ACC_X86(__m128i, _mm_, _si128);
}
It's true that AVX2 and SSE2 code path are very similar, featuring only some predictable name change.
And I also know your suggested construction works.
But I'm kind of cautious about it.
Defining large functions through macros can make debugging more challenging, and even impair readability.
I suspect the main expected benefit is that any change is automatically reported on both variant.
However :
All in all, I believe that readability is slightly negatively impacted, while writability benefits slightly.\
Over the long term, it's generally better for a source code to be "reader oriented".
So I think I prefer for both variants to be written clearly.
Ok. Gotcha.
Also, do you want the PPC64 code next?
Oh yes !
Opened discussion :
In branch xxh128, I'm testing a new formula for the 128-bit variant of XXH3.
The core concept is that each input influences 2 accumulators, hence 128-bit of state.
There are still 8 lanes, so total internal state is widened to 1024 bits.
This takes more memory, and makes initialization and termination more complex.
The design change was prompted by the claim that in the initial XXH3 proposal, since each lane is 64-bit, the combination of 8x 64-bit lanes is still a 64-bit hash.
I'm currently wondering if this statement is correct.
If it was about a cryptographic hash, it would be correct, indeed. Knowing the internal design of the hash algorithm, an attacker could concentrate its modifications into a single lane, and therefore have to search only through 64-bit, instead of 128-bit, in order to produce a collision.
But for a non-cryptographic hash, this is not supposed to be a scenario. As a checksum, xxHash mission is merely to provide a 128-bit random-like value, and guarantee that any __accidental__ change to the source has a 1 in 2^128 chance to generate the same hash. Almost as good as "none".
So one problem here is to define "accidental".
It obviously includes storage and transmission errors, such as truncation, block nullifying, noisy segment, etc. But it can also be something as light as a trivial field update in a larger file, such as a date in a movie's metadata.
The main claim is that a 128-bit hash using XXH3 initial design effectively degenerates into a 64-bit one if _all the changes happen in the same lane_. A lane is a serie of 8-bytes fields every 64-bytes. As soon as the change impacts 2 lanes, it impacts 128-bit of internal state, and the claim doesn't hold anymore.
Therefore, how probable is it that an accidental change only impacts a single lane ?
Well, that's a hard one, especially as changes and errors are rarely "randomly scattered". In general, multiple consecutive bytes are impacted. And as soon as this range of modified bytes is larger than 8 bytes, it impacts 2+ lanes. And if it's shorter than 8 bytes, then it's not enough to generate a collision.
Bottom line :
I'm okay with the fact that a bunch of 64-bit checksum combined do not make a 128-bit cryptographic checksum. But I'm unsure if the statement can be repeated unchanged for non-cryptographic checksums. This would require that a change only impacts one of those smaller checksum.
The fact that the lanes are interleaved makes it more difficult for an accidental change to _not_ impact 2+ lanes. Such event must have a probability of appearance. It's clearly not 100%, but how much is it ?
Should it be < 1 in 2^64, I'm wondering if it would qualify the 8x64-bit design as "good enough" for a 128-bit checksum
In branch wsecret, I'm modifying slightly the API to make it "secret first".
It always was the plan to make the algorithm able to consume any external source of secret.
Since the secret is involved at every step of the calculation, it makes it more difficult to generate a collision without knowledge of the secret.
With this design in place, the seed is now just a convenient short handle, able to generate a custom secret based on the combination of the default secret and some transform dependent on the seed. It's less powerful, but still makes a decent job at hardening the hash generator.
As a consequence, the result of the hash for len==0 must be updated, as it used to be the seed value, but :
1) The seed is no longer central. The expectation is that users interested in security will rather provide their own secret, which is much richer than 8 bytes.
2) If one makes the hash of the empty string a value depending on the secret, it cannot be the seed, since the simulated "seed" for custom secrets is 0. Therefore different secrets always return the same value 0 anyway.
3) Making seed the return value when len==0 makes it easy for any external observer to get the seed, thus simplifying next step (generate collisions).
As a consequence, I've simplified this part : the hash of the empty string is now always 0, whatever the seed or the custom secret.
I suspect it's a very low priority topic, but if someone believes that the hash of the empty string should change when the secret changes, due to some scenario depending on it, this is still a design decision that can be reviewed during this design phase.
In branch wsecret, the "secret" is now defined as "any blob of bytes" respecting a minimum size.
This is a small but important change compared to its previous definition, as a table of 32-bit values. This is designed to remove any compatibility complexity with regards to platform's endianess.
It's also supposed to remove any alignment restriction, so the "custom secret" can really be anything.
As a consequence, the "secret" must be consumed in a way which is endian independent.
This is achieved by XXH3_readKey64(), which effectively delegates to XXH_readLE64() now, which is both endian and alignment independent.
But this read function is bypassed when using the vector instruction set.
For SSE2 and AVX2, no problem : code uses _mm_loadu_si128() or _mm256_loadu_si256(), which do not need any alignment restriction, so it's fine.
For NEON and VSX, that's less clear to me, because I'm not fluent in these instruction sets and have difficulty to find useful information on Internet (Google search brings up a ton of barely relevant pages). @easyaspi314 , I'll need your help on these. I suspect it's fine, as vld1q_u32() (NEON) and vec_vsx_ld() (VSX) are used for both key and data, and there already was no guarantee of alignment on data, but I wouldn't mind a confirmation.
If this could be confirmed, I could change the code comment in xxhash.h, which currently requires a specific alignment, just out of an abundance of precaution. But if it's not necessary, it's better to remove it, as it's a great flexibility for custom secrets.
A later more complex / convoluted question is if it would be beneficial to use the fact that the default secret kKey can be made aligned in order to improve performance when using it, or when the custom secret can be detected aligned. On x64 with SSE2 or AVX2, the answer is clearly "no", so there's no need to add complexity. I would expect a similar answer for arm64 or ppc64, but I'm less sure about arm32 for example, or mips32.
No need to look into this now, this is just a speed refinement, for a later stage.
Correct, vld1q and vec_vsx_ld are the things you need.
Sorry about the inactivity, I am really busy. Once I get this Calculus done I can write it for you if you need, but it shouldn't be too complicated. Just note that
vec_rl(vec, v32);
Is
vec = (vec << 32) | (vec >> 32);
Which I used because the keys would be in reverse order on big endian.
And
vec_revb
Is your average byte swap.
As for the x86, there is no harm in it being aligned, as Penryn and earlier strongly prefer movdqa over movdqu, but the check is only beneficial on these chips, the overhead of the branch and the removal of the alignment penalty on aligned reads makes it not worth it on newer chips.
ARM32 NEON only has a single cycle penalty; it isn't worth it. However, it will alignment fault if you use vld1q_u64 on GCC (it compiles to vld1.64 q0, [r0:128] which requires r0 to be 16-byte aligned).
VSX has no alignment penalty AFAIK.
Excellent, thanks for detailed answer @easyaspi314 !
And wish you the best for your end of year evaluations !
Btw @easyaspi314 ,
I added VSX code path verification on Travis CI,
which was previously testing only the "scalar" code path on PowerPC,
but unfortunately, compilation fails :
In file included from xxhash.c:1021:0:
xxh3.h: In function ‘XXH3_accumulate_512’:
xxh3.h:500:9: warning: implicit declaration of function ‘vec_revb’ [-Wimplicit-function-declaration]
U64x2 const data_vec = vec_revb(vec_vsx_ld(0, xdata + i));
^
xxh3.h:500:9: error: AltiVec argument passed to unprototyped function
It seems it doesn't know vec_revb() ?
This documentation seems to imply that vec_revb() availability is tied to compilation flag -mcpu=power9.
I tried it on Ubuntu Trusty, which is the environment used for PowerPC tests on TravisCI, but it doesn't work : this compiler is limited to power8 at best.
This path seems to imply that vec_revb() was later back-ported to power8, so it could work on this cpu too. Unfortunately, it is probably too late for the compiler version in Ubuntu Trusty : tried it on TravisCI, it still fails.
This makes me think that the automated detection of VSX has quite a number of conditions to check to make sure compilation will be successful.
_edit_ : and indeed, if I don't force the VSX mode and let the detection macro do the work, it happily triggers the VSX code path with -m64 -maltivec -mvsx, and then fails due to absence of vec_revb().
_edit 2_ : I will disable VSX tests on Travis CI for the time being. We still need PowerPC tests for big-endian compatibility.
Indeed. This was intended for POWER9, I don't know if it would work on POWER8.
I found that compiler support was rather lackkuster, especially on the GCC side. Only like GCC 7 or so supports it, and there don't seem to be a lot of macros to discern the versions. I will have to dig some more.
I know that Google used some inline assembly to work around the terrible compiler support and the inconsistent multiply intrisnics.
Granted, anyone who is using PowerPC64 nowadays is not likely to be the average user who doesn't know the difference between 32-bit and 64-bit or doesn't know what AVX2 is. But I still want to get things working properly.
With the release of streaming API for XXH3_64bits(), there's only a very limited number of actions remaining before moving on to XXH128().
1) Following @aras-p investigation, it seems preferable to extend the "short mode" to longer sizes, in order to reduce the performance cliff related to "long mode" initialization. This has direct consequences on streaming's state, so that's why it needed to be done in this order. Also, preserving hash quality is non-trivial, but I believe I've got a solution too, with earlier move to "secret first" helping this objective.
2) Wasm performance is still an issue, and it seems that "unrolling" is actually bad for this target. But in order to fix this, I must be able to observe it first. I made a little progress this morning, as emscripten compilation works again on my Mac. But compilation is just a first step : I still need to find a way to actually run a wasm test program and make measurements.
3) Lastly, I'm currently wondering about the introduction of a new property : it seems it could be possible to make XXH3 essentially bijective on len==8, and injective for any len < 8. It basically means that, for 2 inputs of same len <= 8, there would be a guarantee of no collision if both inputs are different (instead of the usual 1 / 2^64 probability). I'm wondering if this would be useful. The drawback is that, in order to keep 1st-class avalanche effect _on any subrange of bits_ of the output, I need to add one multiplication, making the hash a little bit slower (for len <= 8). Neither the property nor the impact seem large, so it's more a matter of preference : which one seems to matter more ?
I'll have to think it through more, but my main use case for xxhash is as a hash code for hash table lookups (where the big advantage of a high quality 64bit+ hash code is that you can get away with skipping key equality comparisons in far more scenarios than you could with something like an FNV variant), and I'm pretty sure in at least some use cases I could leverage an explicit guarantee of no collisions for keys <= 8 bytes for far more savings than the cost of a single multiply. So currently my vote would be to make it bijective at the cost of a multiply.
I am curious how this would work with a seed-independent zero hash for zero-length input, though (which I also think is something I could leverage for an optimization on lookups); can you simultaneously guarantee both no collisions len <= 8 and seed independent zero hash for zero length?
I still need to find a way to actually run a wasm test program and make measurements
Hmm for me running stuff on Wasm was super simple, basically just:
emcc just like gcc or clang, and it will produce a "command line" executable--preload-file paht/to/file to be able to do fopen/fread of test data files if you need them,python -m SimpleHTTPServer0.0.0.0:8000) and open your resulting html file.
My "compile wasm" build script is https://github.com/aras-p/HashFunctionsTest/blob/master/compile_emscripten.sh if you need an actual full example
can you simultaneously guarantee both no collisions len <= 8 and seed independent zero hash for zero length?
It depends on what you mean by "no collisions len <= 8".
Note that above-mentioned guarantee of no collision would be _for 2 inputs of ___same___ len <= 8_ . If that's what you meant, then yes, it's possible.
It is impossible to guarantee no collision for _any_ 2 inputs of len <= 8, just due to the pigeon hole principle. Or in more mathematical terms, 2 sets of different size cannot be bijective.
A possible property would be to guarantee no collision for any 2 inputs of len __<__ 8. In which case, the starting set is smaller than the destination one, so it's possible. Unfortunately, I have so far ruled out this property because it would be too easy to generate an intentional secret-independent collision between a input of len < 8, and one of len == 8.
However, if that's a desirable property, I could look again to find a better solution.
Thanks for guidance @aras-p , I'll sure try this setup as soon as possible.
Ah, yeah, of course! That makes sense. For my purposes, no same len collisions <=8 is definitely better than no collisions len <8.
Thanks to @aras-p 's hints, I started benchmarks in WebAssembly mode this morning.
I've only used one platform, a recent Mac laptop, featuring a recent Intel Core, and Chrome 74.
Using the "wide range" test, it mostly confirms what we already knew : XXH3 on wasm is a bit faster than XXH32, but slower than XXH64. This is consistent with a non-vectorized scalar code path run on 64-bit cpu.
I'm afraid I don't see a simple and immediate solution. The longer-term hope is that vectorial instructions will start working in a future emcc version, leading to auto-vectorization of the scalar code path, which currently works very well with clang.
If that's too far away, or too unsure, another route could be to generate a new code path, using gcc/clang vectorial intrinsics, which are apparently supported by emcc.
The wide range test doesn't allow me to observe the cliff at 128 bytes and 1 KB, because the distance between 2 consecutive measurement is too large (it's a power of 2).
I will use the more accurate length-byte test to specifically target these areas, and make sure next changes improve wasm performance.
With last changes to dev branch, I believe XXH3_64bits is now "feature complete".
It incorporates all points mentioned above.
I don't plan any more modification, but obviously, the design is still opened to comments and improvements.
Now, all that remains to be done is ... to apply the same mechanisms to the 128-bit variant...
Yawn… I'm back.
School is finally over, and I have a lot of free time for the next few days.
I have to replace my G3 very soon because the screen is dying. It is still functional, but I don't know for how long. God, I suck at decisions. I also plan to replace the Dell tower later this summer.
@Cyan4973 So, what did I miss?
I was looking at the recent changes, and it looks like the ARM and VSX paths need to be updated.
Could you please give me a quick recap about the recent changes to the algorithm? That would make things a little easier.
By the way, speaking of decisions, have you decided on how/if we are going to do the dispatcher?
XXH3_64bits() is stabilized, including its streaming implementation.
XXH3_128bits() is not, and that's my next priority. The current proposal in XXH128() does meet a few requirements, but constraints on performance seem too high, so I'll likely have to update it.
Hence, speaking of updates, prefer concentrating on XXH3_64bits(). I don't remember if NEON and VSX paths are correctly tested / validated.
The dispatcher has a place. I see it more as part of xxhsum than the library itself, but I can be mistaken in describing this separation.
You also proposed an interesting patch reducing instruction size, which looks good. It's been preserved in a feature branch, reroll. But the changes within dev are so large that it's more complex to merge now.
The dispatcher has a place. I see it more as part of xxhsum than the library itself
Well, as I mentioned before, Google Play Store guidelines require a feature test for ARMv7 NEON support, and as for the AVX2/SSE2 paths, if anyone wants to use the AVX2 path, it is impractical if you ever plan to distribute without a dispatcher. People are idiots and wouldn't know which binary to use. 🤷♂
Considering how key reading has changed, it seems that PPC big endian needs an update. I'll do some testing either tomorrow or Friday.
As for the reroll branch, I suggest merge the XXH32/XXH64 changes for now and I'll try to work on XXH3 when I get a chance. Besides, it had a branching issue IIRC.
reroll patch merged
Google Play Store guidelines require a feature test for ARMv7 NEON support
Depends, I wouldn't say that NEON vs non-NEON dispatcher is "absolutely required". E.g. at Unity we've been requiring NEON support for Android builds since ~2016, so for us the dispatcher there is not necessary.
and as for the AVX2/SSE2 paths, if anyone wants to use the AVX2 path, it is
impractical if you ever plan to distribute without a dispatcher
Same here, if someone is using xxHash for some in-house tooling or an application specifically targeted at high-end PC users (e.g. visualization/modeling/scientific etc.), their software might already require AVX2 or similar, in which case the dispatcher is not necessary.
Of course there are classes of users that would need or prefer to have a runtime dispatcher. But it should be optional IMHO.
XXH3_128bits()is not, and that's my next priority
I guess it's still expected the the hash values of 128 bit will change before the "final" release? e.g. today it still has some discrepancies compared to 64 bit one (e.g. hash of zero-sized buffer is full zeroes, unlike for 64 bit)
Yes, it will be updated, and follow the new model
Adapted the implementation to Rust, and made it pretty fast. (this is with Clang 8 and the XXH_VECTOR=0 path, because it isn't fair to compare intrinsics to autovec)
https://gist.github.com/easyaspi314/b01f0f68d2e2aaaacb4f1a345a552dd6
./xxhsum 0.7.0 (64-bits x86_64 + SSE2 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 47738 it/s ( 4661.9 MB/s)
XXH32 unaligned : 102400 -> 40817 it/s ( 3986.0 MB/s)
XXH64 : 102400 -> 65199 it/s ( 6367.1 MB/s)
XXH64 unaligned : 102400 -> 62238 it/s ( 6077.9 MB/s)
XXH3_64bits : 102400 -> 111937 it/s (10931.4 MB/s)
XXH3_64b unaligned : 102400 -> 105455 it/s (10298.3 MB/s)
XXH3_64b_RS : 102400 -> 94732 it/s ( 9251.2 MB/s)
XXH3_64b_RS unalign : 102400 -> 90630 it/s ( 8850.6 MB/s)
XXH128 : 102400 -> 104704 it/s (10225.0 MB/s)
XXH128 unaligned : 102400 -> 89104 it/s ( 8701.6 MB/s)
My new phone came!
Google Pixel 2 XL
2.46 GHz Qualcomm Snapdragon 835 (aarch64)
Clang 8.0.0
Termux
./xxhsum 0.7.0 (64-bits aarch64 little endian), Clang 8.0.0 (tags/RELEASE_800/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 31663 it/s ( 3092.0 MB/s)
XXH32 unaligned : 102400 -> 27540 it/s ( 2689.4 MB/s)
XXH64 : 102400 -> 31554 it/s ( 3081.5 MB/s)
XXH64 unaligned : 102400 -> 31567 it/s ( 3082.7 MB/s)
XXH3_64bits : 102400 -> 61226 it/s ( 5979.1 MB/s)
XXH3_64b unaligned : 102400 -> 57185 it/s ( 5584.5 MB/s)
XXH128 : 102400 -> 61255 it/s ( 5982.0 MB/s)
XXH128 unaligned : 102400 -> 56957 it/s ( 5562.2 MB/s)
Was brainstorming some ideas for size optimizations. Right now, even with XXH_REROLL, xxHash is still a rather hefty .o file.
I feel we should have something like XXH_TINY which enables aggressive size optimizations (at the cost of performance).
static and let the compiler decide.static XXH64_hash_t XXH3_64_hashInternal(const void *data, size_t len, const void *secret, size_t secretSize)
{
XXH64_hash_t ret;
if (len == 0) return 0;
if (len <= 16) ret = ...
else if (len <= 128) ret = ...
return XXH3_avalanche(ret);
}
XXH_PUBLIC_API XXH64_hash_t XXH3_64bits(const void *data, size_t len)
{
return XXH3_64_hashInternal(data, len, kSecret, size of(kSecret));
}
XXH_PUBLIC_API XXH64_hash_t XXH3_64bits_withSeed(const void *data, size_t len, XXH64_hash_t seed)
{
char secret[XXH_DEFAULT_SECRET_SIZE];
XXH3_initKeySeed(secret, seed);
return XXH3_64_hashInternal(data, len, secret, sizeof(secret));
}
...
This also reduces the chance of code duplication memes.
As you can see, I moved the avalanche to the end and the zero return early. Not sure whether it makes a diff.
There is probably a sweetspot
XXH_FORCE_INLINE void XXH32_hashLong(U32 v[4], const void *data, size_t len)
{
do {
XXH32_round(...);
XXH32_round(...);
XXH32_round(...);
XXH32_round(...);
} while (...);
}
uint64_t x = 0x123456789ABCDEF0;
aarch64 code might be:
mov x0, #0xDEF0
movk x0, #0x9ABC, lsl #16
movk x0, #0x5678, lsl #32
movk x0, #0x1234, lsl #48
Additionally, I think we need to work more on cleanliness for next release. Some things to clean up:
BYTE * earlier. This makes things easier to port to other languages which don't play well with void pointers.My 2cents about size optimization: I don't think it is really needed. At least not for the 64 or 128 bit hashes. What is the target CPU of these? Likely 64 bit systems aren't to memory constraint to need a sized optimized hash.
Even most Cortex-M systems have plenty of Flash.
Additionally, I think we need to work more on cleanliness for next release.
Agreed
Cast to BYTE * earlier.
I disagree.
void* is the only "universal" type which makes it possible to feed _anything_ to the function.
Even char* or BYTE* must be casted into whenever input memory area carries another type.
This makes things easier to port to other languages which don't play well with void pointers.
I don't understand that part.
"other languages" access the reference library through binders, which are restrained to invoke the *.h interface only, so they don't care about the internals of the library, which remains C compiled.
I think we should put the original primes in hex.
Agreed
Enforce a coding style. East coast, west const
Sure, though I don't have a feeling that there is _no_ coding style.
There is one, even if it's not specified. And it can certainly be updated / improved.
we can probably mix declarations for the 64-bit functions
I disagree.
I get the idea : long long is not strict ansi c89 anyway, so this part of the code could be written in c99 instead. However, that's not a good enough reason to start having 2 different coding styles depending on the section of the source file.
Besides, long long is only "official" since c99, but effectively, a _lot_ of compilers have been c89+, meaning c89 plus a subset of c99 (and their own extensions), among which long long was very well supported, while mix declaration was not. Visual Studio is an excellent example. So these 2 worlds don't overlap.
Now, if we were writing a _new_ library, starting with requiring c99 support could be a reasonable discussion. But xxhash is an existing library which is already widely deployed, hence it's not a good idea to introduce a potential build break for the benefit of reduced nesting.
Finally, this is more subtle, but there is actually some benefit at scoping variables to their most limited nest level : it's not just about opening, it's also about closing. Ending a variable scope is a good way to keep the rest of the code clean, making it easier and safer to evolve / refactor. This is an under-appreciated property.
In #231, there is a near-final proposal for XXH128().
It's not "completely finished" because NEON and VSX accumulator code paths need to be updated (cc @easyaspi314).
This proposal supports the same level of functionality as XXH3_64bits(), aka it can accept a custom secret of size >= minimal size, and a streaming interface is available, following the same API, and using the same state.
In term of design, we are back to original design of v0.7.0, where 8 lanes of 64 bits are combined at the end to produce a 128 bits hash. In order for each input to impact 128-bit of accumulator, the final operation is performed on the nearby lane, instead of its own lane, as in 64-bit case. This only adds one shuffle operation in the critical loop, but costs nonetheless ~15% performance.
I tried other variants, but they came with outsized impact on performance or flexibility.
There are still parts of this design which can be discussed.
For example, the hash tries to be bijective at 128-bits input. This comes at a speed cost for inputs <= 16 bytes, though not a big one. I presumed that this would be a nice property, although I have no strong use case to declare this property a "must".
The 128-bit hash sometimes manages to produce the same value in its low64 field as the 64-bit one when implementation-convenient, but not always. A big question is, is that an important property ? If it is, maybe it should be generalized ? In which case, several more changes should be done, notably on the 64-bit side, in order to ensure they produce the same value. This will come at a (moderate but non null) speed cost. But here too, I'm not sure if this is an "important" enough property, since I have no use case which would depend on it.
I think we should put the original primes in hex.
Done
I don't see anything else to add,
so I guess it's probably time for a new release ...
Has VSX been updated?
Also, we should do this for Clang.
#ifndef __has_builtin
# define __has_builtin(x) 0
#endif
#if __has_builtin(__builtin_rotateleft32) && __has_builtin(__builtin_rotateleft64)
# define XXH_rotl32 __builtin_rotateleft32
# define XXH_rotl64 __builtin_rotateleft64
#else ...
I just found yet another weird Clang bug, which affects literally every Clang version. Long story short, LLVM's instcombine is very likely to convert a multiply -> rotate into two multiplies and a shift->insert.
So for code like this:
U32 mulrot(U32 a) {
a *= 0x90000007; // imul eax, edi, 0x90000007
a = (a << 4) | (a >> 28); // rol eax, 4
return a;
}
it emits this:
U32 mulrot(U32 a) {
U32 left = a * 0x90000007; // imul eax, edi
U32 right = a * (0x90000007 << 4); // imul ecx, edi, 0x70
left >>= 28; // shr eax, 28
left |= right; // or eax, ecx
return left; // ret
}
It seems to negatively affect XXH32 and XXH64's round functions, and was likely the reason why the finalization stage was so ginormous.
These are good points @easyaspi314, they can be added for next release.
Sorry about the silence, I had something come up.
I think you are right, we should be targeting POWER8 instead of POWER9, as POWER9 is only 2 years old. Additionally, instead of __VSX__, we should check for _ARCH_PWR8 and/or __POWER8_VECTOR__. It completely slipped over my head because apparently QEMU doesn't pick up on illegal instructions, and the POWER9 server is really finicky (Why is CentOS 7.6 shipping glibc 2.17?). I might try one of the POWER8 servers.
Anyways.
vec_xxpermdi is the correct name for GCC, but xl calls it vec_permi. Confusing.
I think we need a normal vperm for the byteswap, but I can't get it to not emit garbage preswaps.
However, what is really frustrating is that Clang in ppc64eb is really happy to turn XXH3 into this:

Hopefully I can have this POWER8 compatible and make big endian code a bit nicer.
I'll try to get everything finalized this weekend.
OOOOOOH I just discovered vpermxor
Purpose
Applies a permute and exclusive-OR operation on two byte vectors.
Prototype
__vector unsigned char __vpermxor(__vector unsigned char a, __vector unsigned char b, __vector unsigned char mask);Result
For each i (0 <= i < 16), let indexA be bits 0 - 3 and indexB be bits 4 - 7 of byte element i of mask.
Byte element i of the result is set to the exclusive-OR of byte elements indexA of a and indexB of b.
(note that xlC uses __vpermxor, gcc uses vec_permxor)
So instead of doing this:
load data_vec
swap data_vec
load key_vec
swap key_vec
xor key_vec, data_vec
we can do
load data_vec
swap data_vec
load key_vec
vpermxor data_vec, key_vec, { 0x07, 0x16, 0x25, 0x34, ... }
I just pushed. I was really disappointed because I realized that the only big endian POWER8 machine was running 32-bit... :(
However, little endian is working on POWER8, and big endian works in qemu-ppc64-static 2.12.0 with -mcpu=power8.
cpu : POWER8E (raw), altivec supported
./xxhsum-clang 0.7.1 (64-bits ppc64 + POWER8 vector little endian), Clang 7.0.0 (tags/RELEASE_700/final), by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 49152 it/s ( 4800.0 MB/s)
XXH32 unaligned : 102400 -> 43463 it/s ( 4244.4 MB/s)
XXH64 : 102400 -> 98446 it/s ( 9613.8 MB/s)
XXH64 unaligned : 102400 -> 93068 it/s ( 9088.7 MB/s)
XXH3_64bits : 102400 -> 101830 it/s ( 9944.3 MB/s)
XXH3_64b unaligned : 102400 -> 83841 it/s ( 8187.5 MB/s)
XXH128 : 102400 -> 90658 it/s ( 8853.3 MB/s)
XXH128 unaligned : 102400 -> 82686 it/s ( 8074.8 MB/s)
I think I found the right manual 128-bit multiply which obsoletes the ugly ARM assembly version and avoids confusing carry tracking.
Ready:
U64 Multiply128(U64 a, U64 b, U64 *high)
{
U64 lo_lo = (a & 0xFFFFFFFF) * (b & 0xFFFFFFFF);
U64 hi_lo = (a >> 32) * (b & 0xFFFFFFFF);
U64 lo_hi = (a & 0xFFFFFFFF) * (b >> 32);
U64 hi_hi = (a >> 32) * (b >> 32);
/* Add two half products to a full product. This caps each
* operation at ULLONG_MAX, and encourages ARM compilers to
* emit the powerful UMAAL instruction which was specifically
* designed for this purpose.
* TODO: Better names. */
U64 cross = (lo_lo >> 32)
+ (hi_lo & 0xFFFFFFFF)
+ lo_hi;
U64 top = (hi_lo >> 32)
+ (cross >> 32)
+ hi_hi;
*high = top;
return (cross << 32) | (lo_lo & 0xFFFFFFFF);
}
clang -O3 -S --target=arm-none-eabi -march=ARMv7-a -fomit-frame-pointer -fno-unwind-tables -fno-asynchronous-unwind-tables
Multiply128:
push {r4, r5, r11, lr}
umull r12, r5, r2, r0
umull lr, r4, r3, r0
ldr r0, [sp, #16]
umaal lr, r5, r2, r1
umaal r4, r5, r3, r1
mov r1, lr
strd r4, r5, [r0]
mov r0, r12
pop {r4, r5, r11, pc}
This change saves 2 cycles and 4-8 bytes a pop because there are no more mov instructions.
As for the algorithm, it is literally just grade school cross multiplication. No complex carries, as they all cap at ULLONG_MAX.
57
----
21
140
150
1000
----
1311
lo_lo = 3 * 7 = 21
hi_lo = 2 * 7 = 14
lo_hi = (3 * 5 = 15)
+ (floor(lo_lo / 10) = 2)
+ (hi_lo % 10 = 4)
= 21
high = (2 * 5 = 10)
+ (floor(hi_lo / 10) = 1)
+ (floor(lo_hi / 10) = 2)
= 13
low = ((lo_lo % 10) = 1)
+ (((lo_hi * 10) % 100) = 10)
= 11
result = low + (high * 100) = 1311
I have not tested the codegen on other compilers, but Clang clearly sees it, and it is arguably more understandable (once we format it right) than the current mess.
This avoids all carry flag messes on ARM
Additionally, it seems that for a better long multiply on MSVC x86, you can do (U64)(U32)(x). I need to investigate.
gcc-9 -O3 -S -m32 -mno-sse2
Multiply128:
push ebp
push edi
push esi
push ebx
xor ebx, ebx
sub esp, 12
mov esi, dword ptr[esp + 40]
mov ebp, dword ptr[esp + 44]
mov eax, esi
mul dword ptr[esp + 32]
mov dword ptr[esp], eax
mov eax, esi
mov dword ptr[esp + 4], edx
mul dword ptr[esp + 36]
mov edi, edx
mov edx, dword ptr[esp + 4]
mov esi, eax
mov ecx, esi
mov esi, edi
mov eax, edx
xor edx, edx
add ecx, eax
mov eax, ebp
adc ebx, edx
mul dword ptr[32 + esp]
add ecx, eax
mov eax, ebp
adc ebx, edx
xor edi, edi
mul dword ptr[esp + 36]
add esi, eax
mov eax, dword ptr[esp + 48]
adc edi, edx
xor edx, edx
add esi, ebx
adc edi, edx
mov edx, ecx
mov dword ptr[eax], esi
mov dword ptr[eax + 4], edi
mov eax, dword ptr[esp]
add esp, 12
pop ebx
pop esi
pop edi
pop ebp
ret
GCC 9 i386's code gen isn't bad as long as it has SSE2 disabled (it still tries to autovectorize).
That looks great @easyaspi314 !
GCC 9 i386's code gen isn't bad as long as it has SSE2 disabled (it still tries to autovectorize).
Is it possible to disable it at function-level granularity ?
I have a new ARM chip to test, and I found the results interesting :
System details : Qualcomm aarch64 SM8150, termux Linux 4.14.78-16154136, clang v8.0.1, -O3.
| | speed |
| --- | --- |
| XXH32 | 5.2 GB/s |
| XXH64 | _3.6 GB/s_ |
| XXH3 | 12 GB/s |
| XXH128 | 10.5 GB/s |
Even though it's supposed to be a _modern_ aarch64 cpu, its speed is _worse_ for XXH64, presumably due to high usage of 64-bit multiplications.
The good news is that XXH3 works well, thanks to @easyaspi314 's NEON implementation.
Hmm. Is Clang maybe vectorizing XXH64?
Edit:
Is it possible to disable it at function-level granularity ?
Yes. We already do that.
Is Clang maybe vectorizing XXH64?
I thought that XXH32 was at risk of auto-vectorization, but XXH64 wasn't, at least not on x64 cpus. But the situation might be different on aarch64 ?
Anyway, I suppose it doesn't auto-vectorize : I benchmarked xxhsum with -O2, which I interpret as "will not auto-vectorize", and the resulting speed was the same. I even tried -O2 -fno-slp-vectorize -disable-loop-vectorization -disable-vectorization -fno-vectorize -fno-tree-vectorize just to be sure, same results.
I have a new ARM chip to test, and I found the results interesting :
System details : Qualcomm aarch64 SM8150,
termuxLinux 4.14.78-16154136,clangv8.0.1,-O3.
speed
XXH32 5.2 GB/s
XXH64 _3.6 GB/s_
XXH3 12 GB/s
XXH128 10.5 GB/sEven though it's supposed to be a _modern_
aarch64cpu, its speed is _worse_ forXXH64, presumably due to high usage of 64-bit multiplications.
I always use pure memcpy() if in doubt to get the raw memory performance. So maybe the DDRAM is slow.
AArch64 has special load instructions that might speed up things also:
"The load-store non-temporal pair instructions provide a hint to the memory system that an access is “non-temporal” or “streaming” and unlikely to be accessed again in the near future so need not be retained in data caches. However depending on the memory type they may permit memory reads to be preloaded and memory writes to be gathered, in order to accelerate bulk memory transfers. "
Okay, I believe there are enough updates to create a new release, v0.7.2.
I'm actually in need of a recent version for an internal project.
This is not the end of the story, XXH3 is still labelled experimental, and we can still bring improvements to it when needed or useful enough.
__ZrHa__
I've been studying @svpv's ZrHa kernel, a clever evolution of XXH128's kernel for long inputs,
which gets rid of the secret. And I do like it.
ZrHa core insight is the realization that
if the secret's main contribution is to maintain entropy (in presence of non-random input),
then the accumulator itself can endorse that role
assuming it remains random enough.
There are some subtle tricks to avoid the situation of "vanishing" accumulators,
which are pretty well explained by @svpv in this thread.
From a quality perspective, it seems to work fine :
it passes SMHasher's test, @svpv provided an avalanche diagram,
and a large-scale collision analysis was recently completed, and it scores great :
306 collisions for 100Bi hashes, right in the "ideal" distribution area.
Removing the secret has many little advantages, which I believe are worth considering :
The downsides are :
By far the biggest issue is the latency.
In tests, keeping the current 8-accumulators model (64-bytes),
SSE speed reaches 20 GB/s. That's not bad : it's faster than XXH64, though slower than current XXH3.
Perhaps more importantly, AVX speed is also 20 GB/s, proving that latency is the limiting factor.
By enlarging accumulators to 128-bytes, speed is unleashed :
SSE climbs to 30 GB/s, while AVX reaches 40 GB/s !
Now, that's in the right ballpark, performance becomes similar to current XXH3.
(It's actually slightly faster for SSE, and slightly slower for AVX).
We could do more, and go to 256-bytes accumulators.
This is by the way the accumulators' size of meowhash, and one of the reasons for its high speed.
And indeed, AVX jumps to 60 GB/s ! At this speed, it's faster than anything else,
even hashes using specialized hardware (AES, CRC32C, etc.) can't keep up.
However, SSE remains stuck at 30 GB/s.
Furthermore, performance is degraded for "small" inputs.
Indeed, more accumulators is not free : on top of larger RAM / registers budget,
is also makes the final merging stage longer,
the impacts of which is more sensible for smaller inputs.
On top of that, this kind of speed is in the "too much" territory, since it's already way faster than RAM,
and the variant which matters most is the SSE one,
which is also is more indicative of potential performance for other architectures.
So I believe that sticking to 128-bytes is a better trade-off.
Such a kernel change would represent a large refactoring of the code.
Even API will be impacted.
And as long as it's not "done", there is always a risk that something bad will show up, preventing the change from happening.
But I believe it can be worth it.
For discussion.
Those shuffles aren't going to be cheap on NEON, though. I posted details in the thread.
It seems that the _MM_SHUFFLE(0, 1, 2, 3) operation can be emulated with a combination of vext + vrev ?
Don't forget the multiply setup.
Now we're at 4 shuffles, and we can't take advantage of in-place vzip on v7 anymore without a temp. The shuffling is already an annoying bottleneck on the current algorithm, and we could end up at 4 GB/s (I'd have to test), the current speed of scalar. 🙁
Yeah this is looking pretty messy.
Needing a DCBA, AC, and a BD all at the same time is really painful for Neon.
My feedback regarding XXH3 on empty string (len==0, length==0, zero length, etc. for Ctrl+f):
Zero is a problematic value for some Bloom filter implementations, like this one, this one, and this one if it occurs more often than its "natural" frequency. Since the empty string can obviously occur with higher frequency than 1 / 2^64 (or 1 / 2^32, etc.), that is a problem for some applications.
Any other value, such as 1, would be fine for algorithms like this. For most applications, it should be OK that hash of empty is not dependent on seed--because what matters for Bloom hashing or table lookup is correlation. If all other inputs depend on the seed, there's no correlation problem.
I could, however, imagine wanting to encode entries from multiple "keyspaces" into one Bloom filter, using seed to select a "keyspace". In this case, the hash of empty string would need to depend on seed. But literally returning the seed is problematic, because naive choice of seeds, which should be perfectly fine, leads to naive correlation between empty string hashes in different keyspaces. For example, I might only need 256 different keyspaces and therefore use seeds 0-255.
Performance? I'm having trouble imagining a legitimate concern over the performance of seeded zero-length hashing. ;)
How about shipping multiple accumulator widths?
How about shipping multiple accumulator widths?
How does this look, @Cyan4973?
/* *********************************************
* XXH3 is a new hash algorithm, featuring improved performance for both
* small and large inputs.
* See full speed analysis here:
*
* http://fastcompression.blogspot.com/2019/03/presenting-xxh3.html
*
* This algorithm aims to make the most out of common hardware, instead of
* relying on non-standard or difficult to emulate extensions such as
* CRC32, AES-NI, or ugly shuffling.
*
* The algorithm itself is written in portable C90 (with long long) and runs
* great as-is, however, it is able to take advantage of common SIMD extensions
* if these are availble.
*
* These SIMD implementations are also designed to be as portable as possible,
* and the SSE2 and NEON implementations are (almost) guaranteed on all desktop
* and mobile targets. There are also AVX2 and POWER8 versions, however, these
* don't have the portability guarantee of the first two.
*
* Unlike most modern hashes, this hash function is designed for BOTH 32-bit
* and 64-bit targets. It can take full advantage of 64-bit bandwidth, however,
* almost all of the 64-bit arithmetic in the main loop is designed to be
* reasonably easy to expand on a 32-bit machine.
*
* In order to be reasonably fast, the base requirements are a CPU that can
* run XXH32 with the additional requirement of a 32-bit long multiply.
*
* There are no known CPUs which can run XXH32 without XXH3, but ARM CPUs
* need to either be running in ARM or Thumb-2 mode for UMULL family of
* instructions. There will be a compiler warning if this is compiled in
* Thumb-1 mode if ARM instructions are available.
*
* On 32-bit scalar targets, XXH3 will usually run at roughly the speed of
* XXH32, usually slightly faster. Considering that this is a true 64-bit
* and 128-bit hash function, it is significantly beneficial to use it
* over XXH32.
*
* 64-bit scalar targets usually see performance halfway between XXH32 and
* XXH64, however, most of these have guaranteed SIMD support.
*
* SIMD versions can run ridiculously fast, and you can expect speeds 2-3x
* faster than XXH32 or XXH64.
*
* XXH3 offers a 64-bit and a 128-bit version.
* If the extra strength is not required, it is recommended to use the
* 64-bit version due to the higher speed and easier return type
* manipulation.
*
* The XXH3 algorithm is still considered experimental.
*
* Produced results can -- and will -- change between versions.
* Results produced by v0.7.x will NOT be comparable with results from v0.7.y.
*
* It's nonetheless possible to use XXH3 for temporary uses like hash
* tables, however, avoid long-term storage until the algorithm is finalized.
*
* .......
*/
The content looks good @easyaspi314 !
In term of tone, I believe some of these sentences can be refactored to feel more "neutral" while effectively preserving their meaning. But since it's a matter of taste, I'll rather do the modifications directly, this is more efficient that bugging you at each minor difference.
It's fine lol, I'm used to being bugged. I have siblings. 😛
I'm going to work on commenting the XXH3 subroutines in the meantime.
Should we officially deprecate XXH32 once XXH3 is finalized?
Considering that XXH3 works on 32-bit, there isn't really any excuse to use XXH32 aside from maybe code size.
It's too soon for such decision,
and there is no hurry.
Was toying with LLVM's compiler runtime, and it turns out that their 128-bit multiply is much better on x86, but garbage on any RISC CPU.
This is their algorithm demangled:
uint128 __mulddi3(uint64_t a, uint64_t b) {
uint128 r;
result.low = (a & 0xffffffff) * (b & 0xffffffff);
uint64_t temp = result.low >> 32;
result.low &= 0xffffffff;
temp += (a >> 32) * (b & 0xffffffff);
result.low += (temp & 0xffffffff) << 32;
result.high = temp >> 32;
temp = result.low >> 32;
result.low &= 0xffffffff;
temp += (b >> 32) * (a & 0xffffffff);
result.low += (temp & 0xffffffff) << 32;
result.high += temp >> 32;
result.high += (a >> 32) * (b >> 32);
return result;
}
Looks more like x86 assembly than C tbh.
But I noticed that it decreased the number of temporaries.
I toyed with the algorithm, and made it use only one temporary, and it compiles to only 39 instructions on i686 with clang, and zero writes to the stack. Meanwhile, Clang still generates umaal on ARMv6.
Still working on readability and haven't tested GCC yet, but this is what I have been testing.
uint128 __mulddi3(uint64_t a, uint64_t b) {
uint128 result;
uint64_t cross = (a >> 32) * (b & 0xffffffff);
result.high = (a >> 32) * (b >> 32);
result.high += cross >> 32;
cross &= 0xffffffff;
cross += (a & 0xffffffff) * (b >> 32);
result.low = (a & 0xffffffff) * (b & 0xffffffff);
cross += (result.low >> 32);
result.high += (cross >> 32);
result.low &= 0xffffffff;
result.low += (cross << 32);
return result;
}
This is the generated ASM with Clang 9.0.1:
__mulddi3:
push ebp
push ebx
push edi
push esi
mov esi, dword ptr [esp + 36]
mov ecx, dword ptr [esp + 28]
mov eax, esi
mul dword ptr [esp + 24]
mov edi, edx
mov ebx, eax
mov eax, esi
mul ecx
mov esi, edx
mov ebp, eax
add ebp, edi
adc esi, 0
mov eax, dword ptr [esp + 32]
mul ecx
mov edi, edx
mov ecx, eax
add ecx, ebx
adc edi, 0
mov eax, dword ptr [esp + 32]
mul dword ptr [esp + 24]
add edx, ecx
adc edi, 0
add edi, ebp
mov ecx, dword ptr [esp + 20]
mov dword ptr [ecx], eax
mov dword ptr [ecx + 4], edx
mov dword ptr [ecx + 8], edi
adc esi, 0
mov dword ptr [ecx + 12], esi
mov eax, ecx
pop esi
pop edi
pop ebx
pop ebp
ret 4
This is the original algorithm we currently use
__mulddi3:
push ebp
push ebx
push edi
push esi
push eax
mov ecx, dword ptr [esp + 36]
mov ebx, dword ptr [esp + 40]
mov esi, dword ptr [esp + 28]
mov eax, ecx
mul esi
mov edi, edx
mov dword ptr [esp], eax # 4-byte Spill
mov eax, ecx
mul dword ptr [esp + 32]
mov ecx, edx
mov ebp, eax
mov eax, ebx
mul esi
mov ebx, edx
mov esi, eax
mov eax, dword ptr [esp + 40]
mul dword ptr [esp + 32]
add esi, edi
adc ebx, 0
add esi, ebp
adc ebx, 0
add eax, ecx
adc edx, 0
add eax, ebx
mov ecx, dword ptr [esp + 24]
mov edi, dword ptr [esp] # 4-byte Reload
mov dword ptr [ecx], edi
mov dword ptr [ecx + 4], esi
mov dword ptr [ecx + 8], eax
adc edx, 0
mov dword ptr [ecx + 12], edx
mov eax, ecx
add esp, 4
pop esi
pop edi
pop ebx
pop ebp
ret 4
```asm
__mulddi3:
push {r4, lr}
umull lr, r12, r2, r1
umull r2, r4, r2, r0
umaal r4, lr, r3, r0
umaal r12, lr, r3, r1
mov r0, r2
mov r1, r4
mov r2, r12
mov r3, lr
pop {r4, pc}
I did note that Clang makes some poor decisions as to which registers it is using on ARM in this version, causing it to push r5 and r11, but that doesn't matter too much when inlined.
Also, the original compiler-rt code exposes a codegen derp:
```asm
__mulddi3:
push {r4, r5, r6, r7, r11, lr}
umull lr, r4, r3, r1
umull r5, r6, r2, r1
umull r12, r1, r2, r0
adds r5, r1, r5
adcs r6, lr, r6
mov r1, r5
mov r2, r6
adc lr, r4, #0
umull r4, r7, r3, r0 // r4,r7 = (u64)r3 * r0
umlal r1, r2, r3, r0 // r1,r2 += (u64)r3 * r0 <<< but you literally just multiplied r3 and r0..
adds r0, r5, r4
adcs r0, r6, r7
adc r3, lr, #0 // you did all that just to check the carry...?
mov r0, r12 // and they don't even use r0
pop {r4, r5, r6, r7, r11, lr}
bx lr
I will spend the next _sprint_ at bringing a new release of xxHash together.
If there are suggestions that should make it into this release, I'm all ears.
I've already planned changes for corner cases with srcSize <= 8.
_edit_ : s/spring/sprint
I will spend the next spring
You mean spring of 2021?
You mean spring of 2021?
No, spring of 2430.
Ok, I finally redid unified NEON.
Currently working on some documentation/cleanup of the internals.
Toying with this for the short 128-bit hashes to highlight the parallels between the two halves.
I don't know if it helps readability or not.
{ xxh_u32 input_lo = XXH_readLE32(input);
xxh_u32 input_hi = XXH_readLE32(input + len - 4);
xxh_u64 acc_lo = input_lo | ((xxh_u64)input_hi << 32);
xxh_u64 acc_hi = XXH_swap64(acc_lo);
acc_lo ^= XXH_readLE64(secret) + seed;
acc_hi ^= XXH_readLE64(secret + 8) - seed;
acc_lo ^= acc_lo >> 51; acc_hi ^= acc_hi >> 47;
acc_lo *= PRIME32_1; acc_hi *= PRIME64_1;
acc_lo += len; acc_hi -= len;
acc_lo ^= acc_lo >> 47; acc_hi ^= acc_hi >> 43;
acc_lo *= PRIME64_2; acc_hi *= PRIME64_4;
{ XXH128_hash_t const h128 = { XXH3_avalanche(acc_lo) /*low64*/, XXH3_avalanche(acc_hi) /*high64*/ };
return h128;
} }
@Cyan4973 Is there any specific reason that s390x hasn't yet been merged into dev?
Do you mean this PR : https://github.com/Cyan4973/xxHash/pull/285 ?
It has already been merged.
Cyan4973 merged 11 commits into
Cyan4973:s390xfromeasyaspi314:s390x
Not into dev.
Indeed, you are right.
I can't remember why the patch was merged into its own feature branch ?
Maybe to run independent tests ?
Anyway, it was probably planned to be merged into dev just after, but this subtlety was lost, and it remained left alone. Trying to merge it now into dev now, it produces a non negligible amount of conflicts.
Onto it.
Was testing things on different compilers and testing minor tweaks.
xxhsum.exe 0.7.2 (32-bits i386 + SSE2 little endian), MSVC 19.24.28314.00, by Yann Collet
Sample of 100 KB...
XXH3_64b : 102400 -> 168817 it/s (16486.1 MB/s)
XXH3_64b unaligned : 102400 -> 168815 it/s (16485.8 MB/s)
XXH3_64b seeded : 102400 -> 159139 it/s (15540.9 MB/s)
XXH3_64b seeded unaligne : 102400 -> 159025 it/s (15529.8 MB/s)
XXH128 : 102400 -> 167321 it/s (16339.9 MB/s)
XXH128 unaligned : 102400 -> 167321 it/s (16339.9 MB/s)
XXH128 seeded : 102400 -> 158050 it/s (15434.6 MB/s)
XXH128 seeded unaligned : 102400 -> 158058 it/s (15435.4 MB/s)
xxhsum 0.7.2 (64-bits x86_64 + SSE2 little endian), MSVC 19.24.28314.00, by Yann Collet
Sample of 100 KB...
XXH3_64b : 102400 -> 243984 it/s (23826.5 MB/s)
XXH3_64b unaligned : 102400 -> 240665 it/s (23502.4 MB/s)
XXH3_64b seeded : 102400 -> 250037 it/s (24417.7 MB/s)
XXH3_64b seeded unaligne : 102400 -> 246639 it/s (24085.8 MB/s)
XXH128 : 102400 -> 239926 it/s (23430.3 MB/s)
XXH128 unaligned : 102400 -> 240151 it/s (23452.2 MB/s)
XXH128 seeded : 102400 -> 245940 it/s (24017.6 MB/s)
XXH128 seeded unaligned : 102400 -> 247279 it/s (24148.4 MB/s)
md5-a1dfc7993970981f5e7ee42f5fce16b8
xxhsum.exe 0.7.2 (32-bits i386 + SSE2 little endian), MSVC 19.24.28314.00, by Yann Collet
Sample of 100 KB...
XXH3_64b : 102400 -> 266229 it/s (25998.9 MB/s)
XXH3_64b unaligned : 102400 -> 266228 it/s (25998.8 MB/s)
XXH3_64b seeded : 102400 -> 258108 it/s (25205.9 MB/s)
XXH3_64b seeded unaligne : 102400 -> 257416 it/s (25138.3 MB/s)
XXH128 : 102400 -> 239253 it/s (23364.6 MB/s)
XXH128 unaligned : 102400 -> 239837 it/s (23421.6 MB/s)
XXH128 seeded : 102400 -> 233737 it/s (22825.9 MB/s)
XXH128 seeded unaligned : 102400 -> 233045 it/s (22758.3 MB/s)
md5-df66e11d081c5589647b10610cb57dd6
xxhsum 0.7.2 (64-bits x86_64 + SSE2 little endian), MSVC 19.24.28314.00, by Yann Collet
Sample of 100 KB...
XXH3_64b : 102400 -> 321710 it/s (31417.0 MB/s)
XXH3_64b unaligned : 102400 -> 320824 it/s (31330.5 MB/s)
XXH3_64b seeded : 102400 -> 314594 it/s (30722.0 MB/s)
XXH3_64b seeded unaligne : 102400 -> 314304 it/s (30693.8 MB/s)
XXH128 : 102400 -> 274966 it/s (26852.1 MB/s)
XXH128 unaligned : 102400 -> 275961 it/s (26949.4 MB/s)
XXH128 seeded : 102400 -> 279273 it/s (27272.8 MB/s)
XXH128 seeded unaligned : 102400 -> 277759 it/s (27124.9 MB/s)
md5-17c498cccfd9cb7e54caca37f1c1ee77
xxhsum.exe 0.7.2 (32-bits i386 little endian), GCC 9.2.0, by Yann Collet
Sample of 100 KB...
XXH3_64b : 102400 -> 94618 it/s ( 9240.0 MB/s)
XXH3_64b unaligned : 102400 -> 94337 it/s ( 9212.6 MB/s)
XXH3_64b seeded : 102400 -> 96110 it/s ( 9385.8 MB/s)
XXH3_64b seeded unaligne : 102400 -> 94710 it/s ( 9249.0 MB/s)
XXH128 : 102400 -> 76141 it/s ( 7435.7 MB/s)
XXH128 unaligned : 102400 -> 73731 it/s ( 7200.3 MB/s)
XXH128 seeded : 102400 -> 75995 it/s ( 7421.4 MB/s)
XXH128 seeded unaligned : 102400 -> 73064 it/s ( 7135.1 MB/s)
md5-df66e11d081c5589647b10610cb57dd6
xxhsum.exe 0.7.2 (32-bits i386 little endian), Clang 9.0.0 (https://github.com/msys2/MINGW-packages.git fdafa4d8c4022588676c8ec0985dafaf834258ae), by Yann Collet
Sample of 100 KB...
XXH3_64b : 102400 -> 57035 it/s ( 5569.8 MB/s)
XXH3_64b unaligned : 102400 -> 56740 it/s ( 5541.0 MB/s)
XXH3_64b seeded : 102400 -> 56848 it/s ( 5551.5 MB/s)
XXH3_64b seeded unaligne : 102400 -> 56687 it/s ( 5535.9 MB/s)
XXH128 : 102400 -> 47836 it/s ( 4671.5 MB/s)
XXH128 unaligned : 102400 -> 47582 it/s ( 4646.7 MB/s)
XXH128 seeded : 102400 -> 47834 it/s ( 4671.2 MB/s)
XXH128 seeded unaligned : 102400 -> 47129 it/s ( 4602.4 MB/s)
md5-1b8d8c11185a71390492293760a98da6
xxhsum.exe 0.7.2 (32-bits i386 little endian), Clang 9.0.0 (https://github.com/msys2/MINGW-packages.git fdafa4d8c4022588676c8ec0985dafaf834258ae), by Yann Collet
Sample of 100 KB...
XXH3_64b : 102400 -> 78483 it/s ( 7664.4 MB/s)
XXH3_64b unaligned : 102400 -> 78141 it/s ( 7631.0 MB/s)
XXH3_64b seeded : 102400 -> 77701 it/s ( 7588.0 MB/s)
XXH3_64b seeded unaligne : 102400 -> 76999 it/s ( 7519.4 MB/s)
XXH128 : 102400 -> 61315 it/s ( 5987.8 MB/s)
XXH128 unaligned : 102400 -> 61124 it/s ( 5969.2 MB/s)
XXH128 seeded : 102400 -> 60948 it/s ( 5951.9 MB/s)
XXH128 seeded unaligned : 102400 -> 60633 it/s ( 5921.2 MB/s)
md5-b7b2252ed9d26f98a84e3b8afcba0799
xxhsum.exe 0.7.2 (64-bits x86_64 + AVX2 little endian), GCC 9.2.0, by Yann Collet
Sample of 100 KB...
XXH3_64b : 102400 -> 357210 it/s (34883.8 MB/s)
XXH3_64b unaligned : 102400 -> 349488 it/s (34129.7 MB/s)
XXH3_64b seeded : 102400 -> 355145 it/s (34682.1 MB/s)
XXH3_64b seeded unaligne : 102400 -> 349091 it/s (34090.9 MB/s)
XXH128 : 102400 -> 400618 it/s (39122.8 MB/s)
XXH128 unaligned : 102400 -> 400281 it/s (39089.9 MB/s)
XXH128 seeded : 102400 -> 400000 it/s (39062.5 MB/s)
XXH128 seeded unaligned : 102400 -> 396731 it/s (38743.2 MB/s)
md5-c640b9589e56f455ff36a2368ff47d55
xxhsum.exe 0.7.2 (64-bits x86_64 + AVX2 little endian), GCC 9.2.0, by Yann Collet
Sample of 100 KB...
XXH3_64b : 102400 -> 538004 it/s (52539.4 MB/s)
XXH3_64b unaligned : 102400 -> 433722 it/s (42355.6 MB/s)
XXH3_64b seeded : 102400 -> 517874 it/s (50573.7 MB/s)
XXH3_64b seeded unaligne : 102400 -> 427260 it/s (41724.6 MB/s)
XXH128 : 102400 -> 575281 it/s (56179.8 MB/s)
XXH128 unaligned : 102400 -> 487777 it/s (47634.4 MB/s)
XXH128 seeded : 102400 -> 576360 it/s (56285.2 MB/s)
XXH128 seeded unaligned : 102400 -> 489298 it/s (47783.0 MB/s)
md5-b30298c5f3c3e42dd6f843170273b8d6
xxhsum.exe 0.7.2 (64-bits x86_64 + AVX2 little endian), GCC 9.2.0, by Yann Collet
Sample of 100 KB...
XXH3_64b : 102400 -> 613364 it/s (59898.8 MB/s)
XXH3_64b unaligned : 102400 -> 491900 it/s (48037.1 MB/s)
XXH3_64b seeded : 102400 -> 614400 it/s (60000.0 MB/s)
XXH3_64b seeded unaligne : 102400 -> 491520 it/s (48000.0 MB/s)
XXH128 : 102400 -> 575335 it/s (56185.1 MB/s)
XXH128 unaligned : 102400 -> 491520 it/s (48000.0 MB/s)
XXH128 seeded : 102400 -> 574206 it/s (56074.8 MB/s)
XXH128 seeded unaligned : 102400 -> 491520 it/s (48000.0 MB/s)
This seems to fix GCC's codegen for AVX2.
/*
* UGLY HACK:
* GCC usually generates the best code with -O3 for xxHash,
* except for AVX2 where it is overzealous in its unrolling
* resulting in code roughly 3/4 the speed of Clang.
*
* There are other issues, such as GCC splitting _mm256_loadu_si256
* into _mm_loadu_si128 + _mm256_inserti128_si256 which is an
* optimization which only applies to Sandy and Ivy Bridge... which
* don't even support AVX2.
*
* That is why when compiling the AVX2 version, it is recommended
* to use either
* -O2 -mavx2 -march=haswell
* or
* -O2 -mavx2 -mno-avx256-split-unaligned-load
* for decent performance, or just use Clang instead.
*
* Fortunately, we can control the first one with a pragma
* that forces GCC into -O2, but the other one we can't without
* "failed to inline always inline function due to target mismatch"
* warnings.
*/
#if XXH_VECTOR == XXH_AVX2 /* AVX2 */ \
&& defined(__GNUC__) && !defined(__clang__) /* GCC, not Clang */ \
&& defined(__OPTIMIZE__) && !defined(__OPTIMIZE_SIZE__) /* respect -O0 and -Os */
# pragma GCC push_options
# pragma GCC optimize("-O2")
#endif
/* body of xxh3.h */
/* Pop our optimization override from above */
#if XXH_VECTOR == XXH_AVX2 /* AVX2 */ \
&& defined(__GNUC__) && !defined(__clang__) /* GCC, not Clang */ \
&& defined(__OPTIMIZE__) && !defined(__OPTIMIZE_SIZE__) /* respect -O0 and -Os */
# pragma GCC pop_options
#endif
As for MSVC x86, in order to get something optimal, we would need to basically:
__allmul callsXXH_FORCE_INLINE xxh_u64
XXH_mult64to64(xxh_u64 a, xxh_u64 b)
{
xxh_u64 lo_lo = XXH_mult32to64(a & 0xffffffff, b & 0xffffffff);
xxh_u32 lo_hi = (xxh_u32)(a & 0xffffffff) * (xxh_u32)(b >> 32);
xxh_u32 hi_lo = (xxh_u32)(a >> 32) * (xxh_u32)(b & 0xffffffff);
lo_lo += (xxh_u64)hi_lo << 32;
lo_lo += (xxh_u64)lo_hi << 32;
return lo_lo;
}
At this point, it'd be better do this:
#if defined(_MSC_VER) && defined(_M_IX86) && ! defined (_M_IX64) && !defined(__clang__)
# error "Get a better compiler, skrub!"
#endif
:unamused:
Apparently, Clang i686 is vectorizing the short XXH128 hashes in SSE2, causing a significant drop in performance compared to GCC.
While this is measuring the smallInputs branch, XXH128 is unaffected.
Spreadsheet showing the Latency test for 1-16 byte hashes


However, it seems that even with SSE turned off, Clang is still generating significantly slower code.
I'm currently investigating it.
Was messing with really old versions of GCC from the 90s for fun.
As long as you nop the XXH_ALIGN macro, even GCC 2.95 will compile xxHash fine. :+1:
However, apparently, it doesn't recognize the a & 0xFFFFFFFF pattern well on 32-bit targets like ARM:
xxh_u64 XXH_mult32to64(xxh_u64 a, xxh_u64 b)
{
return (a & 0xffffffff) * (b & 0xffffffff);
}
@ Generated by gcc 2.9-arm-000512 for ARM/elf
XXH_mult32to64:
push {r4, r5, r6, r7, lr}
mov r5, #0
mov r4, #0xffffffff
mov r7, r5
mov r6, r4
@ mask by 0x00000000 and 0xffffffff ?!?!?!
and r6, r6, r0
and r7, r7, r1
and r4, r4, r2
and r5, r5, r3
@ 64x64->64 multiply
umull r0, r1, r6, r4
mla r1, r6, r5, r1
mla r1, r4, r7, r1
pop {r4, r5, r6, r7, pc}
md5-c51d992a0a26ed25b5857d3c31e75a74
```asm
@ Generated by gcc 2.9-arm-000512 for ARM/elf
XXH_mult32to64:
push {r4, lr}
umull r3, r4, r0, r2
mov r1, r4
mov r0, r3
pop {r4, pc}
I say we change XXH_mult32to64 to a downcast+upcast — seems like an optimization for old/stupid compilers which doesn't affect newer compilers.
I agree
As for simplifying XXH128's short inputs:
The obvious one is to reduce the multiplies as we did with XXH3_64.
With #308 now merged, XXH3_64 is pretty lean:
| | Mults (x64) | Mults (aarch64) | Mults (32-bit) |
|:--|--:|--:|--:|
| 1to3 | 2 | 2 | 6 |
| 4to8 | 2 | 2 | 4 |
| 9to16 | 2 | 3 | 7 |
XXH128 is not so much:
| | Mults (x64) | Mults (aarch64) | Mults (32-bit) | notes |
|:--|--:|--:|--:|--:|
| 1to3 | 4 | 4 | 12 | Clang generates garbage SSE2/NEON on i686/ARMv7 without -fno-slp-vectorize |
| 4to8 | 6 | 6 | 17 | same as above, movw/movt/movk hell on ARM |
| 9to16 | 7 | 9 | 21 | adc on 32-bit |
While I am perfectly fine with XXH128 being primarily 64-bit, there are still a lot of other optimizations:
-fno-slp-vectorizeSurprisingly enough, I find the current performance of xxh128 to be rather good, considering the extra work needed to generate well-dispersed 128-bits outputs.
Fixed-size input Latency measurements on x64, core i7-9700k, gcc 9.2, numbers are in Millions of Hashes per second (MH/s) :
| hash | 1-3 | 4-8 | 9-16 | 17-32 |
| --- | --- | --- | --- | --- |
| xxh3 | 143 | 138 | 135 | 125 |
| xxh128 | 137 | 114 | 115 | 114 |
_Edit_ : xxh128 down to 137 after the fix for perlin noise with 16-bit input, in line with expectation.
I presume the performance is fairly good because modern Intel x64 CPUs are pretty good at churning multiple instructions in parallel, and the pipeline is designed to let the upper and lower parts of the 128-bit hash be calculated in parallel. I presume the performance is probably less good on x86 32-bit, and even on ARM, since these arch are less wide.
Anyway, that gives us a baseline to improve upon.
I don't see any need to address performance for another segment of xxh128.
So I guess we are getting close to a release, and can address the few other issues left.
@easyaspi314 , you suggested at some point to alter the secret selection for small keys ? Is that still on the table ? Or was it tied to the bijectivity of xxh3 for 64-bit inputs (which has been dropped since) ?
I think it is still on the table.
I think we should try secret + secretSize - N, perhaps:
1to3: secret + secretSize - 48
4to8: secret + secretSize - 32
9to16: secret + secretSize - 16
Everything is within 64 bytes == (usually) one cache line, and on kSecret, 16-byte aligned.
Because otherwise, the last bytes of the secret only really get used in scrambleAcc.
Mind if I add this comment?
/* Improves scores on the questionable MomentChi2 test. */
seed ^= (xxh_u64)XXH_swap32((xxh_u32)seed) << 32;
Because that is basically the only reason it is there.
If we aren't going to patch #261, I think we should be transparent about it:
/*
* DISCLAIMER: There are known *seed-dependent* collisions here due to multiplication by zero,
* affecting hashes of lengths 17 to 240.
*
* Keep this in mind when using the unseeded XXH3_64bits() variant: As with all unseeded
* non-cryptographic hashes, it does not attempt to defend itself against specially crafted
* inputs, only random inputs.
*
* Compared to classic UMAC where a 1 in 2^31 chance of 4 consecutive bytes cancelling out
* the secret is taken an arbitrary number of times (addressed in XXH3_accumulate_512), this
* collision is very unlikely with random inputs and/or proper seeding:
*
* This only has a 1 in 2^63 chance of 8 consecutive bytes cancelling out, in a function
* that is only called up to 16 times per hash with up to 240 bytes of input.
*
* This is a minor issue for a non-cryptographic hash function, especially with only a
* 64-bit output.
*
* The 128-bit variant (which trades some speed for strength) is NOT affected by this,
* although it is always a good idea to use a proper seed if you care about strength.
*/
XXH_FORCE_INLINE xxh_u64 XXH3_mix16B(const xxh_u8* XXH_RESTRICT input,
const xxh_u8* XXH_RESTRICT secret, xxh_u64 seed64)
{
xxh_u64 const input_lo = XXH_readLE64(input);
xxh_u64 const input_hi = XXH_readLE64(input+8);
return XXH3_mul128_fold64(
input_lo ^ (XXH_readLE64(secret) + seed64),
input_hi ^ (XXH_readLE64(secret+8) - seed64) );
}
Added some internal documentation in #313.
{ xxh_u64 const input_lo = XXH_readLE64(input) ^ (XXH_readLE64(secret) + seed);
xxh_u64 const input_hi = XXH_readLE64(input + len - 8) ^ (XXH_readLE64(secret+8) - seed);
XXH128_hash_t m128 = XXH_mult64to128(input_lo ^ input_hi, PRIME64_1);
seed is mostly cancelled out here from the low bits, which was an issue with 9to16_64b
Mind if I add this comment?
/* Improves scores on the questionable MomentChi2 test. */
(...)
Because that is basically the only reason it is there.
Not completely.
The primary reason for this xor_shuffle is the new "Perlin Noise" test,
which in essence, generates a list of random numbers from (x,y) coordinates,
one provided via the input, the other via the seed.
It happens to also _help_ MomentChi2, but does not help enough to solve the seed part of this test.
What would be required is something like :
seed = XXH64_avalanche(seed);
which is considerably more expensive.
(That's where I mentioned that it would be "cheating" because this cost is reduced to "zero" in the seed-less variant).
Ultimately, I'm also modifying MomentChi2 in my fork, to make it more rational and extensible. Previously, the quality was checked by passing the same serie of linear numbers to the input and then the seed. It would only prove they both drift together. Now the input serie is compared to some "ideal" threshold to be reached, which is stable due to law of probabilities. As a consequence, the doNothing codec no longer pass the test, which seems like a more faithful outcome. And the seed serie is no longer necessary.
seed is mostly cancelled out here from the low bits, which was an issue with 9to16_64b
Yeah, that's a fair point.
Curiously enough, the "Perlin Noise" test should have been sensible to this cancellation, but it doesn't detect any weakness with this formula. I presume enough of the seed is present in the final mix, likely through re-ingestion of input_hi later.
Nevertheless, I don't see a good reason justifying the presence of seed twice, so this could be simplified.
I think we should try secret + secretSize - N (...)
Everything is within 64 bytes == (usually) one cache line, and on kSecret, 16-byte aligned.
Keep in mind that this topic only matters when trying to obfuscate discovery of a _custom_ secret, hence not kSecret which is public.
And the custom secret is not required to be aligned : the only requirement is that its size must be >= XXH3_SECRET_SIZE_MIN.
That being said, if the goal is to preserve performance when using default kSecret, then it's likely better to align read accesses (although _maybe_ a good enough compiler can replace these static read accesses into kSecret by direct constants in the instructions flow).
Also, I don't remember the exact goal :
is that to make secret discovery more difficult when using small inputs (len <= 16),
because this knowledge could be abused to generate collisions with medium inputs (len >= 17+)
as a mitigation for #261 ?
Note that even the discovery stage is not trivial, as it requires to collect the result of hash calculation. External actor can typically manipulate input, but retrieving the full hash result, as opposed to observing its outcome on the system, is much less obvious.
Just an idea :
we could actually combine multiple secret ranges, with a simple + or a ^.
Advantage : retrieving the combined secret doesn't provide enough information about its constituents. So they remain well protected.
Disadvantage, if the combination is done at run time, it's a performance loss.
However, if the combination is done at compile time, then there is no cost.
Ultimately, combination at compile time might be possible with kSecret, but it cannot be done with a custom secret. Hence, runtime combination is required with a custom secret, which might be slower (sidenote : seed is not affected, it still uses kSecret).
Thoughts ?
Complementary :
made some quick tests on Linux + gcc, and indeed,
as long as kSecret is used,
the combination of fields costs nothing,
they are most likely combined at compile time and directly inserted in the instructions flow.
_edit_ :
completed evaluation with some custom secret :
and if my benchmark is correct,
the cost of combining 2 secrets segments seems practically negligible.
It seems performance is not something to worry about in this proposal.
Also, I don't remember the exact goal :
is that to make secret discovery more difficult when using small inputs (len <= 16),
because this knowledge could be abused to generate collisions with medium inputs (len >= 17+)
as a mitigation for #261 ?Note that even the discovery stage is not trivial, as it requires to collect the result of hash calculation. External actor can typically manipulate input, but retrieving the full hash result, as opposed to observing its outcome on the system, is much less obvious.
It was originally that, but it was also to make the secret used more uniformly.
The first 4-16 bytes are critical in every length, as well as in accumulate_512, while the last bytes only make a difference on longer hashes, and even still, they are only used for scrambleAcc and finalization (unless I am completely missing something).
we could actually combine multiple
secretranges, with a simple+or a^.
Good idea.
There is not a lot that can be done with seed because there isn't enough input to properly hide it, but custom secrets will be literally impossible to determine from the short hashes, adding another layer of protection.
it was also to make the secret used more uniformly.
A bit more uniformly, sure, seems like a good idea.
We don't have to ensure perfect uniformity though.
It's not a big issue if the last bytes of the secret are _less_ used than the first ones
(it would be an issue if they were not used at all !).
the last bytes only make a difference on longer hashes
Actually, last bytes are used in :
Bitflipper for last segment of Midsize inputs
Didn't notice that one, thanks for pointing that out.
Also, I think we should review the original questions.
Here are my thoughts.
/* - 128-bits output type : currently defined as a structure of two 64-bits fields.
* That's because 128-bit values do not exist in C standard.
* Note that it means that, at byte level, result is not identical depending on endianess.
* However, at field level, they are identical on all platforms.
* The canonical representation solves the issue of identical byte-level representation across platforms,
* which is necessary for serialization.
* Q1 : Would there be a better representation for a 128-bit hash result ?
* Q2 : Are the names of the inner 64-bit fields important ? Should they be changed ?
*/
I think the current layout is fine. Besides, you should never store binary data in an endian-dependent matter.
The only different way I would see is a raw byte array, but that is a little difficult to handle.
/*
* - Prototype XXH128() : XXH128() uses the same arguments as XXH64(), for consistency.
* It means it maps to XXH3_128bits_withSeed().
* This variant is slightly slower than XXH3_128bits(),
* because the seed is now part of the algorithm, and can't be simplified.
* Is that a good idea ?
*/
Fine as-is.
/*
* - Seed type for XXH128() : currently, it's a single 64-bit value, like the 64-bit variant.
* It could be argued that it's more logical to offer a 128-bit seed input parameter for a 128-bit hash.
* But 128-bit seed is more difficult to use, since it requires to pass a structure instead of a scalar value.
* Such a variant could either replace current one, or become an additional one.
* Farmhash, for example, offers both variants (the 128-bits seed variant is called `doubleSeed`).
* Follow up question : if both 64-bit and 128-bit seeds are allowed, which variant should be called XXH128 ?
*/
64-bit seed is fine as-is, I think. If we really want, we could adapt it to replace the +seed/-seed, but if people really needed a 128-bit seed, they would just use a custom secret.
/*
* - Result for len==0 : Currently, the result of hashing a zero-length input is always `0`.
* It seems okay as a return value when using "default" secret and seed.
* But is it still fine to return `0` when secret or seed are non-default ?
* Are there use cases which could depend on generating a different hash result for zero-length input when the secret is different ?
*/
Handled already.
/*
* - Consistency (1) : Streaming XXH128 uses an XXH3 state, which is the same state as XXH3_64bits().
* It means a 128bit streaming loop must invoke the following symbols :
* XXH3_createState(), XXH3_128bits_reset(), XXH3_128bits_update() (loop), XXH3_128bits_digest(), XXH3_freeState().
* Is that consistent enough ?
*/
I mean I think it is fine as-is. We may want to add some checking to ensure the 128-bit update is not called with a 64-bit update (store hash type in reserved fields?).
/*
* - Consistency (2) : The canonical representation of `XXH3_64bits` is provided by existing functions
* XXH64_canonicalFromHash(), and reverse operation XXH64_hashFromCanonical().
* As a mirror, canonical functions for XXH128_hash_t results generated by `XXH3_128bits`
* are XXH128_canonicalFromHash() and XXH128_hashFromCanonical().
* Which means, `XXH3` doesn't appear in the names, because canonical functions operate on a type,
* independently of which algorithm was used to generate that type.
* Is that consistent enough ?
*/
Consistent enough I think.
Thanks for feedback,
I guess this is clearly most of the topic.
Since I am planning on going through the comments and checking spelling and grammar, it would be a nice time to set a proper style and margin.
/* Foo
* Bar
* Baz */
/*
* Foo
* Bar
* Baz
*/
I always do the second style without thinking but if you want the first one, I can use that instead.
If I have an exact number, I can put a marker there and avoid guessing. I usually aim for about 75-80 (as that is what I am used to and is the default size on my terminal), but I'm presuming from your general style that you like widescreen and might want 100 or 120. There is a test for lines longer than 120 chars although I question its usefulness.
Which comment style do you prefer?
The second one is fine
How long should the lines be?
I never settled on this one.
Long lines don't annoy me much, due to omnipresence of wide screens, if not ultra-wide ones.
I consider vertical density to be more important, as vertical space is more limited than horizontal one.
That being said, I regularly get comments on this topic, so I guess it's better to keep lines "reasonably" long.
The most hardcore proponents on this topic target 80 columns. As if we were still using PC/AT.
But it's more that a few voices : many tools do target this width, or make 80 their default.
So there is a combination of pushes towards this number.
My own take : try to lean towards 80 columns, but don't overdo it.
If a sentence needs a few more characters to be completed on one line, then it's better than splitting it into 2.
A "hard" limit at 120 characters seems preferable for the code.
I've not yet settled about a limit for comments.
As if we were still using PC/AT.
Hmm, I should find one and run ./xxhsum -b on it :joy:
New XXH3 comment draft which is more neutral than my last version, while also providing more info.
/* ************************************************************************
* XXH3 is a new hash algorithm featuring:
* - Improved speed for both small and large inputs
* - True 64-bit and 128-bit outputs
* - SIMD acceleration
* - Improved 32-bit viability
*
* Speed analysis methodology is explained here:
*
* http://fastcompression.blogspot.com/2019/03/presenting-xxh3.html
*
* In general, expect XXH3 to run about ~2x faster on large inputs,
* and >3x faster on small ones, though exact differences depend on the platform.
*
* The algorithm is portable: Like XXH32 and XXH64, it generates the same hash
* on all platforms.
*
* It benefits greatly from SIMD and 64-bit arithmetic, but does not require it.
*
* Almost all 32-bit and 64-bit targets that can run XXH32 smoothly can run
* XXH3 at usable speeds, even if XXH64 runs slowly. Further details are
* explained in the implementation.
*
* Optimized implementations are provided for AVX2, SSE2, NEON, POWER8, ZVector,
* and scalar targets. This can be controlled with the XXH_VECTOR macro.
*
* XXH3 offers 2 variants, _64bits and _128bits.
* When only 64 bits are needed, prefer calling the _64bits variant, as it
* reduces the amount of mixing, resulting in faster speed on small inputs.
*
* It's also generally simpler to manipulate a scalar return type than a struct.
*
* The 128-bit version adds additional strength at the cost of some speed.
*
* The XXH3 algorithm is still in development.
* The results it produces may still change in future versions.
* Results produced by v0.7.x are not comparable with results from v0.7.y.
* However, the API is completely stable, and it can safely be used for
* ephemeral data (local sessions).
*
* Avoid storing values in long-term storage until the algorithm is finalized.
*
* The API supports one-shot hashing, streaming mode, and custom secrets.
*/
Looks good to me !
http://fastcompression.blogspot.com/2019/03/presenting-xxh3.html
Suuuuper minor: change to https:// maybe; the page works there too, and browsers don't show the scary "page is not secure, boohoo" widgets.
Good point, thanks @aras-p !
The Great Typo Hunt has begun. #319
If anyone finds typos I missed, please let me know there.
Suuuuper minor: change to
https://maybe; the page works there too, and browsers don't show the scary "page is not secure, boohoo" widgets.
Hmm, even though it is merely a redirect, xxhash.com should ideally use HTTPS. Currently, the link is HTTP and it redirects to the HTTP version of github.io (even though it fully supports HTTPS)
That was surprisingly difficult to setup.
But it seems finally done now.
Why don't they make these things easy? :frowning:
You missed the link in the repo description, btw.
The current XXH3 and XXH128 formats are now officially "Release candidate".
After this last validation period, the current format will simply be made the "final" one.
On reaching this stage, we will be publish a v0.8.0 release.
After this point, the return values of these functions will always be comparable (no change in the future).
These are the main goals for v0.8.0:
Something I thought of when reading MeowHash:
Maybe we should change kSecret to the digits of Pi.
It is a nothing-up-our-sleeves number (instead of a "prng" output from someone else), is a pretty common choice for magic numbers like this, and, well, look at my username. :smile:
/*
* This is the default "secret" that is used to mix with the input, and it is also
* used to generate a secret for the seeded variants.
*
* Instead of using a set of numbers claimed to be the output of a pseudorandom
* number generator, it has been changed to a "nothing-up-our-sleeves" number.
*
* Choosing this number was easy, as Pi is a common "nothing-up-our-sleeves"
* number, and the second reason should be obvious. :)
*
*/
XXH_ALIGN(64) static const xxh_u8 kSecret[XXH_SECRET_DEFAULT_SIZE] = {
0x24, 0x3F, 0x6A, 0x88, 0x85, 0xA3, 0x08, 0xD3, 0x13, 0x19, 0x8A, 0x2E, 0x03, 0x70, 0x73, 0x44,
0xA4, 0x09, 0x38, 0x22, 0x29, 0x9F, 0x31, 0xD0, 0x08, 0x2E, 0xFA, 0x98, 0xEC, 0x4E, 0x6C, 0x89,
0x45, 0x28, 0x21, 0xE6, 0x38, 0xD0, 0x13, 0x77, 0xBE, 0x54, 0x66, 0xCF, 0x34, 0xE9, 0x0C, 0x6C,
0xC0, 0xAC, 0x29, 0xB7, 0xC9, 0x7C, 0x50, 0xDD, 0x3F, 0x84, 0xD5, 0xB5, 0xB5, 0x47, 0x09, 0x17,
0x92, 0x16, 0xD5, 0xD9, 0x89, 0x79, 0xFB, 0x1B, 0xD1, 0x31, 0x0B, 0xA6, 0x98, 0xDF, 0xB5, 0xAC,
0x2F, 0xFD, 0x72, 0xDB, 0xD0, 0x1A, 0xDF, 0xB7, 0xB8, 0xE1, 0xAF, 0xED, 0x6A, 0x26, 0x7E, 0x96,
0xBA, 0x7C, 0x90, 0x45, 0xF1, 0x2C, 0x7F, 0x99, 0x24, 0xA1, 0x99, 0x47, 0xB3, 0x91, 0x6C, 0xF7,
0x08, 0x01, 0xF2, 0xE2, 0x85, 0x8E, 0xFC, 0x16, 0x63, 0x69, 0x20, 0xD8, 0x71, 0x57, 0x4E, 0x69,
0xA4, 0x58, 0xFE, 0xA3, 0xF4, 0x93, 0x3D, 0x7E, 0x0D, 0x95, 0x74, 0x8F, 0x72, 0x8E, 0xB6, 0x58,
0x71, 0x8B, 0xCD, 0x58, 0x82, 0x15, 0x4A, 0xEE, 0x7B, 0x54, 0xA4, 0x1D, 0xC2, 0x5A, 0x59, 0xB5,
0x9C, 0x30, 0xD5, 0x39, 0x2A, 0xF2, 0x60, 0x13, 0xC5, 0xD1, 0xB0, 0x23, 0x28, 0x60, 0x85, 0xF0,
0xCA, 0x41, 0x79, 0x18, 0xB8, 0xDB, 0x38, 0xEF, 0x8E, 0x79, 0xDC, 0xB0, 0x60, 0x3A, 0x18, 0x0E
};
This is a nice idea,
however, it also changes return values, so v0.7.3 would no longer be "release candidate".
Triggering another release cycle just for swapping kSecret value seems too much,
however, if we have other reasons to modify the return values, this could easily be added on top.
Yeah, that was what I was thinking. Only if we decide to modify it otherwise.
Also, found some speed hax for ARM which improve short hashLongs.
XXH_FORCE_INLINE void XXH3_initCustomSecret(xxh_u8* XXH_RESTRICT customSecret, xxh_u64 seed64)
{
int const nbRounds = XXH_SECRET_DEFAULT_SIZE / 16;
int i;
/*
* We need a separate pointer for the hack below.
* Any decent compiler will optimize this out otherwise.
*/
const xxh_u8 *kSecretPtr = kSecret;
XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE & 15) == 0);
#if defined(__clang__) && defined(__aarch64__)
/*
* UGLY HACK:
* Clang generates a bunch of MOV/MOVK pairs for aarch64, and they are
* placed sequentially, in order, at the top of the unrolled loop.
*
* While MOVK is great for generating constants (2 cycles for a 64-bit
* constant compared to 4 cycles for LDR), long MOVK chains stall the
* integer pipelines:
* I L S
* MOVK
* MOVK
* MOVK
* MOVK
* ADD
* SUB STR
* STR
* By forcing loads from memory (as the asm line causes Clang to assume
* that kSecretPtr has been changed), the pipelines are used more efficiently:
* I L S
* LDR
* ADD LDR
* SUB STR
* STR
* XXH3_64bits_withSeed, len == 256, Snapdragon 835
* without hack: 2654.4 MB/s
* with hack: 3202.9 MB/s
*/
__asm__("" : "+r" (kSecretPtr));
#endif
/*
* Note: in debug mode, this overrides the asm optimization
* and Clang will emit MOVK chains again.
*/
XXH_ASSERT(kSecretPtr == kSecret);
for (i=0; i < nbRounds; i++) {
/*
* The asm hack causes Clang to assume that kSecretPtr aliases with
* customSecret, and on aarch64, this prevented LDP from merging two
* loads together for free. Putting the loads together before the stores
* properly generates LDP.
*/
xxh_u64 lo = XXH_readLE64(kSecretPtr + 16*i) + seed64;
xxh_u64 hi = XXH_readLE64(kSecretPtr + 16*i + 8) - seed64;
XXH_writeLE64(customSecret + 16*i, lo);
XXH_writeLE64(customSecret + 16*i + 8, hi);
}
}
static XXH64_hash_t
XXH3_mergeAccs(const xxh_u64* XXH_RESTRICT acc, const xxh_u8* XXH_RESTRICT secret, xxh_u64 start)
{
xxh_u64 result64 = start;
size_t i = 0;
for (i = 0; i < 4; i++) {
result64 += XXH3_mix2Accs(acc+2*i, secret + 16*i);
#if defined(__clang__) /* Clang */ \
&& (defined(__arm__) || defined(__thumb__)) /* ARMv7 */ \
&& (defined(__ARM_NEON) || defined(__ARM_NEON__)) /* NEON */ \
&& !defined(XXH_ENABLE_AUTOVECTORIZE) /* Define to disable */
/*
* UGLY HACK:
* Prevent autovectorization on Clang ARMv7-a. Exact same problem as
* the one in XXH3_len_129to240_64b. Speeds up shorter keys > 240b.
* XXH3_64bits, len == 256, Snapdragon 835:
* without hack: 2063.7 MB/s
* with hack: 2560.7 MB/s
*/
__asm__("" : "+r" (result64));
#endif
}
return XXH3_avalanche(result64);
}
Even modern ARM chips are all about the pipelines. ARM's OoO execution is rather basic compared to x86, and many low end/older chips (including AArch64) are completely in-order.
An issue with the original implementation I ran into while porting the XXH3 algorithm to C++: While the first member (and therefore the whole struct) of XXH3_state_s is aligned to a 64 byte boundary when allocated statically, malloc and therefore XXH3_createState doesn't respect that which can lead to segmentation faults when running the AVX2 version of the algorithm.
The issue has been observed while using Travis CI (which uses an unspecified 'AMD64' CPU) and personally on a Ryzen 1600 with the -march=native setting.
Travis job log which contains an example of such a segmentation fault and its stack trace: https://travis-ci.org/RedSpah/xxhash_cpp/jobs/659205982
Good catch!
Hmm.
_mm_malloc/posix_memalign/_aligned_alloc/etcUGLY HACKalignas and use natural alignmentMalloc alignment is now fixed manually (method 2), see #330.
The sanity check now also uses the createState functions to test it.
@Cyan4973 might be a good idea to put that patch into master as well — it is a rather serious bug.
Just went to go update my XXH3 implementation in easyaspi314/xxhash-clean:xxh3.
Oh my how XXH3 has changed…
Just broke the 6 GB/s barrier on my phone with Clang 9 by moving the veorq_u64 below the if block.
./xxhsum 0.7.3 (64-bit aarch64 + NEON little endian), Clang 9.0.1 , by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 28142 it/s ( 2748.3 MB/s)
XXH32 unaligned : 102400 -> 23074 it/s ( 2253.3 MB/s)
XXH64 : 102400 -> 31512 it/s ( 3077.4 MB/s)
XXH64 unaligned : 102400 -> 31543 it/s ( 3080.4 MB/s)
XXH3_64b : 102400 -> 62141 it/s ( 6068.5 MB/s)
XXH3_64b unaligned : 102400 -> 57487 it/s ( 5614.0 MB/s)
XXH3_64b w/seed : 102400 -> 61413 it/s ( 5997.3 MB/s)
XXH3_64b w/seed unaligned : 102400 -> 57456 it/s ( 5611.0 MB/s)
XXH3_64b w/secret : 102400 -> 59019 it/s ( 5763.6 MB/s)
XXH3_64b w/secret unaligned : 102400 -> 53962 it/s ( 5269.7 MB/s)
XXH128 : 102400 -> 51385 it/s ( 5018.1 MB/s)
XXH128 unaligned : 102400 -> 49295 it/s ( 4813.9 MB/s)
XXH128 w/seed : 102400 -> 52260 it/s ( 5103.5 MB/s)
XXH128 w/seed unaligned : 102400 -> 49710 it/s ( 4854.5 MB/s)
XXH128 w/secret : 102400 -> 49710 it/s ( 4854.5 MB/s)
XXH128 w/secret unaligned : 102400 -> 46561 it/s ( 4547.0 MB/s)
Clang seems to interleave it better that way.
GCC 9 is slightly slower, although it is slower in general (4.5 GB/s) due to using inline assembly everywhere in arm_neon.h and therefore not having any pattern recognition.
However, screw GCC AArch64. Everybody uses clang anyways. :joy:
Add proper builtins and then I might change my mind
Updated xxhash-clean with the latest XXH3.
https://github.com/easyaspi314/xxhash-clean
Not planning to do streaming — not yet anyways.
The other cool thing is that it can compile really small, especially since XXH3_64bits and XXH3_128bits are isolated.
aarch64-linux-android-clang 9.0.1 -Oz
xxh3-64b-ref.o :
section size addr
.text 1440 0
.rodata 256 0
.comment 22 0
.note.GNU-stack 0 0
.debug_frame 48 0
Total 1766
xxh3-128b-ref.o :
section size addr
.text 2028 0
.rodata 256 0
.comment 22 0
.note.GNU-stack 0 0
.debug_frame 72 0
Total 2378
XXH_INLINE_ALL wrapping the same functions:
xxh3-64b.o :
section size addr
.text 1792 0
.rodata 256 0
.comment 22 0
.note.GNU-stack 0 0
.debug_frame 88 0
Total 2158
xxh3-128b.o :
section size addr
.text 2324 0
.rodata 256 0
.comment 22 0
.note.GNU-stack 0 0
.debug_frame 48 0
Total 2650
ABI compatible with the single shot functions.
Edit: Happy Pi Day!
RISC-V 64-bit on qemu-riscv64 4.1.1 on my Pixel 2 XL (because my PC is in use)
Clang 9.0.1
musl libc
xxhsum-rv64 0.7.4 (64-bit riscv + mul little endian), Clang 9.0.1 , by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 5829 it/s ( 569.3 MB/s)
XXH32 unaligned : 102400 -> 5830 it/s ( 569.3 MB/s)
XXH64 : 102400 -> 6212 it/s ( 606.7 MB/s)
XXH64 unaligned : 102400 -> 6238 it/s ( 609.2 MB/s)
XXH3_64b : 102400 -> 5032 it/s ( 491.4 MB/s)
XXH3_64b unaligned : 102400 -> 5043 it/s ( 492.5 MB/s)
XXH3_64b w/seed : 102400 -> 5036 it/s ( 491.8 MB/s)
XXH3_64b w/seed unaligned : 102400 -> 5038 it/s ( 492.0 MB/s)
XXH3_64b w/secret : 102400 -> 2392 it/s ( 233.6 MB/s)
XXH3_64b w/secret unaligned : 102400 -> 2392 it/s ( 233.6 MB/s)
XXH128 : 102400 -> 5165 it/s ( 504.4 MB/s)
XXH128 unaligned : 102400 -> 5139 it/s ( 501.9 MB/s)
XXH128 w/seed : 102400 -> 5190 it/s ( 506.9 MB/s)
XXH128 w/seed unaligned : 102400 -> 5170 it/s ( 504.9 MB/s)
XXH128 w/secret : 102400 -> 2357 it/s ( 230.2 MB/s)
XXH128 w/secret unaligned : 102400 -> 2353 it/s ( 229.8 MB/s)
Note that Clang uses byteshift loads, and it seems that RISC-V has optional but recommended unaligned access, saying it can be managed by the execution environment or implemented in hardware. This was intended to make implementing unaligned access easier/having the ability to disable it on embedded.
If I do XXH_FORCE_MEMORY_ACCESS=2, we get a much better speed, but I'm not 100% sure it is safe.
xxhsum-rv64 0.7.4 (64-bit riscv + mul little endian), Clang 9.0.1 , by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 9306 it/s ( 908.8 MB/s)
XXH32 unaligned : 102400 -> 8457 it/s ( 825.8 MB/s)
XXH64 : 102400 -> 17902 it/s ( 1748.3 MB/s)
XXH64 unaligned : 102400 -> 16735 it/s ( 1634.3 MB/s)
XXH3_64b : 102400 -> 18693 it/s ( 1825.5 MB/s)
XXH3_64b unaligned : 102400 -> 17454 it/s ( 1704.5 MB/s)
XXH3_64b w/seed : 102400 -> 18399 it/s ( 1796.7 MB/s)
XXH3_64b w/seed unaligned : 102400 -> 17810 it/s ( 1739.3 MB/s)
XXH3_64b w/secret : 102400 -> 16885 it/s ( 1648.9 MB/s)
XXH3_64b w/secret unaligned : 102400 -> 16311 it/s ( 1592.8 MB/s)
XXH128 : 102400 -> 18250 it/s ( 1782.2 MB/s)
XXH128 unaligned : 102400 -> 17769 it/s ( 1735.3 MB/s)
XXH128 w/seed : 102400 -> 18089 it/s ( 1766.5 MB/s)
XXH128 w/seed unaligned : 102400 -> 17102 it/s ( 1670.1 MB/s)
XXH128 w/secret : 102400 -> 16692 it/s ( 1630.1 MB/s)
XXH128 w/secret unaligned : 102400 -> 16252 it/s ( 1587.2 MB/s)
Also, here's mips64el (MIPS VI) on qemu-mips64el 2.11.50 (because 4.4.0 isn't in the repos and I already had that version patched for Termux)
xxhsum-mips 0.7.4 (64-bit mips64 little endian), Clang 9.0.1 , by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 8909 it/s ( 870.0 MB/s)
XXH32 unaligned : 102400 -> 8545 it/s ( 834.5 MB/s)
XXH64 : 102400 -> 20445 it/s ( 1996.6 MB/s)
XXH64 unaligned : 102400 -> 17705 it/s ( 1729.0 MB/s)
XXH3_64b : 102400 -> 15062 it/s ( 1470.9 MB/s)
XXH3_64b unaligned : 102400 -> 14507 it/s ( 1416.7 MB/s)
XXH3_64b w/seed : 102400 -> 15050 it/s ( 1469.7 MB/s)
XXH3_64b w/seed unaligned : 102400 -> 14759 it/s ( 1441.3 MB/s)
XXH3_64b w/secret : 102400 -> 14367 it/s ( 1403.1 MB/s)
XXH3_64b w/secret unaligned : 102400 -> 13759 it/s ( 1343.6 MB/s)
XXH128 : 102400 -> 15052 it/s ( 1469.9 MB/s)
XXH128 unaligned : 102400 -> 14304 it/s ( 1396.8 MB/s)
XXH128 w/seed : 102400 -> 14735 it/s ( 1438.9 MB/s)
XXH128 w/seed unaligned : 102400 -> 14463 it/s ( 1412.4 MB/s)
XXH128 w/secret : 102400 -> 14290 it/s ( 1395.5 MB/s)
XXH128 w/secret unaligned : 102400 -> 13481 it/s ( 1316.5 MB/s)
Also, damn, generating a constant is torture on RISC-V...
int64_t load_constant(void)
{
return 0x165667919E3779F9;
}
```asm
load_constant:
lui a0, 45
addiw a0, a0, -1331
slli a0, a0, 14
addi a0, a0, -883
slli a0, a0, 14
addi a0, a0, -913
slli a0, a0, 15
addi a0, a0, -1543
ret
```c
int64_t load_constant(void)
{
int32_t a0_32 = 45 << 12;
a0_32 = a0_32 - 1331;
int64_t a0 = (int64_t)a0_32; // sign extend
a0 = a0 << 14;
a0 = a0 - 883;
a0 = a0 << 14;
a0 = a0 - 913;
a0 = a0 << 15;
a0 = a0 - 1543;
return a0;
}
I spent the past days trying to find and exploit other weaknesses, either in implementation or in the algorithm itself, using a few hunches where I expected to find exploitable problems, but ultimately couldn't trigger any additional issue.
So I presume the scope is now good enough to contemplate a new release v0.7.4 .
By far, the most important remaining decision is : is it worth fixing the avalanche issue detected by demerphq test when employing the seed as the variable (as opposed to the input) => #395
The use case seems minor, though not necessarily "useless". And this is more or less the last chance to fix something like that, as next planned release, v0.8.0 will officially stabilize the output, making it impossible to change function return value afterwards.
Also, indirectly, this could open the door to additional minor changes that were kept at bay because they were also impacting the output, such as for example @easyaspi314 's suggestion to change the default secret to use the decimal of Pi instead (or any other "famous" constant with known random qualities).
These changes are not expecting to impact the planning much, a few days at most. So this is more about taking a decision.
If you want to voice your opinion on this topic, now is a great time.
For the record, list of other topics that can still be worked upon, but are not _required_ for next release :
_withSeed128(), suggested by @koraa.generateSecret(), able to generate secrets of custom length (instead of being limited to a single pre-defined length).-c check capability for BSD-style checksums (produced by --tag)x86_dispatch in the libraryIf some tweak is done that changes the computed values anyway, then would/could #342 be rolled into the same release too?
Yes @aras-p , #342 is part of the list of "minor but breaking change" that would become opened for review and potential inclusion.
OK, time to take a decision,
I lean on making the #395 change part of the release. Here is my line of reasoning:
XXH64 avalanche instead of rrmxmx, performance impact has been minimized to the point of being barely noticeable in benchmarks. So it seems like a change which purely improves quality, without performance downside.v0.7.4 is planned to be released later this week, followed by v0.8.0 a few weeks later, which will officially stabilize the output of XXH3 and XXH128.Now, speaking of planning, if I merge this change, then other breaking changes can be introduced too.
Among them, updating the default kSecret, and reducing scrambling (#342).
But in order to keep the planning unchanged, these changes need to be completed within the next few days.
Btw, @easyaspi314 , are you still interested in updating kSecret ?
_edit_ : created new branch newOutput074 where all changes impacting hash return values will be merged, for proper validation.
_edit 2_ : pushed branch Pi which modifies kSecret with decimals of Pi as provided by http://hexpi.sourceforge.net/
All breaking changes are now merged into staging branch newOutput074.
I will now initiate long resiliency and quality tests, to ensure this new variant features no hidden issue (none expected).
Should be completed within a day.
I'm trying to find a good define that will let the C preprocessor differentiate if the XXH3 routines are available via the xxhash.h include. This is so that my code can auto-enable/disable support of the newer hash algorithms no matter what xxhash-devel package the user has installed (I'm hoping to avoid a compile test via autoconf). Obviously there's not a released version that has XXH3 algorithms in the stock xxhash.h yet, so what does the future hold?
Any chance for a define that would be supported currently via xxh3.h and would also be present in the future via xxhash.h? Or is the best differentiator going to be via some future XXH_VERSION_NUMBER value check?
At the moment I settled on a combination of my own define for if xxh3.h should be included combined with a version check:
#ifdef PRE_RELEASE_XXHASH
#include <xxh3.h>
#endif
#include <xxhash.h>
#if defined PRE_RELEASE_XXHASH || XXH_VERSION_NUMBER >= 800
#define SUPPORT_XXH3 1
#endif
XXH_VERSION_NUMBER is probably your best option, yeah.
xxHash installs xxh3.h on v0.7.3 and later. The single shot functions are fine to use, but keep in mind that there are some nasty bugs in the streaming implementation which are to be fixed in the next release.
Also, don't include xxh3.h directly. It is likely going to disappear, and you can just do this:
#define XXH_INLINE_ALL
#include <xxhash.h>
Is there a plan for what the first version number will be that includes XXH3 & XXH128 by default? Is it going to be 1.0.0 (aka 10000)?
It will either be v0.8.0 or v1.0.0, but both will trigger on XXH_VERSION_NUMBER >= 800. :slightly_smiling_face:
Time to clearly define the scope to upgrade to "stable" status for v0.8.0.
Not everything will reach this label. In the text below, I'll divide the different parts of the API, from easiest to decide to more difficult.
This is the minimal scope which, I believe, is beyond dispute and will be labelled stable for next release.
64-bit one shot functions :
XXH3_64bits()
XXH3_64bits_withSeed()
State management functions, from streaming :
XXH3_createState()
XXH3_freeState()
XXH3_copyState()
Streaming functions, with equal scope as one-shot functions :
XXH3_64bits_reset()
XXH3_64bits_reset_withSeed()
XXH3_64bits_update()
XXH3_64bits_digest()
128-bit one-shot hash function :
XXH3_128bits()
Helpers for XXH128_hash_t type :
Since it's not an integral type, standard comparison properties are not provided natively by the language. They must be created, which is what these functions offer :
XXH128_isEqual()
XXH128_cmp()
The following functions will _not_ be stabilized at v0.8.0.
They may become stabilized later, though in a future version (v0.9.0 for example).
XXH3_generateSecret() :This function takes a custom seed of any length, and convert it into a high entropy secret of size XXH3_SECRET_DEFAULT_SIZE, suitable to be employed in combination with _withSecret() variants.
The primary reason to not stabilize this function is to make it possible to change its output. This function is still very new, and new requirements may appear during the testing period.
For example, a recent discussion suggested a need to have a special resolution for seed of size 8, mimicking the internal generation of secret when using the _withSeed() variants, for reproducibility.
Another opened question is about the size of the generated secret : right now, it's static, set at XXH3_SECRET_DEFAULT_SIZE. Should it be possible to make the secret's size a parameter of the function ? If yes, should it be a parameter of _this_ function, or should another (advanced) function be created for this purpose ?
XXH3_128bits_withSeed128() and corresponding XXH3_128bits_reset_withSeed128() :@koraa mentioned a need for a hash using a 128-bits seed. There were not a lot of requests for this feature, but it's definitely a possible one. However, it will take a bit of time to develop. I don't want to commit to it for next version, and more importantly, even if I do, these functions will start their life in the experimental section, and won't join the "stable" section of the API in their first incarnation.
_withSeedAndSecret() and / or _withState() :A recent discussion started by @gzm55 suggests the creation of a new function variant, primarily in order to optimize speed of _withSeed() variants in scenarios where the seed remains constant, trying to avoid the reconstruction of the secret at each round in order to save some latency budget, measurable when input is "medium" size and the selected vector instruction set is AVX.
The discussion is still ongoing, about the merits and consequences of different possible approaches. There is no guarantee that it will result in the creation of new functions during this cycle, and even if it does, these functions will be too young to join the "stable" area.
_256bits*()The need for such a variant is very low, mostly confined to curiosity level, while the amount of work required is very high.
I simply don't intend to work on it in the foreseeable future, so, obviously, not part of v0.8.0.
Sorted from easier to more difficult to settle.
This paragraph regroups XXH3_128bits_reset(), XXH3_128bits_update() and XXH3_128bits_digest().
I think there is no question regarding the scope : of course, streaming 128-bit variants are required for the stabilized scope.
Rather, one could note that XXH3_128bits_reset() is effectively the same as XXH3_64bits_reset(), and XXH3_128bits_update() is exactly the same as XXH3_64bits_update().
This is true since v0.7.4, when the inner loop has been simplified to always employ the stronger 128-bit one.
This underlines an opportunity : could they be merged ?
In such an alternative design, one would see XXH3_reset() and XXH3_update(). The distinction between 64-bit and 128-bit output would only be specified at digest invocation.
This is mostly an API design question. In term of behavior, nothing is changed.
One try to maintain a form of consistency, by prefixing all 128-bit functions with XXH3_128bits_*(),
the other underlines versatility, and how the choice between 64 and 128-bit can be postpone up to the last moment.
Both choices are fine, it's just a matter of selecting one.
XXH3_128bits_withSeed() and XXH3_128bits_reset_withSeed()This is a follow-up of the suggestion from @koraa to introduce _withSeed128() variants.
There are 2 potential questions :
_withSeed() variants ?_withSeed64(), to better emphasize the difference with Seed128 ?I believe it's possible to settle this question. And I believe the answer to both is "no".
I don't think that a variant using a 128-bit seed invalidates the need for another variant using a 64-bit seed.
As mentioned before, integral types are _much_ easier to use. This statement goes beyond C/C++ scenarios : bindings from multiple languages will also exist, and while I don't doubt that solutions exist to manipulate XXH128_hash_t structures from higher level languages, it's also certainly more complex that integrals.
So I believe both can exist.
As for the name, changing from _withSeed() to _withSeed64() would question the equivalent variant of XXH3_64bits*(). It seems that both names would need to change for consistency. This would delay stabilization of _withSeed() variants by another round.
I don't believe there's a need for that, and we can probably accept _withSeed() variants as part of the stabilized scope for v0.8.0. We'll discover later if a _withSeed128() actually exists, and if does, I believe that the distinctive name (and prototype) will be enough to not confuse them.
_withSecret()A comment by @gzm55 underlines that these functions are targeted at "advanced" users, because it's easy to misuse them. For example, it's fairly easy to provide a secret with bad randomness properties, resulting in poor hash quality.
I presume the intended objective is make these variants less accessible.
However, by keeping them in the "experimental" section, it implies, by default, a risk that the return values of these functions may change in the future, strongly reducing their usefulness (only session-local, no storage, no transmission).
Thing is, I don't see any alternate scenario regarding the usage and algorithm of _withSecret() functions. In my view they are perfectly well defined, and don't need a change in the future.
This lead us to 2 solutions :
secret).The current stance is to select option 2, which looks reasonable to me.
If one feels differently about it, now would be good time to present your arguments.
XXH128()XXH128() is a shortcut for the one-shot 128-bit variant, mirroring existing functions XXH32() and XXH64().
Sure, but which one ?
Currently, it's mapped to XXH3_128bits_withSeed(), because both XXH32() and XXH64() offer a seed parameter, so it maintains consistency.
However, presuming that one day a XXH3_128bits_withSeed128() variant exist, it also becomes a contender.
Therefore, which one should become the simplified XXH128() ? _withSeed() or _withSeed128() ?
One could note that the seed of XXH32() is 32-bit, the seed of XXH64() is 64-bit, consequently, it would feel somehow logical for XXH128() to offer a 128-bit seed.
However, there are arguments in the opposite direction :
_withSeed128() doesn't exist yetseed is _more complex_ than a 64-bit one, since it's no longer an _integral_ type. As a shortcut function name, XXH128() should better lean towards the simpler variant to use.XXH128() would break existing code This topic is the least decided, and I can see arguments leaning both ways.
In the worst case, if there is no clear winner, stabilization of this prototype could be delayed to v0.9.0.
But, maybe there is no need to, and it could be settled now, right on time for v0.8.0.
Among the other actions required for the release, API declaration of xxhash.h must be updated, obviously, to include the newly stabilized API into the public section, so that it will no longer require XXH_STATIC_LINKING_ONLY.
Also, xxh3.h must be integrated into xxhash.h (implementation section). I think I will keep xxh3.h around, but more as a stub, so that programs currently including it will continue compiling correctly. This is temporary : as a file, xxh3.h will disappear in a future release. But there is no urgency.
Finally, the README.md should be updated to reflect the presence of XXH3, with new benchmarks using more recent systems, typically taken from there.
Current proposal for v0.8.0 : #435
All existing XXH3 prototypes are promoted to stable status without modification,
except XXH3_generateSecret() and XXH128()
which both remain experimental, preserving a possibility to change them in future versions.
Is it okay if we set XXH64_hash_t to unsigned long on LP64?
This would match stdint.h, and fix some inconsistency annoyances, especially with NEON which uses uint64_t and warns on xxh_u64 in gnu90 mode.
/* LP64 defines uint64_t as unsigned long, try to match it. */
# if defined(__LP64__) && ULONG_MAX == 0xFFFFFFFFFFFFFFFFULL
typedef unsigned long XXH64_hash_t;
# else
typedef unsigned long long XXH64_hash_t;
# endif
I presume it is
Ok, how is this? It should cover all cases.
#ifndef XXH64_HASH_T_DEFINED
# define XXH64_HASH_T_DEFINED
# if !defined (__VMS) \
&& (defined (__cplusplus) /* C++ */ \
|| (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) \
|| defined(UINT64_MAX) /* stdint.h already included */)
# include <stdint.h>
typedef uint64_t XXH64_hash_t;
# else
# include <limits.h>
/* Fake stdint.h */
# if defined(__UINT64_TYPE__) /* usually predefined by GCC */
typedef __UINT64_TYPE__ XXH64_hash_t;
# elif defined(_MSC_VER) /* MSVC */
typedef unsigned __int64 XXH64_hash_t;
# elif ULONG_MAX == 0xFFFFFFFFFFFFFFFFULL /* LP64 ABI */
typedef unsigned long XXH64_hash_t;
# else
typedef unsigned long long XXH64_hash_t;
# endif
# endif
#endif /* XXH64_HASH_T_DEFINED */
The XXH64_HASH_T_DEFINED macro will prevent something like this from happening:
#include <xxhash.h>
#include <stdint.h>
#define XXH_INLINE_ALL
#include <xxhash.h>
Okay, it looks complex, but I guess it indeed adapts to a lot of situations.
Presuming that the rest of the code base already makes a good job of not confusing XXH64_hash_t withunsigned long long, I guess it should be fine (note : compiling with -Wconversion will be important here).
The XXH64_HASH_T_DEFINED macro will prevent something like this from happening:
Have you checked that this is actually required ?
I would expect current code to already protect from such multi-include issue.
If it does not, that's good to know too !
Actually, this still isn't good enough.
The check for stdint.h being included is overkill, and old MSVC versions don't have stdint.h even in C++ mode.
This should work:
#if defined(_MSC_VER) /* MSVC has always supported these types */
typedef unsigned __int32 XXH32_hash_t;
typedef unsigned __int64 XXH64_hash_t;
#elif !defined(__VMS) \
&& ( \
(defined(__cplusplus) && __cplusplus >= 201103L) /* C++11 */ \
|| (defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L) /* C99 */ \
)
# include <stdint.h>
...
#else
....
#endif
I tested on VC++2005 and sure enough, when compiled in C++ mode, it errors because it can't find stdint.h.
It found two other issues:
_mm_castps_si128 isn't on this version of MSVC. Why are we using that?extern "C" instead of only using it for declarations. MSVC does not like that. If we want to be compatible with basically any compiler we put at it, why not add a few CI checks against uncommon/really old compiler/libc combos? It is good for testing and flexing
I have figured out how to programmatically download and install the VC++2005 CLI tools from PowerShell, and I can probably set up a GCC 3.3/glibc 2.2 toolchain for Linux. We can cache these.
If the test becomes so complex, it may be better to create a new build macro like XXH_HAVE_STDINT which could be determined externally, or set manually, so that it's easier to adjust to any configuration.
If we want to be compatible with basically any compiler we put at it
There are some limits to this exercise.
I'm generally favorable to any minor change / tweak which increases the range of compatible compilers without affecting much the code structure.
Also, if we want to pretend that a given compiler is supported, then it needs to be part of CI. Reason is, it's way too easy for any contributor in the future to introduce code which break some of these compilers since most contributors won't check anything beyond their own system and the automated tests.
If an old or rare compiler requires some larger code change to adjust, with several modifications spread out into the code base, then it's best to leave that out. We don't want to impact general code readability and maintenance for the sake of a very rare scenario.
Good point. It is a little complicated.
I will make a PR with the fixes for those though, as well as obeying strict aliasing as best as I can in the main loop.
xxHash v0.8.0 has been released this morning, it stabilizes output values of XXH3.
Side-question : is it still necessary to keep this "general discussion" thread open ?
Now that XXH3 is stabilized, we may be better off using the regular issue board for more targeted topics ?
is it still necessary to keep this "general discussion" thread open
I'd say close this one; more targeted issues are better once things are stable & settled down.
Most helpful comment
All breaking changes are now merged into staging branch
newOutput074.I will now initiate long resiliency and quality tests, to ensure this new variant features no hidden issue (none expected).
Should be completed within a day.