FC23: ComboKey - the perfect value type key for hash container

In the regular expression reuse discussion, we talked about there is a cache lookup in the Regex constructor:

Notice the key for the cache lookup is generated from 5 strings. This is not optimal for cache lookup. What would be a better key type? You could use Tuple, but there will be one heap allocation; plus its GetHashCode/Equals implementation is quite bad.

To avoid heap allocation, you can use ValueTuple, but its IEquatable interface is not optimal either:

EqualityComparer.Default needs to be called every time, and it’s not cheap. Newer version of .Net Core is adding optimizations in JIT compiler layer.

To have the perfect value key type for hash containers, let’s introduce our own ComboKey struct:

ComboKey uses IEquatable constraint to make GetHashCode/Equals implementations faster. They can even be inlined for value types.

Here is the three-field version:

Source code: FrugalCafe/Common/ComboKey.cs at master · ProfFrugal/FrugalCafe (github.com)

Perf test, comparing Tuple, ValueTuple, and ComboKey:

Results:

ValueTuple is 55% faster than Tuple, ComboKey is 59% faster than ValueTuple. We have a clear winner.

Anything strange about the numbers? Why is using Tuple allocating 176 bytes every time? Tuple would be 32 bytes, in 64-bit world. The remaining 144 bytes is 24 × 6. There are 6 boxing happening here: 2 in GetHashCode, 4 in Equals implementation. Avoid using Tuple as hash container key types, especially when value types are involved.