Faster alternative than Dictionary?

Question

I'm creating a library which I'm performance testing. In it I generate a Dictionary<Type, X> once. The items are currently inserted in a random order. The dictionary remains unchanged during the application lifetime.

It's then frequently used to lookup items. The lookup is one of the larger bottlenecks in the library.

Yes, I'm micro-optimizing, but to learn. I'm wondering if there are a better way to get lookup performance?

Update

I've used dotTrace to measure the performance. The report + dotTrace is in my home computer, so I don't have the report here (could have uploaded it somewhere otherwise).

I used the tests found here: https://github.com/danielpalme/IocPerformance

The dictionary definition is found here: https://github.com/jgauffin/Griffin.Container/blob/master/Source/Griffin.Container/ContainerBase.cs

(I created the container last friday, don't expect too much)

Update2

Performance breakdown

Dictionary.TryGetValue takes totally 101ms of Resolve (total 251ms) which is 40,2% if I've interpreted the numbers correctly.

a: How many types/pairs in the data, b: what makes you think it is a bottleneck ? (i.e. how have you measured? can we see any of the lookup code?) — Marc Gravell, May 14 '12 at 07:10
and c: are the callers using static types (i.e. `int` etc), or are they using `Type` objects due to reflection? if the callers know the types statically, there are some tricks that could be used — Marc Gravell, May 14 '12 at 07:11
@MarcGravell : could you extend a bit on those tricks (answer or link) as it is an interesting subject. thanks — mathieu, May 14 '12 at 07:19
@mathieu in particular, I was thinking a generic static type, i.e. `SomeCache.Whatever(...)`, with a static initializer (`.cctor`) to prepare the metadata per `T`. — Marc Gravell, May 14 '12 at 07:21
@MarcGravell: How many types do you use in an average application that uses an IoC container? A couple of hundred in most extreme cases? — jgauffin, May 14 '12 at 08:04
I've just done a test, using both dictionary and hashtable, and in either case it can do, for 200 types in the lookup, 2M lookups in < 100ms. That is pretty stonkingly fast. I'm not convinced this is a real issue...? — Marc Gravell, May 14 '12 at 08:22
Let me install dotTrace on my laptop and redo the tests during my lunch (in two hours) — jgauffin, May 14 '12 at 08:25
@MarcGravell: Doing a static SomeCache will not work, since q. the DI container must be able to have `GetInstance(Type)` which would cause reflection and 2. it is possible that the user creates multiple container instances, which invalides a static cache. But indeed, the performance of `SomeCache` would be great. — Steven, May 14 '12 at 13:38

score 2 · Answer 1 · answered May 14 '12 at 10:30

2

If the type is compile-time defined, you may try to implement it like this:

static class ValueFor<T>
{
  // you get another field per type T
  public static X X { get; private set; }

  internal static SetUpValue(X value) { X = value; }
}

Just access using this.

var myIntX = ValueFor<int>.X;

answered May 14 '12 at 10:30

Stefan Steinegger

63,782
15
129
193

Unfortunately no. The mappings are created by the user/dev at runtime (as for all IoC containers) – jgauffin May 14 '12 at 11:07

Steven · Accepted Answer · 2013-04-04T23:47:01.287

The performance benchmark for IoC containers from Daniel Palme (but those of others as well) is a bit misleading, since the benchmark resolves very shallow object graphs from the container (although it does show clearly that the performance differences between the containers are big). This is unrealistic, because most applications (that use DI properly) will have object graphs that contain dosens of objects. When doing this, only the root object needs to be resolved, and when the container is written properly, this means you will only have a single call to Dictionary<T,V>.TryGetValue per (web) request in most situations (or at most just a few). Because of this, the performance of Dictionary<T, V> is not really an issue.

I believe that biggest part of the performance cost of Dictionary<T,V> where TKey is System.Type, has to do with the performance cost of generating a hash code for the given Type. Every time you call TryGetValue, Type.GetHashCode() has to be called. GetHashCode is virtual (can't be inlined) and that method calls 3 other virtual methods. In the end a static (external) call is made to RuntimeHelpers.GetHashCode(key).

In other words, you would be able to optimize performance to write a specific (non generic) dictionary class that uses Type as a key and instead of calling Type.GetHashCode() you should call RuntimeHelpers.GetHashCode(key).

UPDATE (2013-04-05):

A few months back I tried to improve the performance of the DI container I maintain and I played with optimizing the dictionary part. I wrote my own dictionary that directly called RuntimeHelpers.GetHashCode(key) (and skipped the virtual calls) but in the end the performance gains where so small (around 1% in Palme's benchmarks) that I decided to revert these code changes. So my current understanding is that the real performance cost with Dictionary<Type, X> is actually everything that happens inside RuntimeHelpers.GetHashCode(key).

Would it not be a better way to use Dictionary and save the Type.FullName as the key? This way the call to Type.GetHashCode() will not happen. — gwt, Jan 19 '20 at 15:15
This is an educated guess, but I assume that using `String` as key is much slower, because of [how hashes are calculated](https://stackoverflow.com/questions/15174477/how-is-gethashcode-of-c-sharp-string-implemented) in strings, and because the performance of `String.GetHashCode()` is linear to the length of the string. — Steven, Jan 19 '20 at 15:56
And there is actually overhead in calling `Type.FullName` as well. — Steven, Jan 19 '20 at 16:02

Faster alternative than Dictionary?

2 Answers2