Choose assembly implementation to use based on supported instructions

Question

I am working on a C library which compiles/links to a .a file that users can statically link into their code. The library's performance is very important, so I am writing performance-critical routines in x86-64 assembly to optimize performance.

For some routines, I can get significantly better performance if I use BMI2 instructions than if I stick to the "standard" x86-64 instruction set. Trouble is, BMI2 was introduced fairly recently and some of my users use processors that do not support those instructions.

So, I've written optimized the routines twice, once using BMI2 instructions and once without using them. In my current setup, I would distribute two versions of the .a file: a "fast" one that requires support for BMI2 instructions, and a "slow" one that does not require support for BMI2 instructions.

I am asking if there's a way to simplify this by distributing a single .a file that will dynamically choose the correct implementation based on whether the CPU on which the final application runs supports BMI2 instructions.

Unlike similar questions on StackOverflow, there are two peculiarities here:

• The technique to choose the function needs to have particularly low overhead in the critical path. The routines in question, after assembly-optimization, run in ~10 ns, so even a single if statement could be significant.
• The function that needs to be chosen "dynamically" is chosen once at the beginning, and then remains fixed for the duration of the program. I'm hoping that this will offer a faster solution than the one suggested in this question: Choosing method implementation at runtime

The fastest solution I've come up with so far is to do the following:

1. Check whether the CPU supports BMI2 instructions using the cpuid instruction.
2. Set a global variable true or false depending on the result.
3. Branch on the value of this global variable on every function invocation.

I'm not satisfied with this approach because it has two drawbacks:

• I'm not sure how I can automatically run cpuid and set a global variable at the beginning of the program, given that I'm distributing a .a file and don't have control over the main function in the final binary. I'm happy to use C++ here if it offers a better solution, as long as the final library can still be linked with and called from a C program.
• This incurs overhead on every function call, when ideally the only overhead would be on program startup.

Are there any solutions that are more efficient than the one I've detailed above?

Bossy

Set the global variable, not upon entry to main, but on the first call to one of your functions, using pthread_once or equivalent to ensure thread safety. – Informative

Don't worry about the cost of the branch; it will be predicted reliably after the first call. – Informative

Well, in the C++ itself (as language) you simply distribute the source and let the user to recompile it, that also allows for more specific (driven by user machine) optimizations of the C++ code to be applied. (also code without source is a zombie, in a decade or two it will be very likely dead, so unless you intentionally want to waste part of your life by creating something what will be lost in few years...) – Monophony

Answer 1

x264 uses an init function (which users of the library are required to call before calling anything else, or something like that) to set up a struct of function pointers based on CPUID results. Including taking into account that pshufb is slow on some early CPUs that support it.

If your functions depend on pdep / pext, you probably want to detect AMD vs. Intel, because AMD's pdep/pext is very slow and probably not worth using on Ryzen, even though it is available. (See https://agner.org/optimize/ for instruction tables.)

---

Function pointers are fairly low overhead, about the same as calling a function in a shared library or DLL. call [rel funcptr] instead of call func. (In the compiler-generated asm that calls your functions).

CPU dependent code: how to avoid function pointers? shows a very simple example of it in C, and is asking for ways to avoid it. With dynamic linking, you can do CPU detection at dynamic link time so the dynamic-linking indirection becomes your CPU-dispatch indirection as well (like glibc does for selecting an optimized memcpy implementation.)

But with static linking for a .a, just make function pointers that are statically initialized to the baseline versions, and your CPU init function (which hopefully runs before any of the function pointers are dereferenced) rewrites them to point at the best version for the current CPU.

Zarf

Thanks for the extra information about STT_GNU_IFUNC, and for the idea to use function pointers. Since you asked, I'm not actually using pdep or pext; I need BMI2 for the mulx instruction. Rather than having a special init function, I ended up using init_array (more information here: #31137760) to set up the function pointer before the main function executes. – Bossy

Answer 2

If you are using gcc, you can get the compiler to implement all the boiler plate code automatically. gcc manual page on function multiversioning

Skurnik