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

Martin Nowak <code@dawg.eu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gooberman@gmail.com,
                   |                            |uplink.coder@googlemail.com

--- Comment #1 from Martin Nowak <code@dawg.eu> ---
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.

--

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

--- Comment #2 from uplink.coder@googlemail.com ---
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.

--

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

--- Comment #3 from Martin Nowak <code@dawg.eu> ---
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.

--

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

--- Comment #4 from Martin Nowak <code@dawg.eu> ---
(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).

--

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

ZombineDev <petar.p.kirov@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |petar.p.kirov@gmail.com

--

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

Martin Nowak <code@dawg.eu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Speed up                    |Speed up
                   |TemplateInstance.findExisti |TemplateInstance.findExisti
                   |ngInstance, hash by         |ngInstance hash
                   |mangling                    |

--

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

Martin Nowak <code@dawg.eu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |pull

--- Comment #5 from Martin Nowak <code@dawg.eu> ---
https://github.com/dlang/dmd/pull/6418

--

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

--- Comment #6 from github-bugzilla@puremagic.com ---
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

--

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

github-bugzilla@puremagic.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--

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

--- Comment #7 from github-bugzilla@puremagic.com ---
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

--