5 ms·
Unsigned comparisons in AVX2/SSE: a quick note
- pyler 4y agoWhat gcc/clang does?
- deleted 4y ago[deleted]
- anonymoushn 4y agoI'm not working on superoptimization, but yes it does seem like eq(x,max_unsigned(x,y)) is an "obvious" cmpge_unsigned if one just browses all the intrinsics available here: https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html https://www.intel.com/content/www/us/en/docs/intrinsics-guid... 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.
- dzaima 4y agoFor what it's worth, clang[0] compiles to the vpminu[bwd] + vpcmpeq[bwd] version even from manually written intrinsics of the addition-based version, and has since clang 7. Though, interestingly enough, it fails to cancel out a following xor. (and, for completeness, a regular C loop[1], with some massaging to make it more readable) [0]: https://godbolt.org/z/e7TE5P73Y https://godbolt.org/z/e7TE5P73Y [1]: https://godbolt.org/z/xhj3WTnxv https://godbolt.org/z/xhj3WTnxv
- moonchild 4y agoThat's unfortunate. The solution with min actually does equal work in this case--it just has a lesser startup cost, hence my mention of a 'hostile environment'--but with greater span, because the high-bit toggling can be done for both inputs in parallel. If you switch to a loop, at the very least, it ought to use the traditional solution, but it doesn't. Also it doesn't use the trick with the saturating subtract. https://godbolt.org/z/76qKs49eW https://godbolt.org/z/76qKs49eW
- Const-me 4y ago> simply add 128 (or however much—depending on the sizes at hand) to each of your inputs before comparing 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 http://const.me/articles/simd/simd.pdf
- vardump 4y ago> On many CPUs, bitwise XOR is slightly more efficient than addition. That's pretty interesting, any examples of CPUs (or microcontrollers) where this happens?
- Const-me 4y agoAn example is AMD Zen 2. The latency of both vpaddd and vpxor is 1 cycle, but throughput is different, 0.33 versus 0.25 cycles. BTW, Zen 2 CPUs are used in both Xbox S/X, and PS5.
- vardump 4y agoThat's pretty interesting. So AMD has split traditional ALU to different execution units? I mean, usually same ALU(s) that got an adder has also logical ops.
- Const-me 4y agoZen 2 cores have 4 execution units which run arithmetical and logical SIMD instructions: https://en.wikichip.org/wiki/amd/microarchitectures/zen_2#Floating_Point_Unit https://en.wikichip.org/wiki/amd/microarchitectures/zen_2#Fl... 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.