Ayende @ Rahien

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

ayende@ayende.com

+972 52-548-6969

@

Posts: 5,947 | Comments: 44,540

filter by tags archive

Dictionary<Enum,T> Puzzler


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

No future posts left, oh my!

RECENT SERIES

  1. RavenDB Sharding (2):
    21 May 2015 - Adding a new shard to an existing cluster, the easy way
  2. The RavenDB Comic Strip (2):
    20 May 2015 - Part II – a team in trouble!
  3. Challenge (45):
    28 Apr 2015 - What is the meaning of this change?
  4. Interview question (2):
    30 Mar 2015 - fix the index
  5. Excerpts from the RavenDB Performance team report (20):
    20 Feb 2015 - Optimizing Compare – The circle of life (a post-mortem)
View all series

RECENT COMMENTS

Syndication

Main feed Feed Stats
Comments feed   Comments Feed Stats