Why does LightInject use an ImmutableHashTree to store registrations, instead of a simple Dictionary?

Question

I'm looking at several IoC contains in order to choose one to use in my work, and taking a look at LightInject's codebase I came across something I don't understand...

In ServiceContainer's GetInstance(Type serviceType, string serviceName) method, it forms a key from the parameters and calls 'Search' on 'namedDelegates':

var key = Tuple.Create(serviceType, serviceName);
var instanceDelegate = namedDelegates.Search(key);

namedDelegates is an ImmutableHashTree<TKey, TValue>, an internal class that implements (from its own comments):

/// A balanced binary search tree implemented as an AVL tree.

The reason I'm looking at LightInject is because of its excellent scores in Daniel Palme's IoC Performance Comparison and I'm puzzled as to why a O(log n) binary search algorithm is preferable to using a O(1) Dictionary in this case?

Can anyone educate me here?

Answer 1

Have not used, just peeked at the source code

My theory is so that duplicate keys can used as needed either from their API point of view or the consuming dev's. Search(TKey) handles checking duplicates it found in the tree so that's what lead me to that.

Another is also probably for performance -- as you mentioned in your question it looks quite speedy. Their search on the ImmutableHashTree graciously handles the issue of a value not being found as it just returns default(TValue).

This seems like it would be faster than the following with a Dictionary<TKey, TValue> which already is doing a lot of the same work to find your value based on the Key given.

if (myDictionary.ContainsKey(myKey))
    return myDictionary[myKey]; // Practically double the work has been done
else
    return default(TValue);

try
{
    return myDictionary[myKey];
}
catch(Exception ex)
{
    // Exceptions can be expensive.
    return default(TValue);
}

Their way only does search once and doesn't worry about catching exceptions to handle the fact the key wasn't present.

Again, this is what I gathered giving just a quick look at the source code and should not be considered as concrete.