Xxhash: Runtime check for AVX2

[erijo]

I was looking at experimenting with XXH3 and ccache when I noticed that there doesn't seem to be any runtime check to verify that the CPU actually supports e.g. AVX2. Even if the compiler supports it, it's not certain that the CPU does. Or the CPU supports it but it may be disabled by the OS.

I would assume that such a runtime check is needed to be able to enable e.g. AVX2 support in a generic binary.

I've done some trivial runtime dispatching using __builtin_cpu_supports("avx2) which may be an alternative but have some limitations (see e.g. this comment).

For a better example, see blake3_dispatch.c for details on how BLAKE3 handles this.

[easyaspi314]

Why not use a function pointer?

I had something like this:

static void (*XXH3_hashLong)(...) = &XXH3_dispatch;

static void XXH3_dispatch(...) {
    if (CPU.supports(AVX2)) {
          XXH3_hashLong = &XXH3_hashLong_AVX2;
    } else if (...) {
        ...
    }
    XXH3_hashLong(...);
}

We have to find the right place to break off which allows constprop (or not?)

See https://github.com/easyaspi314/xxHash/tree/multitarget-v2.

[Cyan4973]

The most important opened question when we looked at it some time ago was :
"where does it make sense to make this selection" ?

My position was that it makes sense to add this runtime detection into xxhsum.c, aka the CLI program,
but I'm less enthusiastic about forcing its presence inside the core library itself (i.e. xxhash.c, now effectively xxhash.h), as I can imagine many scenarios where the presence of a runtime detection mechanism is unwelcome.

Looking at the Blake3 example, it seems something equivalent could be done.
It requires the creation of an additional dispatch level, either part of its own separate xxh_dispatch.c unit, or as part of xxhsum.c, which could embed the detection test and then dispatch to the appropriate variant. Each variant can be compiled either as a separate object file, with the help of compilation flags and XXH_NAMESPACE to rename symbols and avoid duplication, or by relying on inlining and enforcing bytecode with compilation flags directly within the source code (slightly more complex, requires that inlining is enforced. _note_: this is the way zstd detects and enforces bmi2 at runtime).

I'm fully opened to progresses on this topic, the sole condition is that the detection mechanism must remain on the xxhsum (program) side.

[easyaspi314]

the detection mechanism must remain on the xxhsum (program) side

So you are saying that we should only dispatch in the xxhsum binary instead of the library?

Seems kinda pointless for a library.

Also, may I bring up the idea of splitting up the source files again? We have three >70 kB files with 1.7k lines each, and 4 completely different hash functions which don't actually share a lot of code. (The algorithms are similar, but aside from a few inlines and XXH3_hashLong, they are independent)

