[Issue 4244] AA insert from fixed-sized array much slower than from equivalent struct

[via Digitalmars-d-bugs]

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

--- Comment #3 from hsteoh at quickfur.ath.cx ---
The problem is caused by the hash computation of arrays (including static
arrays). Here's the benchmark code I used:


------
void hashTest() {
    import std.conv : to;
    import std.datetime : Duration, benchmark;
    import std.stdio : writefln;

    static struct Pair { int x, y; }

    int[2] staticArray;
    Pair pair;

    auto result = benchmark!(() => typeid(staticArray).toHash(),
                             () => typeid(pair).toHash())(30_000_000);

    writefln("staticArrayHash: %s", to!Duration(result[0]));
    writefln("structHash: %s", to!Duration(result[1]));
}

void main() {
    hashTest();
}
------


Here are some trial runs showing the typical measurements:
------
$ ./test 
staticArrayHash: 8 secs, 947 ms, 130 μs, and 7 hnsecs
structHash: 1 sec, 196 ms, 711 μs, and 1 hnsec
$ ./test 
staticArrayHash: 9 secs, 130 ms, 423 μs, and 2 hnsecs
structHash: 1 sec, 196 ms, and 737 μs
$ ./test 
staticArrayHash: 8 secs, 922 ms, 449 μs, and 9 hnsecs
structHash: 1 sec, 260 ms, 688 μs, and 8 hnsecs
$ ./test 
staticArrayHash: 9 secs, 43 ms, 237 μs, and 6 hnsecs
structHash: 1 sec, 196 ms, and 983 μs
------

This shows that computing the hash of a static array is about 8-9 times slower
than computing the hash of a struct of equivalent size.

Looking into the druntime code, it seems that a likely cause of the performance
problem is the getArrayHash() function, which calls an inner function
hasCustomHash() that in turn calls getElement(), which uses a loop to walk up
the TypeInfo tree to ascertain whether the array elements have a custom hash
function. I copied the druntime code into my test file, and modified
hasCustomToHash() to just return false, and the benchmark shows that the array
hash function is now approximately on par with the struct hash function.

So, it looks like the culprit is the call to getElement(). I'll see if I can
cook up a PR to fix this.

--