C# Dictionary Performance: Default string Comparer's GetHashCode() allocates memory in violation of guidelines, thus wrecking performance?

Question

There is an established guideline that getting a hashcode should not allocate memory because this will negatively impact hash table lookups by invoking the garbage collector.

Yet this exact failing is what I see what I profile my application which uses a System.Collections.Generic.Dictionary

Way deep down in a very tight loop I find the following in my profiler results:

• [3.47%] TryGetValue(TKey, TValue&) (...Dictionary)
  • [3.47%] FindEntry(TKey) (...Dictionary)
    • [3.47%] GetHashCode(string) (System.CultureAwareComparer)
      • [3.46%] GetHashCodeOfString(String, CompareOptions) (System.Globalization.CompareInfo)
        • [3.39%] [Garbage Collection]
        • [0.01%] [Thread Suspendended]

That's the whole sub-tree accounting from the profiler.

I'm not a seasoned expert in this specific sort of work, so I could be reading these tea leaves incorrectly. But it looks to me like GetHashCodeOfString "must be" allocating memory and inviting the garbage collector to interrupt my program in the middle of this loop I want REALLY TUNED AND TIGHT, and this is accounting for the staggering majority of the cost of this loop.

As an aside, here is an additional piece of evidence suggesting this code allocates memory

My next step will be to initialize the Dictionary with the ordinal comparer and re-run my tests.

But I want to know if there is existing wisdom out there around this issue. It seems like dictionaries with string keys are common, and the costs of such a common thing may be well explored. I found the following analysis, but it focuses on the actual comparison as the cause for woe, and not the hash code method allocating memory.

Can anyone suggest the proper way to use a dictionary with string keys that avoids this problem?

Specific questions I have include:

• If I use the ordinal comparitor will the allocation go away?
• If not, do I need to write my own comparitor, and will THAT make the allocation go away?
• If I do make the comparitor go away, can I really expect a real improvement, as per the MSFT recommendation link I started with?

EDIT: Crud, my bad, but this is not with the default comparer properties, we have it set to ignoreCase. Not sure if this impacts the results, but since ignoreCase would impact the equality, it must therefor have some impact on the hash.

UPDATE: Ran another test using the ordinal comparer (still with IgnoreCase), and recast the original results output to 100% cost = TryGetValue so it would be more apples to apples

Original:

• 100% TryGetValue
  • 100% FindEntry
    • 99.5% CultureAwareComparer.GetHashCode
      • 99.5% CompareInfo.GetHashCodeOfString
        • 95.86% [Garbage Collection]
        • 3.31% [Thread Suspended]
    • 0.5% CultureAwareComparer.Equals
      • 0.5% Compare
        • 0.5% [garbage collection]

Ordinal:

• 100% TryGetValue
  • 100% FindEntry
    • 47.22% CultureAwareComparer.Equals
      • 47.22% [Garbage Collection]

There also appeared to be a dramatic decrease in the overall time spend in TryGetValue. I was not careful to make sure all else was equal, but this accounted for 46 seconds out of a 10 minute stress test in the first run, and in the orindal run it accounted for 252 milliseconds. Consider that anecdotal, not an expected relative cost.

It seems like the entire cost of the hash, which used to be 99+% of the cost, is now so "free" that it fails to even appear in the profiler, which I think is running in sampling mode.

I guess this seconds the word on the street that you should use ordinal comparison.

I still can't PROVE to myself why the GC cost is contributing so heavily to the first profile result, but from the comments below I suppose I have to believe it does NOT allocate managed heap memory, but that because it's slow, it tends to be the function that is "randomly" GCed by other activities on other threads, as this process is indeed using server mode gc.

Maybe this indicates that this tight loop tends to be concurrent with allocation-happy code someplace else.

Answer 1

By default, when you use string keys, string.GetHashCode() is used. This method doesn't allocate any memory on the heap, and should be pretty fast.

But since you're using ignore case, CultureAwareComparer.GetHashCode() is used instead. That method calls (as can be seen from your profile results) CompareInfo.GetHashCodeOfString(), which in turn calls the unmanaged function InternalGetGlobalizedHashCode(). Neither of the two managed methods makes any heap allocations (as you can see if you look at them in a decompiler). I can't say what InternalGetGlobalizedHashCode() does, but since it is unmanaged, I doubt it makes any allocations on the managed heap. In any case, it has to be quite a lot more complex than the default hash code computation, especially since it is culture-aware and has to keep in mind issues like the Turkish İ.

What this means is that you probably have some other code that allocates memory on the heap, which causes the garbage collection.

And if you are going for maximum performance, you should avoid “ignore case”, and especially its culture-aware variants.