ExpandoObject vs. Dictionary from a performance point of view?

Question

A rather simple question really. I'm working on a project where I need to store and retrieve property values dynamically from a kind of context storage. The values will be written now and then and read multiple times. Speed of retrieval is the top priority here, and every nanosecond counts.

Usually, I'd simply implement this with a Dictionary, but with C# 4 and the ExpandoObject I'm thinking that maybe there is a better way? Does anyone have any experience with it? I've seen in other posts that it is NOT implemented using a Dictionary, which makes me curious as to whether it is quicker or slower?

Let me try to clarify with some pseudo code:

// In the main loop
var context = new Context();
context["MyKey"] = 123;
context["MyOtherKey"] = "CODE";
context["MyList"] = new List<int>() { 1, 12, 14 };

foreach(var handler in handlers) {
    handler.DoStuff(context);
}

-

// "Handlers"
class MyFirstHandler {
     void DoStuff(Context context) {
          if (context["MyKey"] > 100)
               context["NewKey"] = "CODE2";
     }
}

class MySecondHandler {
     void DoStuff(Context context) {
          if (context["MyOtherKey"] == "CODE")
             context["MyList"].Add(25); // Remember, it's only Pseudo-code..
     }
}

Well, hopefully you get what I'm trying to do..

I'm also completely open to other suggestions here. I have been toying with the idea of making the Context class statically typed (i.e. actually having a MyKey property, a MyOtherKey property etc), and while it might be possible it would hinder productivity quite a lot for us.

Answer 1

Speed of retrieval is the top priority here, and every nanosecond counts.

Anything to do with dynamic probably isn't what you're looking for then...

Don't get me wrong, it's pretty heavily optimised - but if you basically just want a string-to-string dictionary lookup, stick with a dictionary.

Alternatively, if you have a limited number of keys, have you considered just having an array with either an enum or a bunch of int constants as the keys?

Answer 2

Does it have to be that fast at the first call? Thanks to the call site cache, the expression trees created for the dynamic object (including the methods you add to it) is cached after it´s compiled and will be returned when you use it again.

Using ExpandoObject should work, but if you really need to get the absolutely best performance, maybe you should use custom types.

Answer 3

If the list of strings is known in advance, you could use IL Emit to create a branching tree based on the characters in the search string and resolve to an index into an array. This should give you pretty fast lookup speed.

I implemented something like this for fun and practice while I was learning IL Emit. It works based on the limited test cases I've tried, but you'll definitely want to make it more robust and create proper unit tests for production code. I've posted the raw code (it's a tad long); you'd need to change a few things for your particular case, but the core logic is there. I didn't include the EmitLdc helper function (there are a lot of overloads), but it's just a function to load an arbitrary constant to the stack. You can simply replace the calls to emit the string and numeric types directly using Ldstr and Ldc_I4 respectively.

    protected void GenerateNestedStringSearch<T>(ILGenerator gen, T[] values, Func<T, string> getName, Action<ILGenerator, T> loadValue)
    {
        //We'll jump here if no match found
        Label notFound = gen.DefineLabel();

        //Try to match the string
        GenerateNestedStringSearch(gen, notFound, values, getName, loadValue, 0);

        //Nothing found, so don't need string anymore
        gen.MarkLabel(notFound);
        gen.Emit(OpCodes.Pop);

        //Throw ArgumentOutOfRangeException to indicate not found
        gen.EmitLdc("name");
        gen.EmitLdc("Binding does not contain a tag with the specified name: ");
        gen.Emit(OpCodes.Ldarg_0);
        gen.Emit(OpCodes.Call, typeof(String).GetMethod("Concat",
                                                        BindingFlags.Static | BindingFlags.Public,
                                                        null,
                                                        new[] { typeof(string), typeof(string) },
                                                        null));
        gen.Emit(OpCodes.Newobj,
                 typeof(ArgumentOutOfRangeException).GetConstructor(new[] { typeof(string), typeof(string) }));
        gen.Emit(OpCodes.Throw);
    }

    protected void GenerateNestedStringSearch<T>(ILGenerator gen, Label notFound, T[] values, Func<T, string> getName, Action<ILGenerator, T> loadValue, int charIndex)
    {
        //Load the character from the candidate string for comparison
        gen.Emit(OpCodes.Dup);
        gen.EmitLdc(charIndex);
        gen.Emit(OpCodes.Ldelem_U2);

        //Group possible strings by their character at this index
        //We ignore strings that are too short
        var strings = values.Select(getName).ToArray();
        var stringsByChar =
            from x in strings
            where charIndex < x.Length
            group x by x[charIndex]
                into g
                select new { FirstChar = g.Key, Strings = g };

        foreach (var grouped in stringsByChar)
        {
            //Compare source character to group character and jump ahead if it doesn't match
            Label charNotMatch = gen.DefineLabel();
            gen.Emit(OpCodes.Dup);
            gen.EmitLdc(grouped.FirstChar);
            gen.Emit(OpCodes.Bne_Un, charNotMatch);

            //If there is only one string in this group, we've found our match
            int count = grouped.Strings.Count();
            Debug.Assert(count > 0);
            if (count == 1)
            {
                //Don't need the source character or string anymore
                gen.Emit(OpCodes.Pop);
                gen.Emit(OpCodes.Pop);

                //Return the value for this name
                int index = Array.FindIndex(strings, s => s == grouped.Strings.First());
                loadValue(gen, values[index]);
                gen.Emit(OpCodes.Ret);
            }
            else
            {
                //Don't need character anymore
                gen.Emit(OpCodes.Pop);

                //If there is a string that ends at this character
                string endString = grouped.Strings.FirstOrDefault(s => s.Length == (charIndex + 1));
                if (endString != null)
                {
                    //Get string length
                    gen.Emit(OpCodes.Dup);
                    gen.Emit(OpCodes.Call, typeof(char[]).GetProperty("Length").GetGetMethod());

                    //If string length matches ending string
                    gen.EmitLdc(endString.Length);
                    Label keepSearching = gen.DefineLabel();
                    gen.Emit(OpCodes.Bne_Un, keepSearching);

                    //Don't need the source string anymore
                    gen.Emit(OpCodes.Pop);

                    //Create an UnboundTag for this index
                    int index = Array.FindIndex(strings, s => s == endString);
                    loadValue(gen, values[index]);
                    gen.Emit(OpCodes.Ret);

                    //String length didn't match
                    gen.MarkLabel(keepSearching);
                }

                //Need to consider strings starting with next character
                var nextValues = from s in grouped.Strings
                                 join v in values on s equals getName(v) 
                                 select v;

                GenerateNestedStringSearch(gen, notFound, nextValues.ToArray(),
                    getName, loadValue, charIndex + 1);
            }

            //This character didn't match, so consider next character
            gen.MarkLabel(charNotMatch);
        }

        //We don't need the character anymore
        gen.Emit(OpCodes.Pop);

        //No string match, so jump to Not Found at end of check
        gen.Emit(OpCodes.Br, notFound);
    }

---

EDIT: I just realized that you're not actually using string keys, so this may not be applicable to your case. You could use a similar technique with other look ups as long as you have the ability to collect all of the required keys together in advance of using them. I'll keep this here in case anybody else might find it useful.