Fast hashtable

Cecil Ward via Digitalmars-d digitalmars-d at puremagic.com
Thu Mar 2 04:56:28 PST 2017


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.


More information about the Digitalmars-d mailing list