Bug 16513 – Speed up TemplateInstance.findExistingInstance hash

We still have a few reports about extremely slow TemplateInstance.findExistingInstance performance. What can be seen in profiles is an excessive amount of TemplateInstance comparisons for lookups in the hash table that eat ~20% of the compilation time. Maybe we're producing an unsuited hash that isn't order dependent? Or it's just an extreme number of instances with many arguments? Still have to investigate further, but since issue 7469 got fixed we might now hash by the mangling of the template (.getIdent) instead of doing an expensive arrayObjectMatch on RootObjects (using a "virtual" match function).

It's the horrible hash that is causing the performance issue. Arguments as widely different than genericIndexOf!(CPPMethods, ushort, int, uint, long, ulong) genericIndexOf!(VTable, ushort, int, uint, long, ulong) produce the same hash. From the 88.3K lookups, 7900 have the hash 1 (one). The test code that triggered the issue contains 1K instances of VariableDescriptor!(tonsofsimulatedobjects, SimulatedEntity, "Simulated_Object_1063") VariableDescriptor!(tonsofsimulatedobjects, SimulatedEntity, "Simulated_Object_1064") and lots of instances like IsVariable!(Simulated_Object_963) IsMemberVariable!(Simulated_Object_973) isSomeFunction!(Simulated_Object_571) IsVariable!(Simulated_Object_964) IsMemberVariable!(Simulated_Object_974) isSomeFunction!(Simulated_Object_572) IsVariable!(Simulated_Object_966) IsMemberVariable!(Simulated_Object_975) isSomeFunction!(Simulated_Object_573) all producing the same hash. With such a crappy hash the behavior degrades back to the old linear search. I'll try to replace this with the mangling suffix (.getIdent) instead which should be both simpler and effective, given that all mangling bugs are fixed.

Hash collisions will happen! We need a way to speed up those equals compares in rootObject. I'll look if I can find a good way to gradually remove the virtual calls. IsVariable!(Simulated_Object_966) IsMemberVariable!(Simulated_Object_975) isSomeFunction!(Simulated_Object_573) Those SHOULD produce the same hash they work on the same types! I am of the impression that template-inlining can help here.

Managed to speed up the test case from 1.8s to 1.2s, almost completely eliminating the lookup cost. Still need to fix a few issues, the cppmangler thinks member variables are static, we might not want to fill the idPool with unused identifiers (would save some memory to just compute the hash), needs some more testing whether the mangling is really bijective, if so we could only hash the string and ditch the TemplateInstance.compare code.

(In reply to uplink.coder from comment #2) > Hash collisions will happen! > We need a way to speed up those equals compares in rootObject. > I'll look if I can find a good way to gradually remove the virtual calls. This whole RootObject hashing/comparison is a kludge when we can cheaply generate a unique string. > IsVariable!(Simulated_Object_966) > IsMemberVariable!(Simulated_Object_975) > isSomeFunction!(Simulated_Object_573) > > Those SHOULD produce the same hash they work on the same types! Yes right, only the arguments are part of the hash. > I am of the impression that template-inlining can help here. True for isSomeFunction and it does work, the other 2 take alias parameters (via variadic arguments) and create one instance per object (w/ the same hash).

Commits pushed to master at https://github.com/dlang/dmd https://github.com/dlang/dmd/commit/d41992ee9c9ce96c0dc0df97b5a63ff7f8be077f use non-associative op to combine hashes - use mixHash from MurmurHash2 for any order sensitive hashes - use ^ instead of + to reduce order insensitive AA elem hashes as it doesn't have the bias towards more significant bits - fixes Issue 16513 https://github.com/dlang/dmd/commit/b69e2edc9564850573f046a4206bbea9ff61e23b Merge pull request #6418 from MartinNowak/fix16513 fix Issue 16513 - slow findExistingInstance

Commits pushed to newCTFE at https://github.com/dlang/dmd https://github.com/dlang/dmd/commit/d41992ee9c9ce96c0dc0df97b5a63ff7f8be077f use non-associative op to combine hashes https://github.com/dlang/dmd/commit/b69e2edc9564850573f046a4206bbea9ff61e23b Merge pull request #6418 from MartinNowak/fix16513

Commits pushed to stable at https://github.com/dlang/dmd https://github.com/dlang/dmd/commit/d41992ee9c9ce96c0dc0df97b5a63ff7f8be077f use non-associative op to combine hashes https://github.com/dlang/dmd/commit/b69e2edc9564850573f046a4206bbea9ff61e23b Merge pull request #6418 from MartinNowak/fix16513