digitalmars.D.bugs - [Issue 21005] New: Speed up hashOf for associative arrays
- d-bugmail puremagic.com (49/49) Jul 01 2020 https://issues.dlang.org/show_bug.cgi?id=21005
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 puremagic.com Reporter: n8sh.secondary 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. --
Jul 01 2020