5 ms·

I love these incomprehensible magic number optimizations. Every time I see one I wonder how many optimizations like this we missed back in the old days when we

I love these incomprehensible magic number optimizations. Every time I see one I wonder how many optimizations like this we missed back in the old days when we were writing all our inner loops in assembly? Does anyone have a collection of these things?

masfuerte 1y ago
We didn't miss them. In those days they weren't optimizations. Multiplications were really expensive.
- kurthr 1y ago
  and divides were worse. (1 cycle add, 10 cycle mult, 60 cycle div)
  - genewitch 1y ago
    That's fair but mod is division, or no? So realistically the new magic number version would be faster. Assuming there is 32 bit int support. Sorry, this is above my paygrade.
    - bobmcnamara 1y ago
      Many compiles will compute div-by-a-constant using the invert, multiply, and shift off the remainder trick. Once you have that, you can do mod-by-a-constant as a derivative and usually still beat 1-bit or 2-bit division.
  - qingcharles 1y ago
    Yeah, I'm thinking more of ones that remove all the divs from some crazy math functions for graphics rendering and replace them all with bit shifts or boolean ops.
  - ryao 1y ago
    Division still is worse: https://github.com/ridiculousfish/libdivide https://github.com/ridiculousfish/libdivide
- godelski 1y ago
  Related, Computerphile had a video a few months ago where they try to put compute time relative to human time, similar to the way one might visualize an atom by making the proton the size of a golfball. I think it can help put some costs into perspective and really show why branching maters as well as the great engineering done to hide some of the slowdowns. But definitely some things are being marked simply by the sheer speed of the clock (like how the small size of a proton hides how empty an atom is) https://youtube.com/watch?v=PpaQrzoDW2I
- deleted 1y ago
  [deleted]
- TacticalCoder 1y ago
  [dead]
- JdeBP 1y ago
  Multiplications of this word length, one should clarify. It's not that multiplication was an inherently more expensive or different operation back then (assuming from context here that the "old days" of coding inner loops in assembly language pre-date even the 32-bit ALU era). Binary multiplication has not changed in millennia. Ancient Egyptians were using the same binary integer multiplication logic 5 millennia ago as ALUs do today. It was that generally the fast hardware multiplication operations in ALUs didn't have very many bits in the register word length, so multiplications of wider words had to be done with library functions that did long multiplication in (say) base 256. So this code in the headlined article would not be "three instructions" but three calls to internal helper library functions used by the compiler for long-word multiplication, comparison, and bitwise AND; not markedly more optimal than three internal helper function calls for the three original modulo operations, and in fact less optimal than the bit-twiddled modulo-powers-of-2 version found halfway down the headlined article, which would only need check the least significant byte and not call library functions for two of the 32-bit modulo operations. Bonus points to anyone who remembers the helper function names in Microsoft BASIC's runtime library straight off the top of xyr head. It is probably a good thing that I finally seem to have forgotten them. (-: They all began with "B$" as I recall.
  - eru 1y ago
    > Multiplications of this word length, one should clarify. It's not that multiplication was an inherently more expensive or different operation back then (assuming from context here that the "old days" of coding inner loops in assembly language pre-date even the 32-bit ALU era). Binary multiplication has not changed in millennia. Ancient Egyptians were using the same binary integer multiplication logic 5 millennia ago as ALUs do today. Well, we can actually multiply long binary numbers asymptotically faster than Ancient Egyptians. See eg https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm
  - kruador 1y ago
    Most 8-bit CPUs didn't even have a hardware multiply instruction. To multiply on a 6502, for example, or a Z80, you have to add repeatedly. You can multiply by a power of 2 by shifting left, so you can get a bigger result by switching between shifting and adding or subtracting. Although, again, on these earlier CPUs you can only shift by one bit at a time, rather than by a variable number of bits. There's also the difference between multiplying by a hard-coded value, which can be implemented with shifts and adds, and multiplying two variables, which has to be done with an algorithm. The 8086 did have multiply instructions, but they were implemented as a loop in the microcode, adding the multiplicand, or not, once for each bit in the multiplier. More at https://www.righto.com/2023/03/8086-multiplication-microcode.html https://www.righto.com/2023/03/8086-multiplication-microcode.... Multiplying by a fixed value using shifts and adds could be faster. The prototype ARM1 did not have a multiply instruction. The architecture does have a barrel shifter which can shift one of the operands by any number of bits. For a fixed multiplication, it's possible to compute multiplying by a power of two, by (power of two plus 1), or by (power of two minus 1) in a single instruction. The latter is why ARM has both a SUB (subtract) instruction, computing rd := rs1 - Operand2, and a RSB (Reverse SuBtract) instruction, computing rd := Operand2 - rs1. The second operand goes through the barrel shifter, allowing you to write an instruction like 'RSB R0, R1, R1, #4' meaning 'R0 := (R1 << 4) - R1', or in other words '(R1 * 16) - R1', or R1 * 15. ARMv2 added in MUL and MLA (MuLtiply and Accumulate) instructions. The hardware ARM2 implementation uses a Booth's encoder to multiply 2 bits at a time, taking up to 16 cycles for 32 bits. It can exit early if the remaining bits are all 0s. Later ARM cores implemented an optional wider multiplier (that's the 'M' in 'ARM7TDMI', for example) that could multiply more bits at a time, therefore executing in fewer cycles. I believe ARM7TDMI was 8-bit, completing in up to 4 cycles (again, offering early exit). Modern ARM cores can do 64-bit multiplies in a single cycle.
