Unsigned comparisons in AVX2/SSE: a quick note
outerproduct.net
outerproduct.net
(and, for completeness, a regular C loop[1], with some massaging to make it more readable)
On many CPUs, bitwise XOR is slightly more efficient than addition. But you still need the magic number.
> and you are in a hostile environment, you will have to figure out how to load up a vector of 128s, which costs cycles
That particular vector can be generated with 2 instructions without RAM access, pcmpeqd to generate a vector with all bits set, and psllw/pslld for shifts.
Modern compilers support LTCG/LTO which optimizes code across translation units. If you have a loop comparing these vectors, the magic vector is likely to be created outside, and kept in a register.
> To avoid this, use min
Yeah, but if you need to compare for a < b as opposed to a <= b, you gonna need couple more instructions.
> if anyone working on superoptimisation has caught these?
Page #17 there: http://const.me/articles/simd/simd.pdf
That's pretty interesting, any examples of CPUs (or microcontrollers) where this happens?
BTW, Zen 2 CPUs are used in both Xbox S/X, and PS5.
Apparently 3 out of 4 units can add integers, but all 4 of them can do bitwise operations. Despite the ISA defines multiple equivalent bitwise instructions like pand / andps / andpd, apparently modern AMD CPUs don’t have a bypass delay so these instructions are 100% equivalent on these CPUs. And with some luck (when not bottlenecked on instruction fetch, decode, or other place in the pipeline) each Zen2 core can run 4 of them every cycle.
On a more global scale, all assembly "optimisations"/tricks are hidden deep into compilers, which are reasonably "transparent" to their devs only, that due to their abysmal complexity and size.
We would need some sort of online library for those assembly (boolean/branchless calculus...) tricks.
A job for wikipedia? Maybe linked to the maths/boolean calculus?
Couple times I even back-ported these tricks from clang-generated assembly back into C++ intrinsics.
They also have less trivial instructions equivalent to some of these tricks, only faster. Couple examples.
To turn off the rightmost 1-bit in a word, on AMD64 there’s BLSR instruction from BMI1 set.
ARM CPUs have a fast instruction to reverse bits. AMD64 do not, but they have a fast instruction to flip order of bytes allowing to reverse these bits faster than what’s in that book.
These tricks are only useful very rarely. For instance, SIMD instructions can’t divide vectors of integers. Some older GPUs can’t divide FP64 numbers but most of them can multiply FP64, and all of them can divide FP32. For these exotic use cases, these tricks are still relevant.
When the divisor’s the same for all lanes and known at compile time, there’re tricks to reduce division to a single integer multiplication, and a few extra cheap instructions like shifts and additions. Usually faster than 16 cycles. Here’s an example, automagically made by clang 13: https://godbolt.org/z/T4TKb7oov
In general yes. Depending on your use for the mask, it might be fine to compute !(a < b) == (b <= a) and use the mask with andnot.
Depends on what you are doing--you may not need to spend any extra ops at all. For instance, if you are blending then you can compute a >= b and commute the blend arguments. If you are branching, then you pick the complementary flag to branch on. Etc.
I would like to read more about superoptimizers targeting AVX2, since previously I've complained that gcc will not make transformations between various equivalent instruction sequences for moving bytes around within and between registers, and some of these are a lot slower than others.