Ayende @ Rahien

Hi!
My name is Oren Eini
Founder of Hibernating Rhinos LTD and RavenDB.
You can reach me by phone or email:

ayende@ayende.com

+972 52-548-6969

, @ Q c

Posts: 18 | Comments: 72

filter by tags archive

Dictionary<Enum,T> Puzzler

time to read 2 min | 261 words

A while ago in the NHibernate mailing list we got a report that NHibernate is making use of a dictionary with an enum as the key, and that is causing a big performance issue.

The response was almost unanimous, I think, “what?! how can that be?!!?”. Several people went in to and tried to figure out what is going on there. The answer is totally non oblivious, Dictionary<K,V> force boxing for any value type that is used as the key.

That sound completely contradictory to what you would expect, after all, one of the major points in generics was the elimination of boxing, so what happened?

Well, the issue is that Dictionary<K,V> has to compare the keys, and for that, it must make some assumptions about the actual key. It is abstracted into EqualityComparer, and that is where the actual problem starts. EqualityComparer has some special cases for the common types (anything that is IEquatable<T>, which most of the usual suspects implements), to speed this up.

The problem is that the fall back is to an ObjectComparer, and that, of course, will box any value type.

And enum does not implements IEquatable<T>…

Omer has a good coverage on the subject, with really impressive results. Take a look at his results.

image

I am not going to steal his thunder, but I suggest going over and reading the code, it is very elegant.


Comments

Dmitry

Is this really an issue with a generic dictionary? How many values can an enum have in real life, 10-15?

Ayende Rahien

The problem isn't with the number of elements, the problem is with the number of comparisions!

Gil Fink

Thanks for sharing!

Simone

It can be accomplished in 10 lines with C# 3.0, I posted a comment on the article, I think it's been updated.

Omer Mor

Simone is right, and I'll update my article soon.

The general solution is still valid: overcoming generics' shortcoming using dynamic code generation.

Simone's idea is to use Expression Trees to generate the code instead of Lightweight Code Generation (DynamicMethod), which makes the code clearer (no need for IL).

LCG is still useful when you can't use .Net 3.5 & C#3.

Omer Mor

firefly

I am more interested on how to identify the bottleneck in the first place.

Josh

Well 1) you could forego the default comparison mechanism by supplying your own IComparer <t in the dictionary's constructor

2) It always bothered me that the CLR can't provide default implementations for IEquatable <t and GetHashCode() for value types based on its binary structure.

Comment preview

Comments have been closed on this topic.

FUTURE POSTS

  1. RavenDB 3.0 New Stable Release - 7 hours from now
  2. Production postmortem: The industry at large - about one day from now
  3. The insidious cost of allocations - 2 days from now
  4. Buffer allocation strategies: A possible solution - 5 days from now
  5. Buffer allocation strategies: Explaining the solution - 6 days from now

And 3 more posts are pending...

There are posts all the way to Sep 11, 2015

RECENT SERIES

  1. Find the bug (5):
    20 Apr 2011 - Why do I get a Null Reference Exception?
  2. Production postmortem (10):
    01 Sep 2015 - The case of the lying configuration file
  3. What is new in RavenDB 3.5 (7):
    12 Aug 2015 - Monitoring support
  4. Career planning (6):
    24 Jul 2015 - The immortal choices aren't
View all series

RECENT COMMENTS

Syndication

Main feed Feed Stats
Comments feed   Comments Feed Stats