Fast hashtable

[Cecil Ward via Digitalmars-d]

On Wednesday, 1 March 2017 at 09:45:23 UTC, Daniel Kozak wrote:
> 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

Does anyone know if the compilers could use this for code 
generation? I did later CTFE the prime from the power, can do the 
reverse more easily which is the way compilers would need to do 
it for division by known x.