- Someone 1y ago
  And branches were cheaper without pipelining
tylerhou 1y ago
You should look at supercompilation.
- mshockwave 1y ago
  sometimes also known as superoptimization, which many of them also use SMT solvers like Z3 mentioned in the article
  - tylerhou 1y ago
    Yes, sorry, superoptimization is the correct term.
owl_vision 1y ago
there is "Hacker's Delight" by Henry S. Warren, Jr. https://en.wikipedia.org/wiki/Hacker's_Delight https://en.wikipedia.org/wiki/Hacker's_Delight
- qingcharles 1y ago
  Looks awesome, thank you :)
ryao 1y ago
Here is a short list: https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html It is not on the list, but #define CMP(X, Y) (((X) > (Y)) - ((X) < (Y))) is an efficient way to do generic comparisons for things that want UNIX-style comparators. If you compare the output against 0 to check for some form of greater than, less than or equality, the compiler should automatically simplify it. For example, CMP(X, Y) > 0 is simplified to (X > Y) by a compiler. The signum(x) function that is equivalent to CMP(X, 0) can be done in 3 or 4 instructions depending on your architecture without any comparison operations: https://www.cs.cornell.edu/courses/cs6120/2022sp/blog/superoptimizer/ https://www.cs.cornell.edu/courses/cs6120/2022sp/blog/supero... It is such a famous example, that compilers probably optimize CMP(X, 0) to that, but I have not checked. Coincidentally, the expansion of CMP(X, 0) is on the bit hacks list. There are a few more superoptimized mathematical operations listed here: https://www2.cs.arizona.edu/~collberg/Teaching/553/2011/Resources/jay-slides.pdf https://www2.cs.arizona.edu/~collberg/Teaching/553/2011/Reso... Note that the assembly code appears to be for the Motorola 68000 processor and it makes use of flags that are set in edge cases to work. Finally, there is a list of helpful macros for bit operations that originated in OpenSolaris (as far as I know) here: https://github.com/freebsd/freebsd-src/blob/master/sys/cddl/contrib/opensolaris/uts/common/sys/sysmacros.h#L236 https://github.com/freebsd/freebsd-src/blob/master/sys/cddl/... There used to be an Open Solaris blog post on them, but Oracle has taken it down. Enjoy!
- JdeBP 1y ago
  For an entire book on this stuff, see Henry S. Warren Jr's Hackers Delight. The "three valued compare function" is in chapter 2, for example.
- eru 1y ago
  > It is not on the list, but #define CMP(X, Y) (((X) > (Y)) - ((X) < (Y))) is an efficient way to do generic comparisons for things that want UNIX-style comparators. If you compare the output against 0 to check for some form of greater than, less than or equality, the compiler should automatically simplify it. For example, CMP(X, Y) > 0 is simplified to (X > Y) by a compiler. I guess this only applies when the compiler knows what version of > you are using? Eg it might not work in C++ when < and > are overloaded for eg strings?

