FC67: A super cool interface to add: IMatcher<T>

PerfView has a feature to export call stacks in xml format. I clicked on it and found it to be super slow, so I captured a trace. Here is from allocation trace:

97.4% of total allocations are from string.Substring call in a single method, 43 gb in the trace, something is not right.

Source code:

The problem is that the code is calling string.Substring twice and then try to do interning based on the substrings. This is the slow way of interning based on strings. You need to implement interning with a little sub string allocations as possible.

Here is the implementation:

It’s a custom hash container implementation, based on IEquatable interface. The problem with IEquatable and IEqualityComparer interface is that they only allow comparing objects of the same types. What if I want to compare an apple with an orange, just based on their nutritional values, you can’t do that.

Let’s add a new interface to allow such comparison, introducing IMatcher:

IMatcher interface allows objects of another type to return matching hash codes, perform equality check, while deferring conversion as much as possible.

A common usage case would be Substring struct to implement IMatcher interface:

Substring’s GetHashCode is designed to match .Net Framework 64-bit string.GetHashCode exactly, the Win16 slow implementation.

Equals check is much easier:

Now we can adda new Intern method:

In the lookup phase, IMatcher interface’s GetHashCode/Equals implementations are used. ConvertTo is only called when the value needs to be added as a new entry.

Most of those substring allocations would be gone, and the xml generation is now much faster. The power of a little interface.

Notice IMatcher interface can be implemented by lots of classes/structs. Here is another place using it in this call stack:

FrameInfo2 is a cheaper clone of FrameInfo for interning lookup.

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