[Issue 21005] New: Speed up hashOf for associative arrays

[d-bugmail at puremagic.com]

https://issues.dlang.org/show_bug.cgi?id=21005

          Issue ID: 21005
           Summary: Speed up hashOf for associative arrays
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: druntime
          Assignee: nobody at puremagic.com
          Reporter: n8sh.secondary at hotmail.com

Current code:
---
size_t h = 0;
foreach (key, ref val; aa)
{
    size_t[2] hpair;
    hpair[0] = key.hashOf();
    hpair[1] = val.hashOf();
    h += hpair.hashOf();
}
---

Proposed code:
---
size_t h = 0;
foreach (ref key, ref val; aa)
    h += hashOf(hashOf(val), hashOf(key));
---

On a 32-bit machine the old code is equivalent to:
---
size_t h = 0;
foreach (key, ref val; aa)
{
        size_t k = hashOf(hashOf(key), 0);
        k = hashOf(hashOf(val), h);
        k = fmix32(k ^ (size_t.sizeof * 2)); // fmix32 being the MurmurHash3
finalizer.
        h += k;
}
---

On a 64-bit machine the work involved is greater. That level of mixing at each
step is excessive.

Note:
Writing `hashOf(val, hashOf(key))` might seem better than `hashOf(hashOf(key),
hashOf(key))` as it possibly avoids redundancy, but that can't be used by the
TypeInfo-based hash in rt.aaA._aaGetHash.

--