Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Unsigned comparisons in AVX2/SSE: a quick note

outerproduct.net

Post reply on HN
Print view View original

11–20 of 21 posts

Re: Unsigned comparisons in AVX2/SSE: a quick note

#11

Post by Const-me »

sylware wrote: post #9
Const-me wrote: post #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 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 t…

I think the compiler tricks are reasonably transparent to any developer who knows both C and assembly, thanks to godbolt.org.

Couple times I even back-ported these tricks from clang-generated assembly back into C++ intrinsics.

Re: Unsigned comparisons in AVX2/SSE: a quick note

#12

Post by anonymoushn »

Const-me wrote: post #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 t…

> Yeah, but if you need to compare for a 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.

Re: Unsigned comparisons in AVX2/SSE: a quick note

#13

Post by pjungwir »

sylware wrote: post #9
Const-me wrote: post #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 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 t…

If you're interested in this, Hacker's Delight has several hundreds of pages of these tricks. The book picks up from a 1972 MIT memo called HAKMEM. For a database/web guy like me, reading it is just recreational, but that's probably true for most people here. I'm currently about halfway through one hundred pages on how to divide. :-)

Re: Unsigned comparisons in AVX2/SSE: a quick note

#14

Post by Const-me »

pjungwir wrote: post #13
sylware wrote: post #9

Earlier quoted context omitted.

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 t…

If you're interested in this, Hacker's Delight has several hundreds of pages of these tricks. The book picks up from a 1972 MIT memo called HAKMEM. For a database/web guy like me, reading it is just recreational, but that's probably true for most people here. I'm currently about halfway through one hundred pages on how to divide. :-)

I sometimes write optimized low-level code, but many of these books, and internet articles, are rather old. CPU architectures have converted to just two, AMD64 and ARM64. They have tons of useful instructions like sign extension and integer division.

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.

Re: Unsigned comparisons in AVX2/SSE: a quick note

#15

Post by vardump »

Const-me wrote: post #10
vardump wrote: post #8

Earlier quoted context omitted.

> 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.

That'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.

Re: Unsigned comparisons in AVX2/SSE: a quick note

#16

Post by janwas »

sylware wrote: post #9
Const-me wrote: post #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 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 t…

github.com/google/highway is arguably such a collection of tricks, the x86_256-inl.h header does emulate some missing AVX-512 instructions such as this one or compressstoreu. (In this case we currently use a constant.)

Re: Unsigned comparisons in AVX2/SSE: a quick note

#17

Post by muziq »

Const-me wrote: post #14
pjungwir wrote: post #13

Earlier quoted context omitted.

If you're interested in this, Hacker's Delight has several hundreds of pages of these tricks. The book picks up from a 1972 MIT memo called HAKMEM. For a database/web guy like me, reading it is just recreational, but that's probably true for most people here. I'm currently about halfway through one hundred pages on how to divide. :-)

I sometimes write optimized low-level code, but many of these books, and internet articles, are rather old. CPU architectures have converted to just two, AMD64 and ARM64. They have tons of useful instructions like sign extension and integer division. 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 BL…

If you’re not dividing greater than 2^23 numbers then can’t you just use the FP divide ? I’m sure I’ve done this in CUDA many years back.. Worked a treat :) If you are then you have my sympathies..

Re: Unsigned comparisons in AVX2/SSE: a quick note

#18

Post by moonchild »

Const-me wrote: post #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 t…

> if you need to compare for a 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.

Re: Unsigned comparisons in AVX2/SSE: a quick note

#19

Post by Const-me »

muziq wrote: post #17
Const-me wrote: post #14

Earlier quoted context omitted.

I sometimes write optimized low-level code, but many of these books, and internet articles, are rather old. CPU architectures have converted to just two, AMD64 and ARM64. They have tons of useful instructions like sign extension and integer division. 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 BL…

If you’re not dividing greater than 2^23 numbers then can’t you just use the FP divide ? I’m sure I’ve done this in CUDA many years back.. Worked a treat :) If you are then you have my sympathies..

That’s often a good way, but not necessarily the best one. On my computer with Zen3 CPU, cvtdq2ps and cvttps2dq have 3 cycles of latency each, divps up to 10 cycles, results in 16 CPU cycles in total.

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

Re: Unsigned comparisons in AVX2/SSE: a quick note

#20

Post by Const-me »

vardump wrote: post #15
Const-me wrote: post #10

Earlier quoted context omitted.

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.

That'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.

Zen 2 cores have 4 execution units which run arithmetical and logical SIMD instructions: 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.

Post reply on HN