Even if we duplicate the things like kSecret, XXH3_update, etc, most people will be either inlining or using a static library (which benefits from split object files, so aside from a shared library and xxhsum, it will allow smaller code and faster compilation.

[Cyan4973]

Both questions go actually hand in hand.

How will the library be used ?
Sure, a program can link to the dynamic library libxxhash, and this is probably fine for check-summing. But for _many_ usages, especially involving small data, the library will have to be inlined, for adequate performance. So integration is often at source code level.
And now it makes the integration experience fairly critical to the success of the library. Having just one file to include in any project considerably simplifies this step, and that's a major benefit that should not be under-estimated.

That's why the target is a single xxhash.h file, with a companion xxhash.c (when inlining is not required). xxh3.h is a temporary add-on, to underline that it is in development, but it will be merged when stabilized.

Now, I'm aware that it makes xxhash.h a long file, if not a very long one, and that's indeed a pity. If the project was self-contained, yes, sure, this file could be separated into several smaller ones. But the integration experience matters _a lot_, and I don't take a chance on this topic.

Now, it's also a reason to properly define what's the content of this un-splittable "core", and limit it to what is essential. Anything else can be _outside_ of this single-file policy.

xxhsum.c for example doesn't need to be a single file. It can be separated into multiple components. It doesn't matter as much, since it's primarily a self-contained project, delivered ready-to-compile with its own build scripts.

And by the way, the component in charge of detecting cpu capabilities and routing invocations to the proper bytecode ? Yes, it's part of xxhsum "domain", but it can be its own separate unit.

Now that's interesting because it allows a user to integrate a custom scope, larger than just the "core" one. To simplify :

xxhsum -> bytecode selector -> xxhash core lib

A user could select to embed _both_ the core library and the bytecode selector into its own program, the same way xxhsum would do it.

The important part is that integrating the selector is _opt in_. This design choice is necessary because I'm pretty sure that a commanding share of datacenter applications will _not_ want it, and they must be able to include xxhash with the safety that the selector is not part of the deal.

And of course, it should be possible for those who want it. It's merely an extended scope.

[gzm55]

How will the library be used ?
Sure, a program can link to the dynamic library libxxhash, and this is probably fine for check-summing. But for many usages, especially involving small data, the library will have to be inlined, for adequate performance. So integration is often at source code level.
And now it makes the integration experience fairly critical to the success of the library. Having just one file to include in any project considerably simplifies this step, and that's a major benefit that should not be under-estimated.

Even we integrate xxhash by inlining header instead of linking library, we still need this feature. Some CPU feature are the super set of another, and share most common instructions, such as SSE -> AVX -> AVX2. In reality, a distributed services is built once and deployed everywhere. If some of machines are AVX and others AVX2, we have to compiled the service as AVX/SSE which lost performance on new hardwares. The CI matrix is already very large, so many teams cannot afford to build different binaries for each X64 sub features. With runtime check, the same binary can dispatch the calculation to the proper branch, or fallback to scalar version.

[easyaspi314]

With runtime check, the same binary can dispatch the calculation to the proper branch, or fallback to scalar version.

The nice thing about this is that we don't need the scalar version on x86_64 and aarch64 — SSE2 and NEON are required by the architecture.

But yeah, this needs to be looked at.

[Cyan4973]

a distributed services is built once and deployed everywhere. If some of machines are AVX and others AVX2 (...) With runtime check, the same binary can dispatch the calculation to the proper branch, or fallback to scalar version.

I agree.
And I believe it's compatible with the suggestion above to create an "overlay" library, that would encapsulate xxhash.h, and enforce the dispatch based on runtime detection of cpu features.
Such overlay would be integrated into xxhsum, but could also be integrated into any other application looking for equivalent capabilities.

[Cyan4973]

@easyaspi314 , I know you wanted to create an AVX2/SSE2 dispatcher some time ago,
do you still have time and want to work on it ?

If not, I would be able to start something before the end of the week. Just trying to avoid silent effort duplication.

[easyaspi314]

I mean all I have is time thanks to being stuck in the house. :weary:

I can work on it.

So this is the plan I am thinking of.

1. Add XXH_DISPATCH flag which replaces the hashLong family with an external function pointer
2. Define XXH_COMPILING_DISPATCH, which defines XXH_INLINE_ALL and only makes an external symbol for hashLong.
3. Recompile xxhash.c a few times with different flags.
4. Define the hashLong function pointer in xxhash-dispatch.c
5. Make the initial function pointers do this:

static void XXH3_hashLong_64b_defaultSecret_dispatch(const xxh_u8 *input, size_t len);
void (*XXH3_hashLong_64b_defaultSecret)(const xxh_u8 *input, size_t len) = XXH3_hashLong_64b_defaultSecret_dispatch;
static void XXH3_dispatchInit(void)
{
   // check features
    XXH3_hashLong_64b_defaultSecret = <dispatched func>
}

static void XXH3_hashLong_64b_defaultSecret_dispatch(const xxh_u8 *input, size_t len)
{
    XXH3_dispatchInit();
    XXH3_hashLong_64b_defaultSecret(input, len);
}

Either way, it will be ugly, though.

Dispatching the entire thing will be completely redundant and slow down short hashes.

[Cyan4973]

I'm sure it can be made to work this way.
That being said, I'm afraid a solution based on a combination of complex build system + source support will indeed be painful to deploy, and even more painful to integrate into a 3rd party code base.

I would prefer a solution entirely based on source code.
And I believe it's possible, because we basically achieved just that in zstd.

Code example, for reference : https://github.com/facebook/zstd/blob/v1.4.4/lib/decompress/huf_decompress.c#L77

The basic design works this way (pseudo-code) :

FORCE_INLINE function_body() { ... }

COMPILER_ATTRIBUTE_SSE2 function_sse2() {
   return function_body();
}

COMPILER_ATTRIBUTE_AVX2 function_avx2() {
   return function_body();
}

PUBLIC function() {
   if (g_feature == avx2) return function_avx2(); 
   else return function_sse2();
}

OK, real code requires some more boiler plate, but you get the gist of it.

Advantage : no code duplication. No multi-includes. Fully source code driven. No dependency on complex build procedure.

Disadvantage : tied to specific compiler implementations: the scheme depends on the ability to send a COMPILER_ATTRIBUTE_xxx directive at function level. And requires function_body() to be fully inlined.

Lastly, g_feature should be a local static variable initialized once, as querying the cpu about its feature flags is a long operation.

Suggestion for discussion.

[easyaspi314]

Disadvantage : tied to specific compiler implementations: the scheme depends on the ability to send a COMPILER_ATTRIBUTE_xxx directive at function level. And requires function_body() to be fully inlined.

Also to be noted: arm_neon.h and altivec.h physically cannot be included without NEON/Altivec support enabled entirely, and shutting off NEON is not something Clang likes to do, the primary issue I see with this approach.

[Cyan4973]

Well, there are limits I guess.
For example, removing SSE2 support for x86_64 target doesn't end well with clang either.

But I'm not sure that's an "additional" problem. If clang doesn't want to compile aarch64 without NEON support, then it doesn't want to. No other solution can fix that either.

Besides, we don't have to be "complete" on first try. I presume that the most important request is the ability to automatically invoke AVX2 when it's available. This could be a good enough use case to start an implementation, and then update it later to support more platforms.

[vlovich]

Can't you use the indirect function resolver for GCC/clang instead of manual dispatch? That happens once during loading which is friendlier when integrating into other tools.

[easyaspi314]

Might be an option instead of mucking with complicated inline assembly routines.

We would have to do a xgetbv check for AVX2 because some GCC versions don't check for OS support, but it would just be something like this:

int supports_avx2 = __builtin_cpu_supports("avx2");
if (supports_avx2) {
    unsigned eax, edx, ecx = 0;
    __asm__("xgetbv" : "=a" (eax), "=d" (edx) : "c" (ecx) : "cc");
    if (eax & AVX2_MASK) {
        // ok
    }
}

The only issue is that MSVC doesn't support it.

[easyaspi314]

Wait, you mean ifunc

That doesn't work on Windows or macOS.

however, I think we can do this

extern const XXH3_vtable_t *xxh3_vtable;
static void XXH3_dispatch(void)
{
    const XXH3_vtable_t *tmp;
#if !defined(__x86_64__) /* x86_64 always has sse2 */
    tmp = &xxh3_vtable_scalar;
    if (!__builtin_cpu_supports("sse2"))
        goto end;
#endif 
    tmp = &xxh3_vtable_sse2;
#ifdef XXH3_DISPATCH_AVX2
    if (!__builtin_cpu_supports("avx2") || (xgetbv(0) & AVX2_MASK) != AVX2_MASK)
        goto end;
    tmp = &xxh3_vtable_avx2;
#endif 
#ifdef XXH3_DISPATCH_AVX512
     if (__builtin_cpu_supports("avx512f") && (xgetbv(0) & AVX512_MASK) == AVX512_MASK)
        tmp = &xxh3_vtable_avx512;
#endif 
end:
    xxh3_vtable = tmp;
}
// Make clones
static XXH64_hash_t XXH3_hashLong_64b_defaultSecret_dispatch(const void *input, size_t len) {
    XXH3_dispatch();
    xxh3_vtable->hashLong_64b_defaultSecret(input, len);
}
// ...
static const XXH3_vtable_t xxh3_vtable_dispatch = {
    &XXH3_hashLong_64b_defaultSecret_dispatch,
     ...
};
const XXH3_vtable_t *xxh3_vtable = &xxh3_vtable_dispatch;

This would work on Windows, but it would add globals which might not be desired.

[gzm55]

writing a single byte will always be guaranteed atomic on all arch, and xxh3_vtable could be also static, while XXH3_dispatch() is still executed almost O(1) times.

static const XXH3_vtable_t XXH3_vtables[];
typedef enum {
  XXH3_RT_IMP_RESOLVER,
  XXH3_RT_IMP_SSE2,
  ...,
} imp_idx_t;

static uint8_t XXH3_vtables_idx = XXH3_RT_IMP_RESOLVER;
static void XXH3_dispatch(void) {
  // run time dispatch and save back to XXH3_vtables_idx.
  // the dispatching algorithm should and must be idempotent.
  XXH3_vtables_idx = XXH3_RT_IMP_SSE2;
}
static XXH64_hash_t XXH3_hashLong_64b_defaultSecret_dispatch(...) {
  XXH3_dispatch();
  XXH3_vtables[XXH3_vtables_idx].hashLong_64b_defaultSecret(...);
}
static const XXH3_vtable_t XXH3_vtables[] = {
  { .hashLong_64b_defaultSecret = &XXH3_hashLong_64b_defaultSecret_dispatch },
  { xxh3_vtable_sse2 },
  ...
};
static XXH64_hash_t XXH3_hashLong_64b_defaultSecret(...) {
    XXH3_vtables[XXH3_vtables_idx].hashLong_64b_defaultSecret(...);
}

[easyaspi314]

See #358.

[easyaspi314]

Should be fixed with #387

[vlovich]

ifunc wouldn't work with MSVC but clang-cl, clang & GCC should work so it might not be so bad to have MSVC vs everything else. I see you went with manual runtime dispatch though so probably not worth it.