Use Fast-Mod algorithm for native EEHashTableBase

[EgorBo]

When I profile this simple virtual generic callsite:

public class Prog
{
    static void InvokeVGM(Prog p)
    {
        while (true)
            p.VGM<string>();
    }

    virtual void VGM<T>() {}
}

in VTune I see div as the most expensive part (if I read it correctly):

It turns out to be a EEHashTable lookup:

And It does make sense since div is a very expensive operation, on some CPU its latency can be bigger than 100 cycles. On my Coffee Lake it's 26/6 while e.g. mul is 3/1 (Latency/rec.trput)

The managed Dictionary was optimized with "Fast Mod" algorithm where we pre-calculate a special multiplier every time a new bucket is added and then can avoid expensive idiv operation by using mul see dotnet/coreclr#27299 and #406

Quick demo:

public static uint Test(uint x)
{
    uint result = 0;

    ulong cachedMul = GetFastModMultiplier(y);
    for (int i = 0; i < x; i++)
    {
        // result = i % x;
        result = FastMod(i, x, cachedMul);
    }
    return result;
}

public static ulong GetFastModMultiplier(uint divisor) =>
    ulong.MaxValue / divisor + 1;

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static uint FastMod(uint value, uint divisor, ulong multiplier) => 
    (uint)(((((multiplier * value) >> 32) + 1) * divisor) >> 32);

NOTE: the algorithm adds an overhead on dictionary expansion
NOTE2: CompareKeys is not inlined

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[EgorBo]

cc @VSadov

[jkotas]

I think this can use the same or very similar hashtable as casting https://github.com/dotnet/runtime/blob/main/src/coreclr/System.Private.CoreLib/src/System/Runtime/CompilerServices/CastHelpers.cs

[bartonjs]

If the number of buckets is a power of 2 then mod is just a masking operation. (Though depending on the distribution of dwHash values it may create overweighted buckets)

[EgorBo]

I applied the FastMod locally and got 22% improvement for the benchmark - but I am not sure I do it in a race-condition free fashion.

[VSadov]

Using FastMod could be an easy way to speed up EEHashTableBase. A few thoughts:

• FastMod has two components - divisor and multiplier. They must match thus needing a bit more care regarding races. Storing multiplier in the table, the same way we store length, could be sufficient.

• Are we sure the real problem is not collisions?
  Sometimes excessive hashing expenses is what we see, but the real problem is collisions.

• Whether EEHashTableBase is a good choice for caching is another good question.
  If scenario that we have here is similar to the type casting cache (i.e. the values can be relatively cheaply recomputed), then a solution similar to cast cache could fit better.

[EgorBo]

Prototype: EgorBo@c99fe02

the only problem that it assumes NumBuckets fits into 32bit (pretty normal) and dwHash - they always do, DWORD is 32bit

public class P
{
    [Benchmark]
    public void CallVGM()
    {
        VGM<string>();
    }

    virtual void VGM<T>()
    {
    }

    static void Main(string[] args) => 
        BenchmarkSwitcher.FromAssembly(typeof(P).Assembly).Run(args);
}

Method	Toolchain	Mean	Error	StdDev	Ratio
CallVGM	\Core_Root\corerun.exe	5.267 ns	0.1216 ns	0.1301 ns	1.00
CallVGM	\Core_Root_PR\corerun.exe	4.452 ns	0.0342 ns	0.0319 ns	0.85

then a solution similar to cast cache could fit better.

I agree but that sounds like a more invasive change, while FastMod could also improve other EEHashTable users?