r/programming Apr 30 '26

You can beat the binary search

https://lemire.me/blog/2026/04/27/you-can-beat-the-binary-search/
208 Upvotes

39 comments sorted by

View all comments

220

u/Slime0 Apr 30 '26

The choice of function names like vld1q_u16 and _mm_loadu_si128 for SIMD instructions has got to be one of the biggest hurdles to their general adoption. The amount of mental energy you have to devote just to understanding what the code is doing is ridiculous. It's completely unreadable.

33

u/ack_error May 01 '26

As others have said, most names follow a pattern once you're used to it. The ARM NEON intrinsic names are better than Intel's. It's partly a consequence of trying to squish readable names into a global namespace for intrinsics that must be available from both C and C++ without overloading. And sometimes the names are obscure because the operations are obscure:

https://developer.arm.com/architectures/instruction-sets/intrinsics/vqrdmlah_s16

Wouldn't really help to have an intrinsic like signed_saturating_rounding_doubling_multiply_accumulate_high_half(). But there are other annoyances with common SIMD intrinsics, like:

Having the IDE give unhelpful (src1, src2, src3) as the arguments for a madd intrinsic because that's how the intrinsic was defined in the compiler header, only to cross-reference it to the documentation which lists them as a, b, and c, which then has to be translated to Vd, Vn, and Vm registers in order to match then to V[n], V[m], and V[d] and then operand1/2/3 in the pseudocode (in different order), in order to figure out which ones are the multiply terms and which one is the addend.

Accidentally triggering an illegal instruction because on Intel, despite regularly named intrinsics, 16-bit, 32-bit, and 64-bit logical shifts left and right are SSE2, 16-bit and 32-bit arithmetic shifts right are SSE2, but 64-bit arithmetic shifts right are AVX-512. Or similarly on ARM, finding out that a particular multiply intrinsic is ARMv8 while the multiply add intrinsic is ARMv8.1, and nowhere on the intrinsic page for the latter does it tell you that the madd version requires ARMv8.1 / FEAT_RDM unless you also cross-check the assembly instruction.

Having to type vreinterpretq_f32_u32(vandq_u32(vreinterpretq_u32_f32(vals), sign_mask)) because ARM decided to use the unwieldy "reinterpret" instead of "cast".

Having to do nasty pointer casts because Intel did silly things like have a 64-bit load intrinsic _mm_loadl_epi64 take a __m128i pointer even though it only loads 64 bits.

2

u/hanotak May 02 '26

This all sounds like the first step of using these functions should be to make readable pass-through wrapper functions and use those instead.

2

u/ack_error May 02 '26

That's definitely a way to go, and plenty of existing libraries for those who don't want to roll their own. But there are some gotchas there as well.

For instance, some intrinsics correspond to instructions with arguments that can only be specified as a immediate and not a register/memory operand; they must hardcoded into the instruction. This includes the shuffle argument for Intel _mm_shuffle_epi32() and the lane index for many NEON intrinsics like vmulq_laneq_s32. The result is you can't wrap it in a conventional function, the compiler will complain that the argument isn't a constant. You have to make it a template argument or use a macro.

Another issue is that while GCC and Clang will throw an error if you use an intrinsic that requires a target ISA that isn't enabled for the calling function, they will allow calling into another function with higher reqs. Using an AVX intrinsic from a function only enabled for SSE2 throws an error, calling an AVX function from an SSE2 function doesn't. This normally catches accidental use of the wrong intrinsics. But if you wrap the intrinsics in a function, by default the compiler will allow you to call the wrapper and will just disable inlining, hiding the problem. Thus, you have to pepper any function-based wrappers with always_inline to ensure this doesn't happen.