5 ms·

Round a direction vector to an 8-way compass

64 points by greghn 4y ago

thexa4 4y ago
Taking the dot product of the [x,y] with the 8 directions and picking the one with the largest magnitude might be faster in some cases.
- rocqua 4y ago
  You only need 4 directions, and can look at the sign of the dot-product.
- tgv 4y ago
  Good idea. Only four inproducts and comparisons are needed: the other four have the same value, but negated. Might be SIMD-able.
  - Someone 4y ago
    I was thinking about a more complicated approach (edit2: that ends up simpler). A 4-way version of this can be done with two comparisons (if x > y to check on what side of one diagonal the point lies and if x > -y to check the same for the other diagonal, plus some bit twiddling to get the required two bits out). One can do that, rotate by 45 degrees, do that again, and do some further bit manipulation to combine the two bits of the first 4-way version with those of the second into the three bits this should produce. That would be four comparisons, a 2×2 matrix multiplication (edit: that’s a matrix-vector multiplication) with a known-ahead rotation matrix (naively, that would be 8 (edit: 4) multiplications and 4 (edit: 2) additions, but I think we can lose those multiplications because all elements of a 45 degree rotation matrix have absolute value 1/√2 and the problem is scale-invariant) and some bit twiddling. Now, make that branchless… Edit2: and of course, you can do both splits into quadrants by just looking at the signs of x and y. That rotates the four quadrants by 45 degrees, but that doesn’t matter. That makes the 4-way version simply (x>0) + 2 × (y>0): two comparisons and a bit shift. twoBits = (x > 0) + 2 × (y > 0) x’ = x + y y’ = x - y twoMoreBits = (x’ > 0) + 2 × (y’ > 0) (Some bit twiddling with ‘twoBits’ and ‘twoMoreBits’ Feel free to compute those bit pairs differently if it makes the bit twiddling easier)
RicoElectrico 4y ago
I wonder if some amount of hysteresis would be helpful to avoid switching back and forth on the edge.
- ChrisLomont 4y ago
  Button debouncing is useful for all sorts of stuff like this, but it requires much trickier code to get right, including tracking some form of history.
iainmerrick 4y ago
What’s the motivation for optimising this? If it’s for user input, you only need to call this once per frame (or at most a few times).
- beckingz 4y ago
  faster parsing of user input means more time for doing graphics and game state! Though in this case 1.5 nanoseconds vs 40 nanoseconds is small and won't matter for most games.
- Cthulhu_ 4y ago
  More faster is more better; you only have 16 milliseconds per tick assuming you want to read input 60 times a second, some games poll even faster / have a higher frame rate.
  - nmilo 4y ago
    It's still a difference of 38.5 nano seconds. You have a budget 16,000,000 nanoseconds per frame. It's like Jeff Bezos writing about how to save money at Walmart; just pick the readable and stupid approach and move on. Game loops are made fast or slow by the efficiency of their tight loops: the render loop, physics update loop, UI loop, etc. Something that happens once per frame is barely ever worth considering.
    - GeoKureli 4y ago
      Agreed, 35ns x4 times per frame is less important than readability.
  - sgtnoodle 4y ago
    Ok, but 40ns of 16ms is 0.00025% of your frame time.
- dahart 4y ago
  It doesn’t matter for user input, the 40ns won’t make a difference even at 60fps or higher with 4 players. (Have written the controller processing loop for a console game engine.) I suspect it would be less than 40ns if float was used instead of double; there’s no good reason to use double here at all. But the proposed solution is better, and super easy (arguably easier than atan2+sincos), so maybe no reason not to use it a save a few microseconds if it happens to add up to that much. I could imagine other uses of this code, like a UI wind map, or some kind of randomized maze, or something else. There might be reasons to round a vector of directions all at once.
