Unsigned comparisons in AVX2/SSE: a quick note
outerproduct.net
Unsigned comparisons in AVX2/SSE: a quick note
1–10 of 21 posts
Re: Unsigned comparisons in AVX2/SSE: a quick note
#2What gcc/clang does?
Re: Unsigned comparisons in AVX2/SSE: a quick note
#3I'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-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.
Re: Unsigned comparisons in AVX2/SSE: a quick note
#4For 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)
Re: Unsigned comparisons in AVX2/SSE: a quick note
#5What gcc/clang does?
[deleted]
Re: Unsigned comparisons in AVX2/SSE: a quick note
#6For 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 [1]: https://godbolt.org/z/xhj3WTnxv
That'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
Re: Unsigned comparisons in AVX2/SSE: a quick note
#7> 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 > if anyone working on superoptimisation has caught these?
Page #17 there: http://const.me/articles/simd/simd.pdf
Re: Unsigned comparisons in AVX2/SSE: a quick note
#8> 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 t…
> On many CPUs, bitwise XOR is slightly more efficient than addition.
That's pretty interesting, any examples of CPUs (or microcontrollers) where this happens?
Re: Unsigned comparisons in AVX2/SSE: a quick note
#9> 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 t…
Yep, some constants are better to be generated than loaded, see the docs from Mr. Agner.
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?
Re: Unsigned comparisons in AVX2/SSE: a quick note
#10> 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 t…
> On many CPUs, bitwise XOR is slightly more efficient than addition. That's pretty interesting, any examples of CPUs (or microcontrollers) where this happens?
An 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.