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 also Remove method and an Enumerator. I left that to give you a direction and the idea but I want to left something for you. In fact easy part for work on your own. So, you may be wonder how fast this collection is? I compared with also very fast ConcurrentDictionary and I get 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 there 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 few percent decreasing of invocation time.

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

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 (2837 downloads). It is one more thing… :) In StoreageDictionary 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 need to be thread-safe :P. Enyoj!

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.