jameshart 4y ago
Seems to rest on the assumption that an input control provides a vector on the unit circle, and tries to divide that into eight regions, corresponding to unit vectors aligned to compass directions. That seems like an odd assumption though - most analog XY inputs produce a vector with x and y components nominally distributed from -1 to 1, (although in practice constrained by calibration, and not necessarily linear in control stick deflection) This approach effectively divides the ‘unit square’ of possible input vectors up into a grid, based on cos(pi/8) and cos(3pi/8) gridlines, with basically 9 possible areas in each quadrant mapped to corresponding directional vectors. It may not be a bad strategy in general to use this kind of grid model, but it needs testing with actual controllers to see what the ‘feel’ ends up being. While this mathematical model makes sense in theory, in practice there’s no reason to suspect that these cosine values are necessarily good thresholds to use to create an intuitive compass direction control that actually feels intuitive. In general in games, math needs to be a guide, but not a straitjacket for how you approach things.
- dahart 4y ago
  This is a good point; some controllers are neither circular nor square. Check out the mapping ranges for a couple of Nintendo’s old controllers: https://electromodder.co.uk/ https://electromodder.co.uk/ That said, Lemire’s approach rewritten as dot products might work nicely and even look a bit more clean, even if it took 3ns instead of 1.5.
  - Arrath 4y ago
    > This is a good point; some controllers are neither circular nor square. Check out the mapping ranges for a couple of Nintendo’s old controllers: https://electromodder.co.uk/ https://electromodder.co.uk/ Very interesting, thanks! I've noticed myself that sometimes if I'm holding the controller a bit skewed my natural impulse will be to push in directions that don't exactly map to what the controller wants. EG I think I'm pushing forward, but I'm moving forward and slightly to the left. And its not just stick drift, its my own user error.
    - 4y ago
dahart 4y ago
Is the problem with the sin/cos approach that it’s using double precision? That’s surely completely unnecessary precision. These days I don’t know what happens in x86 land with sin & cos, but on a gaming GPU the fp32 cosf() is typically 16 or 32 times faster than fp64 cos(). Is that true on CPUs too? (I’m sure the simple proposed solution is always faster even in fp32, I’m just curious if the gap is much narrower, smaller than 25x.)
- hansvm 4y ago
  The precision doesn't matter much on the CPU (roughly half the throughout if you're doing a lot of them). You have a data dependency on the arctangent, and transcendentals are slow anyway, so you're not going to have a good time. You can even compute the sin and cos together and still expect a bare minimum latency of 50 clock cycles for the arctangent followed by 50 for the sincos, usually implemented with a variable speed algorithm that might be slower (i.e., lower bound of 30ns of latency on a moderately fast single core, just for the trig). Throughput can be a bit higher with vectorization and pipelining, but more or less any such optimization you can make to the transcendentals you can also make on the proposed solution.
  - dahart 4y ago
    Thanks, good to know! So that does suggest to me that if there are other threads in progress, the actual impact to the runtime in practice probably would be lower with fp32 - the half throughput rate does tell us how long we wait for any instructions dependent on the operation, right? I’m saying I suspect the total latency can be filled with other work, so this isn’t really 40ns that is fully devoted to atan2+sincos and nothing else. Is that accurate? (On the GPUs I use, trig functions use a different math pipe than FMA, and so they can be ‘free’ if you don’t use too many of them and there is enough logic or FMA to hide the trig latency.) Aren’t the benefits of using fp32 bigger than the trig instruction throughput too? Doubles eat more register space, and double the bandwidth to memory if anything ends up in memory. I just don’t see any reason whatsoever to use doubles for this operation. If we’re going to worry about nanoseconds, then these extra bytes matter too, no?
jansan 4y ago
Two more optimizations: - Use else if to avoid uncessary condition checking. - Only check for xneg / yneg if outx / outy are non-zero.
- WithinReason 4y ago
  Would else if be actually faster on a modern CPU architecture?
  - pklausler 4y ago
    Only measurement with real data would tell for sure, but I would bet "yes" if I had to. With the "else", the "if" predicate is being predicted over a smaller amount of relevant cases; without the "else", the prediction is going to have to cope with some amount of needless false results and is likely to be less accurate.