masfuerte 1y ago

We didn't miss them. In those days they weren't optimizations. Multiplications were really expensive.

kurthr 1y ago
and divides were worse. (1 cycle add, 10 cycle mult, 60 cycle div)
- genewitch 1y ago
  That's fair but mod is division, or no? So realistically the new magic number version would be faster. Assuming there is 32 bit int support. Sorry, this is above my paygrade.
  - bobmcnamara 1y ago
    Many compiles will compute div-by-a-constant using the invert, multiply, and shift off the remainder trick. Once you have that, you can do mod-by-a-constant as a derivative and usually still beat 1-bit or 2-bit division.
- qingcharles 1y ago
  Yeah, I'm thinking more of ones that remove all the divs from some crazy math functions for graphics rendering and replace them all with bit shifts or boolean ops.
- ryao 1y ago
  Division still is worse: https://github.com/ridiculousfish/libdivide https://github.com/ridiculousfish/libdivide
godelski 1y ago
Related, Computerphile had a video a few months ago where they try to put compute time relative to human time, similar to the way one might visualize an atom by making the proton the size of a golfball. I think it can help put some costs into perspective and really show why branching maters as well as the great engineering done to hide some of the slowdowns. But definitely some things are being marked simply by the sheer speed of the clock (like how the small size of a proton hides how empty an atom is) https://youtube.com/watch?v=PpaQrzoDW2I
deleted 1y ago
[deleted]
TacticalCoder 1y ago
[dead]
JdeBP 1y ago
Multiplications of this word length, one should clarify. It's not that multiplication was an inherently more expensive or different operation back then (assuming from context here that the "old days" of coding inner loops in assembly language pre-date even the 32-bit ALU era). Binary multiplication has not changed in millennia. Ancient Egyptians were using the same binary integer multiplication logic 5 millennia ago as ALUs do today. It was that generally the fast hardware multiplication operations in ALUs didn't have very many bits in the register word length, so multiplications of wider words had to be done with library functions that did long multiplication in (say) base 256. So this code in the headlined article would not be "three instructions" but three calls to internal helper library functions used by the compiler for long-word multiplication, comparison, and bitwise AND; not markedly more optimal than three internal helper function calls for the three original modulo operations, and in fact less optimal than the bit-twiddled modulo-powers-of-2 version found halfway down the headlined article, which would only need check the least significant byte and not call library functions for two of the 32-bit modulo operations. Bonus points to anyone who remembers the helper function names in Microsoft BASIC's runtime library straight off the top of xyr head. It is probably a good thing that I finally seem to have forgotten them. (-: They all began with "B$" as I recall.
- eru 1y ago
  > Multiplications of this word length, one should clarify. It's not that multiplication was an inherently more expensive or different operation back then (assuming from context here that the "old days" of coding inner loops in assembly language pre-date even the 32-bit ALU era). Binary multiplication has not changed in millennia. Ancient Egyptians were using the same binary integer multiplication logic 5 millennia ago as ALUs do today. Well, we can actually multiply long binary numbers asymptotically faster than Ancient Egyptians. See eg https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm
