Fast hashtable

[deadalnix via Digitalmars-d]

On Wednesday, 1 March 2017 at 06:44:34 UTC, Cecil Ward wrote:
>     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?

The lower slot will be twice as crowded as the higher ones.