Sort issue with K64V64 or uint128_t

[jeromeDelrieu]

When using 128bit sort an assert can occur in the Recurse method:
HWY_DASSERT(bound != 0);

Or the sort is not sorted correctly (we have a signed sort instead).

Small example:

const int nbValues = 1000;
hwy::K64V64 listValues[nbValues];

for (int i = 0; i < nbValues; i++) {
listValues[i].key = i;
listValues[i].value = i - 500;
}
hwy::VQSort(listValues, nbValues, hwy::SortAscending());
for (int i = 1; i < nbValues; i++) {
HWY_DASSERT(listValues[i - 1].value <= listValues[i].value);
}

It is compiled on windows for x64, with clang, and the dispatch used is AVX2.

[jeromeDelrieu]

The result can be OK in release with more records, because the pivot is really bad, and it reverts to heapsort.
So if we are not in debug, there is no assert and it can be visible only with the poor performances.
It should be easy to reproduce, and it can also be reproduced with msvc compiler.

[jeromeDelrieu]

Any thoughts on this issue ?

[jan-wassenberg]

Oops, somehow I missed this issue, sorry about that and thanks for pinging it. I will investigate soon :)

[jan-wassenberg]

I have run your code and it looks like there might be a misunderstanding :) .key is what we are actually sorting on, whereas the repro checks value (this is a 'payload' that the sort comparator ignores). When changing the assert to check key, the test passes. I've tried this in release and debug builds, also with asan, and also printing information on each recursion, which looks reasonable.

Can you confirm it's fine if we switch the assert to key?

[jeromeDelrieu]

Sorry, for the bad repro code.
I found out what is happening. The buffer given to the sort function have to be aligned to 128bit.
Mine was aligned only to 64 bit.
Is it mandatory to be aligned to 128bit for the 128bit sort ? I found nothing in the documentation on this issue.

[jan-wassenberg]

Oh, interesting, glad you found the root cause. Generally it is a good idea to element-align data (so alignof == sizeof), some platforms can fault otherwise. But I do not yet understand why we would sort incorrectly if unaligned.

[jeromeDelrieu]

Here is the correct repro code.
Better in debug to see the assert in "vqsort-inl.h" :
// ChoosePivot* ensure pivot != last, so the right partition is never empty
// except in the rare case of the pivot matching the last-in-sort-order value,
// which implies we anyway skip the right partition due to kWasLast.
HWY_DASSERT(bound != num || result == PivotResult::kWasLast);

const int nbValues = 1000;
size_t sizeData = sizeof(hwy::K64V64) * (nbValues + 1);
unsigned char *pBuffer = (unsigned char *)malloc(sizeData + 8);
unsigned char *pUsedBuffer = pBuffer;
if ((size_t(pUsedBuffer) & 0xF) == 0) {
   pUsedBuffer += 8;
}
hwy::K64V64 *pArray = (hwy::K64V64 *)pUsedBuffer;
for (int i = 0; i < nbValues; i++) {
  pArray[i].value = i;
  pArray[i].key = i - 500;
}

hwy::VQSort(pArray, nbValues, hwy::SortAscending());
for (int i = 1; i < nbValues; i++) {
  HWY_DASSERT(pArray[i - 1].key <= pArray[i].key);
}
free(pBuffer);

For me this is an issue, because i cannot force 16 bytes alignment on the buffer easily.