- dundarious 4y ago
  Almost certainly makes it worse to add additional conditional dependencies, meaning branches upon branches. Some examples: 1. Branches with dependencies. static void minMax(u8* pxmin, u8* pxmax, const u8* xs, size_t n) { const u8 init = n > 0u ? xs[0] : (u8)0u; u8 xmin = init u8 xmax = init; for (size_t i = 1u; i < n; ++i) { const u8 x = xs[i]; if (x < xmin) { xmin = x; } else if (x > xmax) { xmax = x; } } *pxmin = xmin; *pxmax = xmax; } 2. Branches w/o dependencies static void minMax(u8* pxmin, u8* pxmax, const u8* xs, size_t n) { const u8 init = n > 0u ? xs[0] : (u8)0u; u8 xmin = init u8 xmax = init; for (size_t i = 1u; i < n; ++i) { const u8 x = xs[i]; if (x < xmin) { xmin = x; } if (x > xmax) { xmax = x; } /*not doing else if*/ } *pxmin = xmin; *pxmax = xmax; } Compiling with auto-vectorization enabled (-O3 for most versions of GCC, and I was using -march=native on a Zen1 AMD CPU, so AVX2 capable), version 2 is 0.05x the runtime of the version 1 (so a lot faster). Version 2 disassembly will show lots of “packed” vector instructions. 3. Branchless inline u8 minBranchless(u8 x, u8 y) { return x * (u8)(x <= y ? 1u : 0u) + y * (u8)(x > y ? 1u : 0u); } inline u8 maxBranchless(u8 x, u8 y) { return x * (u8)(x >= y ? 1u : 0u) + y * (u8)(x < y ? 1u : 0u); } static void minMax(u8* pxmin, u8* pxmax, const u8* xs, size_t n) { const u8 init = n > 0u ? xs[0] : (u8)0u; u8 xmin = init u8 xmax = init; for (size_t i = 1u; i < n; ++i) { const u8 x = xs[i]; xmin = minBranchless(xmin, x); xmax = maxBranchless(xmax, x); } *pxmin = xmin; *pxmax = xmax; } Version 3 is probably a better comparison for the code from the article — there are only 1 or 2 joystick direction vectors that need normalization, so perhaps not enough to show major vectorization benefit, or to even prompt compiler auto-vectorization. Version 3 will most likely be compiled into cmov instructions on x86_64, which are branchless, but branches can still be better, if they can be predicted well. The test data I used was random, so cmov should be expected to be beneficial. Last time I ran comparisons, Version 2 was 0.07x the runtime of Version 3, so Version 3 was not that much faster than Version 1, but still a good improvement. As a final note, I should say I’m not a fan of relying on compiler auto-vectorization. If you depend on the performance of vectorized code (and vectorizing code is one of the best optimizations out there), then I’m a fan of explicitly vectorizing. SSE2 is in nearly 100% of relevant x86_64 systems (first coming out in 2003). If you’re targeting consumers, AVX is almost certainly worth it. If you’re writing server code, you should be taking full advantage of AVX2 and maybe 512. For arm, NEON is the current vector extension of relevance, and you can polyfill with DLTcollab/sse2neon or something like that, until you go native. Writing vectorized code using SIMD intrinsics (#include <immintrin.h>) is preferable. Especially since compilers just cannot know how to auto-vectorize a lot of floating point code, because of strict assumptions about requirements around non-commutativity, so they almost never generate packed FMADDs. As for the article code, I wouldn’t make any assumptions about whether the compiler is generating branches or cmov-s. I’d guess cmov-s would be faster, but I haven’t really thought about it. All I’ll say is that turning a lot of `if`s into `else if`s would make it impossible to generate cmov-s, and chaining branches just to avoid assigning to a local that’s almost certainly in a register is only going to make branching slower.
phkahler 4y ago
It may be useful to read about the CORDIC algorithms. It just feels like there is an even simpler solution lurking here: https://en.wikipedia.org/wiki/CORDIC https://en.wikipedia.org/wiki/CORDIC
moralestapia 4y ago
This but in a 2-sphere space is what I need right now for a quantum computing simulator I'm coding for fun/learning. I'm doing a different thing tho, dot product vs. four cardinal points.
bee_rider 4y ago
Is it possible to just ask... xinput or whatever joystick driver is used nowadays... to produce the cardinal or 8-compass directions? I guess it seems plausible, at least, that maybe for some controllers we could skip the whole conversion to/from a pair of floats thing, depending on what signals are sent down the USB pipe.

64 points by greghn 4y ago

Taking the dot product of the [x,y] with the 8 directions and picking the one with the largest magnitude might be faster in some cases.

rocqua 4y ago
You only need 4 directions, and can look at the sign of the dot-product.
tgv 4y ago
Good idea. Only four inproducts and comparisons are needed: the other four have the same value, but negated. Might be SIMD-able.
- Someone 4y ago
  I was thinking about a more complicated approach (edit2: that ends up simpler). A 4-way version of this can be done with two comparisons (if x > y to check on what side of one diagonal the point lies and if x > -y to check the same for the other diagonal, plus some bit twiddling to get the required two bits out). One can do that, rotate by 45 degrees, do that again, and do some further bit manipulation to combine the two bits of the first 4-way version with those of the second into the three bits this should produce. That would be four comparisons, a 2×2 matrix multiplication (edit: that’s a matrix-vector multiplication) with a known-ahead rotation matrix (naively, that would be 8 (edit: 4) multiplications and 4 (edit: 2) additions, but I think we can lose those multiplications because all elements of a 45 degree rotation matrix have absolute value 1/√2 and the problem is scale-invariant) and some bit twiddling. Now, make that branchless… Edit2: and of course, you can do both splits into quadrants by just looking at the signs of x and y. That rotates the four quadrants by 45 degrees, but that doesn’t matter. That makes the 4-way version simply (x>0) + 2 × (y>0): two comparisons and a bit shift. twoBits = (x > 0) + 2 × (y > 0) x’ = x + y y’ = x - y twoMoreBits = (x’ > 0) + 2 × (y’ > 0) (Some bit twiddling with ‘twoBits’ and ‘twoMoreBits’ Feel free to compute those bit pairs differently if it makes the bit twiddling easier)

RicoElectrico 4y ago

I wonder if some amount of hysteresis would be helpful to avoid switching back and forth on the edge.

ChrisLomont 4y ago
Button debouncing is useful for all sorts of stuff like this, but it requires much trickier code to get right, including tracking some form of history.

iainmerrick 4y ago

What’s the motivation for optimising this? If it’s for user input, you only need to call this once per frame (or at most a few times).

beckingz 4y ago
faster parsing of user input means more time for doing graphics and game state! Though in this case 1.5 nanoseconds vs 40 nanoseconds is small and won't matter for most games.
Cthulhu_ 4y ago
More faster is more better; you only have 16 milliseconds per tick assuming you want to read input 60 times a second, some games poll even faster / have a higher frame rate.
- nmilo 4y ago
  It's still a difference of 38.5 nano seconds. You have a budget 16,000,000 nanoseconds per frame. It's like Jeff Bezos writing about how to save money at Walmart; just pick the readable and stupid approach and move on. Game loops are made fast or slow by the efficiency of their tight loops: the render loop, physics update loop, UI loop, etc. Something that happens once per frame is barely ever worth considering.
  - GeoKureli 4y ago
    Agreed, 35ns x4 times per frame is less important than readability.
- sgtnoodle 4y ago
  Ok, but 40ns of 16ms is 0.00025% of your frame time.
dahart 4y ago
It doesn’t matter for user input, the 40ns won’t make a difference even at 60fps or higher with 4 players. (Have written the controller processing loop for a console game engine.) I suspect it would be less than 40ns if float was used instead of double; there’s no good reason to use double here at all. But the proposed solution is better, and super easy (arguably easier than atan2+sincos), so maybe no reason not to use it a save a few microseconds if it happens to add up to that much. I could imagine other uses of this code, like a UI wind map, or some kind of randomized maze, or something else. There might be reasons to round a vector of directions all at once.

jameshart 4y ago

Seems to rest on the assumption that an input control provides a vector on the unit circle, and tries to divide that into eight regions, corresponding to unit vectors aligned to compass directions. That seems like an odd assumption though - most analog XY inputs produce a vector with x and y components nominally distributed from -1 to 1, (although in practice constrained by calibration, and not necessarily linear in control stick deflection) This approach effectively divides the ‘unit square’ of possible input vectors up into a grid, based on cos(pi/8) and cos(3pi/8) gridlines, with basically 9 possible areas in each quadrant mapped to corresponding directional vectors. It may not be a bad strategy in general to use this kind of grid model, but it needs testing with actual controllers to see what the ‘feel’ ends up being. While this mathematical model makes sense in theory, in practice there’s no reason to suspect that these cosine values are necessarily good thresholds to use to create an intuitive compass direction control that actually feels intuitive. In general in games, math needs to be a guide, but not a straitjacket for how you approach things.

dahart 4y ago
This is a good point; some controllers are neither circular nor square. Check out the mapping ranges for a couple of Nintendo’s old controllers: https://electromodder.co.uk/ https://electromodder.co.uk/ That said, Lemire’s approach rewritten as dot products might work nicely and even look a bit more clean, even if it took 3ns instead of 1.5.
- Arrath 4y ago
  > This is a good point; some controllers are neither circular nor square. Check out the mapping ranges for a couple of Nintendo’s old controllers: https://electromodder.co.uk/ https://electromodder.co.uk/ Very interesting, thanks! I've noticed myself that sometimes if I'm holding the controller a bit skewed my natural impulse will be to push in directions that don't exactly map to what the controller wants. EG I think I'm pushing forward, but I'm moving forward and slightly to the left. And its not just stick drift, its my own user error.
  - 4y ago

dahart 4y ago

Is the problem with the sin/cos approach that it’s using double precision? That’s surely completely unnecessary precision. These days I don’t know what happens in x86 land with sin & cos, but on a gaming GPU the fp32 cosf() is typically 16 or 32 times faster than fp64 cos(). Is that true on CPUs too? (I’m sure the simple proposed solution is always faster even in fp32, I’m just curious if the gap is much narrower, smaller than 25x.)

hansvm 4y ago
The precision doesn't matter much on the CPU (roughly half the throughout if you're doing a lot of them). You have a data dependency on the arctangent, and transcendentals are slow anyway, so you're not going to have a good time. You can even compute the sin and cos together and still expect a bare minimum latency of 50 clock cycles for the arctangent followed by 50 for the sincos, usually implemented with a variable speed algorithm that might be slower (i.e., lower bound of 30ns of latency on a moderately fast single core, just for the trig). Throughput can be a bit higher with vectorization and pipelining, but more or less any such optimization you can make to the transcendentals you can also make on the proposed solution.
- dahart 4y ago
  Thanks, good to know! So that does suggest to me that if there are other threads in progress, the actual impact to the runtime in practice probably would be lower with fp32 - the half throughput rate does tell us how long we wait for any instructions dependent on the operation, right? I’m saying I suspect the total latency can be filled with other work, so this isn’t really 40ns that is fully devoted to atan2+sincos and nothing else. Is that accurate? (On the GPUs I use, trig functions use a different math pipe than FMA, and so they can be ‘free’ if you don’t use too many of them and there is enough logic or FMA to hide the trig latency.) Aren’t the benefits of using fp32 bigger than the trig instruction throughput too? Doubles eat more register space, and double the bandwidth to memory if anything ends up in memory. I just don’t see any reason whatsoever to use doubles for this operation. If we’re going to worry about nanoseconds, then these extra bytes matter too, no?

