On Wednesday, 1 March 2017 at 06:44:34 UTC, Cecil Ward wrote:
I liked that article. I didn't really understand the point
about implementation of modulo primes, maybe I missed
something. Given that our man is doing modulo a 'known' value
(he had a switch statement to get to them), why not do
something rather cheaper than a compiler-expanded constant
div/mod made up of multiplies and shifts
const uint power2 = 512; // say, some 1 << n anyway
const uint prime = 509; // some prime just below the power,
some prime > power2/2
static assert( power2 - 1 - prime < prime );
x = x & ( power2 - 1 );
x = ( x >= prime ) ? x - prime : x;
which is good news on my x86 with GDC -O3 (only 3 operations,
and sub cmovx ) - all well provided you make sure that you are
getting CMOVx not branches. I could work out the power from the
prime using CTFE given a bit of thought. Maybe CTFE could even
do the reverse?
Have I finally gone mad?
Yes :D, this is something compiler should do.
btw: https://github.com/dlang/phobos/pull/1452
