I mis-remembered, it was a linear search though a list rather than a dict that was the problem (I think it was a list because we were looking up multiple entries or something from a list of Objects based on a field). O(N) lookup to be sure so not well optimized. But on list of 100,000 items doing 100,000 lookups it is very slow - > 1 minute whereas in Java it was like a few seconds.

Yes - refactoring was the solution. I'm not saying it couldn't perform better and it did when we re-wrote it. But that's a low-enough number of items that it surprised me that it was a problem.