jansan 4y ago

Two more optimizations: - Use else if to avoid uncessary condition checking. - Only check for xneg / yneg if outx / outy are non-zero.

WithinReason 4y ago
Would else if be actually faster on a modern CPU architecture?
- pklausler 4y ago
  Only measurement with real data would tell for sure, but I would bet "yes" if I had to. With the "else", the "if" predicate is being predicted over a smaller amount of relevant cases; without the "else", the prediction is going to have to cope with some amount of needless false results and is likely to be less accurate.
dundarious 4y ago
Almost certainly makes it worse to add additional conditional dependencies, meaning branches upon branches. Some examples: 1. Branches with dependencies. static void minMax(u8* pxmin, u8* pxmax, const u8* xs, size_t n) { const u8 init = n > 0u ? xs[0] : (u8)0u; u8 xmin = init u8 xmax = init; for (size_t i = 1u; i < n; ++i) { const u8 x = xs[i]; if (x < xmin) { xmin = x; } else if (x > xmax) { xmax = x; } } *pxmin = xmin; *pxmax = xmax; } 2. Branches w/o dependencies static void minMax(u8* pxmin, u8* pxmax, const u8* xs, size_t n) { const u8 init = n > 0u ? xs[0] : (u8)0u; u8 xmin = init u8 xmax = init; for (size_t i = 1u; i < n; ++i) { const u8 x = xs[i]; if (x < xmin) { xmin = x; } if (x > xmax) { xmax = x; } /*not doing else if*/ } *pxmin = xmin; *pxmax = xmax; } Compiling with auto-vectorization enabled (-O3 for most versions of GCC, and I was using -march=native on a Zen1 AMD CPU, so AVX2 capable), version 2 is 0.05x the runtime of the version 1 (so a lot faster). Version 2 disassembly will show lots of “packed” vector instructions. 3. Branchless inline u8 minBranchless(u8 x, u8 y) { return x * (u8)(x <= y ? 1u : 0u) + y * (u8)(x > y ? 1u : 0u); } inline u8 maxBranchless(u8 x, u8 y) { return x * (u8)(x >= y ? 1u : 0u) + y * (u8)(x < y ? 1u : 0u); } static void minMax(u8* pxmin, u8* pxmax, const u8* xs, size_t n) { const u8 init = n > 0u ? xs[0] : (u8)0u; u8 xmin = init u8 xmax = init; for (size_t i = 1u; i < n; ++i) { const u8 x = xs[i]; xmin = minBranchless(xmin, x); xmax = maxBranchless(xmax, x); } *pxmin = xmin; *pxmax = xmax; } Version 3 is probably a better comparison for the code from the article — there are only 1 or 2 joystick direction vectors that need normalization, so perhaps not enough to show major vectorization benefit, or to even prompt compiler auto-vectorization. Version 3 will most likely be compiled into cmov instructions on x86_64, which are branchless, but branches can still be better, if they can be predicted well. The test data I used was random, so cmov should be expected to be beneficial. Last time I ran comparisons, Version 2 was 0.07x the runtime of Version 3, so Version 3 was not that much faster than Version 1, but still a good improvement. As a final note, I should say I’m not a fan of relying on compiler auto-vectorization. If you depend on the performance of vectorized code (and vectorizing code is one of the best optimizations out there), then I’m a fan of explicitly vectorizing. SSE2 is in nearly 100% of relevant x86_64 systems (first coming out in 2003). If you’re targeting consumers, AVX is almost certainly worth it. If you’re writing server code, you should be taking full advantage of AVX2 and maybe 512. For arm, NEON is the current vector extension of relevance, and you can polyfill with DLTcollab/sse2neon or something like that, until you go native. Writing vectorized code using SIMD intrinsics (#include <immintrin.h>) is preferable. Especially since compilers just cannot know how to auto-vectorize a lot of floating point code, because of strict assumptions about requirements around non-commutativity, so they almost never generate packed FMADDs. As for the article code, I wouldn’t make any assumptions about whether the compiler is generating branches or cmov-s. I’d guess cmov-s would be faster, but I haven’t really thought about it. All I’ll say is that turning a lot of `if`s into `else if`s would make it impossible to generate cmov-s, and chaining branches just to avoid assigning to a local that’s almost certainly in a register is only going to make branching slower.

phkahler 4y ago

It may be useful to read about the CORDIC algorithms. It just feels like there is an even simpler solution lurking here: https://en.wikipedia.org/wiki/CORDIC https://en.wikipedia.org/wiki/CORDIC

moralestapia 4y ago

This but in a 2-sphere space is what I need right now for a quantum computing simulator I'm coding for fun/learning. I'm doing a different thing tho, dot product vs. four cardinal points.

bee_rider 4y ago

Is it possible to just ask... xinput or whatever joystick driver is used nowadays... to produce the cardinal or 8-compass directions? I guess it seems plausible, at least, that maybe for some controllers we could skip the whole conversion to/from a pair of floats thing, depending on what signals are sent down the USB pipe.