Performance Quiz #12 -- The Cost of a Good Hash -- Some Help
I continue to be astounded by what my readers can come up with.
As usual I had a purpose for posing my last question and that purpose was to show that basically its hard to get a handle on what things cost in any kind of omnibus way. But imagine my surprise when Frank and Shuggy turned this into an interesting discussion of hashing techniques and combining hashes. To say nothing of some of the other regulars (you know who you are) that have insightful comments. Those comments are definately worth a read and thanks very much for presenting them!
But I don't know that anyone has answered my question quite squarely (except maybe Alois) and I think this makes my point that it is hard to answer this question.
But what if you were to download this file... I think you'd find it quite helpful.
What you see is a compilation of one cost metric for the entire framework. It's not the only cost metric by any means, you could imagine many others, but it is an interesting one. The cost is computed by doing a static analysis of all allocations made in the call tree of each method. It's the metric that I discussed in this article on performance signatures including the exception for methods that look like they do a one-time allocation. The cost is logarithmic, base 10, offset by 1, i.e.
if (allocation_count == 0)
cost = 0;
cost = 1+log(allocation_count)
And I'm only reporting one digit after the decimal because I want to give the idea that this is just a rough cost, it's not supposed to be super-precise it's just supposed to give you a rough idea of whether or not a method is very complex or not so much.
I'm trying to think of a good name for this metric, so far I'm thinking something like Allocation Complexity but I'm open to better ideas.
Anyway snoop the file then see if you can answer my question. For bonus points look at some other low level functions that might be interesting like say Compare, Equals, or GetEnumerator. It's very intersting to see that some methods that seem like they should be very low level are actually quite high level.
I think costs like this one can be very useful in making decisions about which framework features to use in which contexts.
Again this is only one kind of cost and its only approximate but I think it's interesting nonetheless.
Now would you like to try the original question again:
Q: Name five implementations of GetHashCode in the framework that do things that you wouldn't expect a hashing function to do.