Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Choose assembly implementation to use based on supported instructions

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?

like image 590
Sam Kumar Avatar asked Nov 28 '18 02:11

Sam Kumar


2 Answers

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.

like image 121
Peter Cordes Avatar answered Oct 14 '22 05:10

Peter Cordes


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

like image 30
David Avatar answered Oct 14 '22 05:10

David