dotnet/corefx — pull request #164 by stephentoub (2014-11-28 21:22:46+00:00)
Title: Improve lookup perf on immutable dictionaries and sets

This PR improves the performance of lookups (indexer access, Contains, etc.) on both ImmutableDictionary and ImmutableHashSet. For the former, I've measured upwards of a 40% improvement, and for the latter, upwards of 60%, but it depends significantly on the amount of work required to get hash codes and compare TKey values... the more work required for those operations, the less benefits this change provides.

The reason for this is that, today, other than the costs of getting a hash code / comparing TKey values, a primary cost in looking up values is in traversing the ImmutableSortedDictionary.Node tree that backs both dictionaries and sets. For each node, the sorted dictionary's key needs to be compared against the supplied Int32 key. This is done using a Comparer.Default, which means an interface call through IComparer.Compare. The comparer returned from Comparer.Default is a GenericComparer, which implements its Compare method by delegating to a call to Int32's IComparable.CompareTo interface method, for another interface call. Thus, even though we know we're comparing Int32 values, each comparison actually involves multiple interface calls.

This commit creates a specialized version of ImmutableSortedDictionary`2.Node that setsTKey as Int32. This allows the new implementation, which is then used by both ImmutableDictionary`2 and ImmutableHashSet`1, to avoid multiple interface calls per node during lookups, doing the Int32 comparisons directly rather than going through Comparer.Default, which in turn goes through Int32's IComparable.CompareTo implementation. The new code is really just a copy of ImmutableSortedDictionary`2.Node, with Int32 substituted for TKey, and with doing the Int32 comparisons directly rather than going through IComparer.

Even though it's copied code (basically the equivalent of what you'd get with template expansion), it does add a bunch of code to the project. I think it's worth it for the perf improvements, but let me know if you disagree.