FastStringKeyDictionary Intro

Hi, today I will show you intro, partly implemented code of the fast dictionary with string type key. My work is partial. There are tests for Add, ContainsKey, and TryGetValue methods. If you like, you can continue this work and add the Remove method and an Enumerator. I left that to give you a direction and the idea, but I want to leave something for you. In fact easy part of working on your own. So, you may be wondering how fast this collection is? I also compared it with very fast ConcurrentDictionary and got better results. Improvement is small, but it is. And when you fight with every millisecond for any backed system, even that can help you. So here are my results.

image

As you can see new fast string key dictionary is a bit faster, and I think that in any real-time system that optimization is worth do do it. Even if it is only a few percent decreases in invocation time.

I like to post code in ready to download form. So I will share with you the complete solution in a zip file. But first, I want to show you the essence of optimization. I called this class StorageDictionary. And I used tiny maps as arrays for all letter indexes in the English alphabet, so from ‘A’ to ‘Z’ and from ‘a’ to ‘z’ and from ‘0’ to ‘9’ works great. Of course, if you want more characters to address your values in the string key, feel free to add more. But for any URL, URI, or different kinds of addresses, I think it is fine. And you will get an idea of how it works by looking at the code below.

private class StoreageDictionary<U>
{
    private readonly U[] L = new U[(int)('Z' - 'A') + 1];
    private readonly U[] l = new U[(int)('z' - 'a') + 1];
    private readonly U[] d = new U[(int)('9' - '0') + 1];
    internal int FindIndex(char key, out U[] a)
    {
        if (key >= 'A' && key <= 'Z')
        {
            a = L;
            return (int)(key - 'A');
        }
        if (key >= 'a' && key <= 'z')
        {
            a = l;
            return (int)(key - 'a');
        }
        if (key >= '0' && key <= '9')
        {
            a = d;
            return (int)(key - '0');
        }
        a = null;
        return -1;
    }
    internal void Add(char key, U value)
    {
        U[] a;
        var i = FindIndex(key, out a);
        a[i] = value;
    }
    internal bool TryGetValue(char key, out U value)
    {
        value = default(U);
        U[] a;
        var i = FindIndex(key, out a);
        if (i == -1) return false;
        value = a[i];
        return value != null;
    }
    internal void Remove(char key)
    {
        U[] a;
        var i = FindIndex(key, out a);
        a[i] = default(U);
    }
}

As I promised this is whole solution of intro for you FastStringKeyDictionary (3045 downloads). It is one more thing… 🙂 In StoreageDictionary, the class state is created all-in-one at construction time. But when you have only digits, not all state is needed. Do you know how to solve it? Keep in mind that this construction needs to be thread-safe :P. Enjoy!

p ;).

3 Replies to “FastStringKeyDictionary Intro”

  1. Hi,
    I think that the results of your implementation strongly depend on the machine where the tests were run. I received the following times on my computer (Intel Core I7 2.40 GHz, 16GB RAM): 880/822, 1657/1771, 89/90, 134/115, 109/107, 126/125 and unfortunately they show that FastStringKeyDictionary is slower.

  2. Did you try run it not in Visual Studio but compile in Release mode and run from command line? Not from vhost in VS?

    • I received the previous results by running your program outside of VS. However, I repeated my tests in Release mode and here are example times of 1 run: 946/919, 1336/1315, 86/106, 77/73, 84/82, 77/74.
      I run your program a few times. Your implementation was always slower in the case of ADD operation. As to CONTAINS KEY and TRY GET operations, your dictionary was sometimes a little bit slower and sometimes a little faster.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.