- kruador 1y ago
  Most 8-bit CPUs didn't even have a hardware multiply instruction. To multiply on a 6502, for example, or a Z80, you have to add repeatedly. You can multiply by a power of 2 by shifting left, so you can get a bigger result by switching between shifting and adding or subtracting. Although, again, on these earlier CPUs you can only shift by one bit at a time, rather than by a variable number of bits. There's also the difference between multiplying by a hard-coded value, which can be implemented with shifts and adds, and multiplying two variables, which has to be done with an algorithm. The 8086 did have multiply instructions, but they were implemented as a loop in the microcode, adding the multiplicand, or not, once for each bit in the multiplier. More at https://www.righto.com/2023/03/8086-multiplication-microcode.html https://www.righto.com/2023/03/8086-multiplication-microcode.... Multiplying by a fixed value using shifts and adds could be faster. The prototype ARM1 did not have a multiply instruction. The architecture does have a barrel shifter which can shift one of the operands by any number of bits. For a fixed multiplication, it's possible to compute multiplying by a power of two, by (power of two plus 1), or by (power of two minus 1) in a single instruction. The latter is why ARM has both a SUB (subtract) instruction, computing rd := rs1 - Operand2, and a RSB (Reverse SuBtract) instruction, computing rd := Operand2 - rs1. The second operand goes through the barrel shifter, allowing you to write an instruction like 'RSB R0, R1, R1, #4' meaning 'R0 := (R1 << 4) - R1', or in other words '(R1 * 16) - R1', or R1 * 15. ARMv2 added in MUL and MLA (MuLtiply and Accumulate) instructions. The hardware ARM2 implementation uses a Booth's encoder to multiply 2 bits at a time, taking up to 16 cycles for 32 bits. It can exit early if the remaining bits are all 0s. Later ARM cores implemented an optional wider multiplier (that's the 'M' in 'ARM7TDMI', for example) that could multiply more bits at a time, therefore executing in fewer cycles. I believe ARM7TDMI was 8-bit, completing in up to 4 cycles (again, offering early exit). Modern ARM cores can do 64-bit multiplies in a single cycle.
Someone 1y ago
And branches were cheaper without pipelining

tylerhou 1y ago

You should look at supercompilation.

mshockwave 1y ago
sometimes also known as superoptimization, which many of them also use SMT solvers like Z3 mentioned in the article
- tylerhou 1y ago
  Yes, sorry, superoptimization is the correct term.

owl_vision 1y ago

there is "Hacker's Delight" by Henry S. Warren, Jr. https://en.wikipedia.org/wiki/Hacker's_Delight https://en.wikipedia.org/wiki/Hacker's_Delight

qingcharles 1y ago
Looks awesome, thank you :)

ryao 1y ago

Here is a short list: https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html It is not on the list, but #define CMP(X, Y) (((X) > (Y)) - ((X) < (Y))) is an efficient way to do generic comparisons for things that want UNIX-style comparators. If you compare the output against 0 to check for some form of greater than, less than or equality, the compiler should automatically simplify it. For example, CMP(X, Y) > 0 is simplified to (X > Y) by a compiler. The signum(x) function that is equivalent to CMP(X, 0) can be done in 3 or 4 instructions depending on your architecture without any comparison operations: https://www.cs.cornell.edu/courses/cs6120/2022sp/blog/superoptimizer/ https://www.cs.cornell.edu/courses/cs6120/2022sp/blog/supero... It is such a famous example, that compilers probably optimize CMP(X, 0) to that, but I have not checked. Coincidentally, the expansion of CMP(X, 0) is on the bit hacks list. There are a few more superoptimized mathematical operations listed here: https://www2.cs.arizona.edu/~collberg/Teaching/553/2011/Resources/jay-slides.pdf https://www2.cs.arizona.edu/~collberg/Teaching/553/2011/Reso... Note that the assembly code appears to be for the Motorola 68000 processor and it makes use of flags that are set in edge cases to work. Finally, there is a list of helpful macros for bit operations that originated in OpenSolaris (as far as I know) here: https://github.com/freebsd/freebsd-src/blob/master/sys/cddl/contrib/opensolaris/uts/common/sys/sysmacros.h#L236 https://github.com/freebsd/freebsd-src/blob/master/sys/cddl/... There used to be an Open Solaris blog post on them, but Oracle has taken it down. Enjoy!

JdeBP 1y ago
For an entire book on this stuff, see Henry S. Warren Jr's Hackers Delight. The "three valued compare function" is in chapter 2, for example.
eru 1y ago
> It is not on the list, but #define CMP(X, Y) (((X) > (Y)) - ((X) < (Y))) is an efficient way to do generic comparisons for things that want UNIX-style comparators. If you compare the output against 0 to check for some form of greater than, less than or equality, the compiler should automatically simplify it. For example, CMP(X, Y) > 0 is simplified to (X > Y) by a compiler. I guess this only applies when the compiler knows what version of > you are using? Eg it might not work in C++ when < and > are overloaded for eg strings?