For SWAR algorithms, calculating floor(64/n) for 0 < n < 65 has always been crucial, so I spent a lot of time developing fast division algorithms. But since the Ryzen 7000 series, the fastest approach has been to simply cast 64/n to an integer.
I'm kind of sad that all those algorithms have become obsolete, but at the same time, I'm happy that integer division has finally become fast enough in hardware.
This looks very interesting, and very well written. I'll definitely give a it a thorough read when I get the time, and probably include the technique in our compiler. Floor division is almost always more useful than truncating division, so having a fast path there would be nice.
I can't help but do a shameless plug for another recent result in that space: we developed fast algorithms for 64-bit integer divisions (by constants and non-constants) for JavaScript, where you don't even have 64-bit integers to start with. Paper [1] and slides [2] available. The Scala.js compiler uses all of that. The Kotlin/JS compiler recently accepted my PR for the non-constant divisors algorithms.
I love to see this kind of optimization, of course, but there are other cases where Robison division is great, just because it has basically the same form for every divisor:
1. The divisor is not actually a compile-time constant, but comes from a small set. You can compute a table of corresponding constants and use the same code for every divisor.
2. You want to do many divisions by many different divisors (whether known at compile-time or drawn from a small set, like above, or pre-computable and applied many times... think of something like a quantization matrix for image coding, for example). Here Robison easily SIMDifies, whereas an algorithm that needs different code paths for every divisor is going to be much more difficult.
Regarding the lack of native signed-unsigned multiplies, as someone who does a lot of multimedia processing, I find the set of available multiplication instructions on x86 and ARM to be rather shamefully limited (especially x86). I recall a colleague who used to optimize for VideoCore (the GPU in a Raspberry Pi) saying that when he first started he was astounded that it had 80 different multiply instructions, but within a year or two he had used basically all of them.
Neat result, and good writeup! I don't have time to compare them, but another resource you might look at is Daniel Lemire's "Fast Division": https://github.com/lemire/fast_division
If you've come up with something better, I'd encourage you to contact Daniel and see if he's interested in helping you write it up into a paper. He's friendly, and may be better positioned to get the optimizations into mainstream compilers.
> As you can see, the technique is so simple that I'd expect that somebody has done this before, but I've looked around and not found it documented anywhere.
I'm one of those people I suppose. Yes, if you want to play with microoptimisations and part of a calculation are known, you can flip a division into a mult (and shift).
This might seem somewhat useless at first, but you can use this to e.g. speed up calculations in nested loops, where you can precompute this for relevant loop-layers.
Hello, you are correct that part of it is done to death for standard integer division.
The `new` thing is the range-splitting which achieves the floor division for negative inputs (eg. sign-selected for 60% of divisors, and the negative/positive bump for the remaining 20%/20% of cases each).
I found this by accident because I wanted to speed up a part on my Pebble watch face, I didn't even know the history of past attempts. The floor variant was born out of a particular rounding optimisation attempt that felt like it could be easier if I just use floor/ceil and moved it into a large int-multiplication space. (this is very tempting because certain constants for rendering and angle calculations are based around large integer constants on that platform, kinda doing half the work towards this idea by creating this particular constraint)
The mul-shift part is what any optimizing compiler does for known divisors and has done since the 90s, if anything it was more vital back then when the gap between div and mul was wider than today.
For SWAR algorithms, calculating floor(64/n) for 0 < n < 65 has always been crucial, so I spent a lot of time developing fast division algorithms. But since the Ryzen 7000 series, the fastest approach has been to simply cast 64/n to an integer.
I'm kind of sad that all those algorithms have become obsolete, but at the same time, I'm happy that integer division has finally become fast enough in hardware.
This looks very interesting, and very well written. I'll definitely give a it a thorough read when I get the time, and probably include the technique in our compiler. Floor division is almost always more useful than truncating division, so having a fast path there would be nice.
I can't help but do a shameless plug for another recent result in that space: we developed fast algorithms for 64-bit integer divisions (by constants and non-constants) for JavaScript, where you don't even have 64-bit integers to start with. Paper [1] and slides [2] available. The Scala.js compiler uses all of that. The Kotlin/JS compiler recently accepted my PR for the non-constant divisors algorithms.
[1] https://arith2026.org/papers/64-bit%20Integer%20Division%20f...
[2] https://arith2026.org/slides/session_1_2_doeraene.pdf
I love to see this kind of optimization, of course, but there are other cases where Robison division is great, just because it has basically the same form for every divisor:
1. The divisor is not actually a compile-time constant, but comes from a small set. You can compute a table of corresponding constants and use the same code for every divisor.
2. You want to do many divisions by many different divisors (whether known at compile-time or drawn from a small set, like above, or pre-computable and applied many times... think of something like a quantization matrix for image coding, for example). Here Robison easily SIMDifies, whereas an algorithm that needs different code paths for every divisor is going to be much more difficult.
Regarding the lack of native signed-unsigned multiplies, as someone who does a lot of multimedia processing, I find the set of available multiplication instructions on x86 and ARM to be rather shamefully limited (especially x86). I recall a colleague who used to optimize for VideoCore (the GPU in a Raspberry Pi) saying that when he first started he was astounded that it had 80 different multiply instructions, but within a year or two he had used basically all of them.
Neat result, and good writeup! I don't have time to compare them, but another resource you might look at is Daniel Lemire's "Fast Division": https://github.com/lemire/fast_division
If you've come up with something better, I'd encourage you to contact Daniel and see if he's interested in helping you write it up into a paper. He's friendly, and may be better positioned to get the optimizations into mainstream compilers.
> As you can see, the technique is so simple that I'd expect that somebody has done this before, but I've looked around and not found it documented anywhere.
I'm one of those people I suppose. Yes, if you want to play with microoptimisations and part of a calculation are known, you can flip a division into a mult (and shift).
This might seem somewhat useless at first, but you can use this to e.g. speed up calculations in nested loops, where you can precompute this for relevant loop-layers.
Hello, you are correct that part of it is done to death for standard integer division.
The `new` thing is the range-splitting which achieves the floor division for negative inputs (eg. sign-selected for 60% of divisors, and the negative/positive bump for the remaining 20%/20% of cases each).
I found this by accident because I wanted to speed up a part on my Pebble watch face, I didn't even know the history of past attempts. The floor variant was born out of a particular rounding optimisation attempt that felt like it could be easier if I just use floor/ceil and moved it into a large int-multiplication space. (this is very tempting because certain constants for rendering and angle calculations are based around large integer constants on that platform, kinda doing half the work towards this idea by creating this particular constraint)
The mul-shift part is what any optimizing compiler does for known divisors and has done since the 90s, if anything it was more vital back then when the gap between div and mul was wider than today.
I have great respect for those who conduct research on algorithm optimization.