Fast case-insensitive hash-code for specific codes

Question

I'm trying to fix another bottleneck identified with a profiler (dotTrace). This time it's a case insensitive hash-code.

Currently I'm using the StringComparer.OrdinalIgnoreCase as a comparer for a dictionary and a custom implementaion of an IComparable<string>. With 40 millions calls it costs me ~14 seconds. This is too much as there will be more calls in future. I'd like to replace it with an int to improve the lookup time.

The values I'm working with are in the format and between 1A and 99Z. There will never be other codes.

I've build a proof-of-concept for encoding and decoding these codes that works like that:

I shift each char to the left by 8 bits from left to right: for example 5A and 20F.

               5        A
       2       0        F
-------- ------- --------

The decoder unshifts them and rebuilds the string (mainly for debugging purposes as I actually won't be doing this much). Additionaly if a letter exceeds the A-Z alphabet its case is fixed to upper-case.

static class CaseInsensitiveCoordinate
{
    private const int AlphabetLength = ('Z' - 'A');
    private const int AlphabetsDistance = ('a' - 'Z');
    private const int CaseFix = AlphabetLength + AlphabetsDistance;

    public static int Encode(this string value)
    {
        var result = 0;

        // Assume the code has only two chars.
        result += (int)value[0] << 8;

        // Oh, there are tree, then shift what we have and add the next one.
        if (value.Length == 3)
        {
            result <<= 8;
            result += (int)value[1] << 8;
        }

        // Finally add the letter and fix the casing.
        var letter = (int)value[value.Length - 1];
        if (letter > 'Z')
        {
            letter -= CaseFix;
        }

        return result += letter;
    }

    public static string Decode(this int value)
    {
        // Unshift all values and rebuild the string.
        return
            (value > "9Z".Encode())
                ? new string(new[]
                {
                    (char)((value & 0xFF0000) >> 16),
                    (char)((value & 0xFF00) >> 8), 
                    (char)(value & 0xFF) 
                })
                : new string(new[] 
                { 
                    (char)((value & 0xFF00) >> 8), 
                    (char)(value & 0xFF) 
                });
    }
}

Simple Stopwatch measurements in LINQPad (compiled as release) result in a difference of about ~1.5 seconds for 40 million loops between the string-comparer and my hash-code.

void Main()
{

    var dic = new Dictionary<string, object>(StringComparer.OrdinalIgnoreCase) { ["5A"] = new object() };
    var dic2 = new Dictionary<int, object> { [13633] = new object() };

    var count = 40_000_000;

    var sw = Stopwatch.StartNew();  
    for (int i = 0; i < count; i++)
    {
        var result = dic["5A"];
    }   
    sw.Elapsed.Dump();

    sw = Stopwatch.StartNew();  
    for (int i = 0; i < count; i++)
    {
        var result = dic2["5A".Encode()];
    }   
    sw.Elapsed.Dump();
}

I call them hash-codes because I'm going to use them as such but at the same time they are a numeric representation of the string-code and they also need to remain sortable (they are use in a SortedHashSet).

Answer 1

There isn't much left to optimize there, just few cycles, but with 40 millions calls the difference might be at least measurable.

When value.length == 3 you perform << 8 twice and csc or JIT compiler have no chance to optimize this, given that length can be only 2 or 3 then you can make it explicit (I think you will also gain in clarity but that's just a point of view):

public static int Encode(this string value)
{
    Debug.Assert(value != null);
    Debug.Assert(value.Length == 2 || value.Length == 3);

    if (value.Length == 2)
    {
        return ((int)value[0] << 8)
            | EncodeLetter(value[1]);
    }
    else
    {
        return ((int)value[0] << 16)
            | ((int)value[1] << 8)
            | EncodeLetter(value[2]);
    }

    int EncodeLetter(char c)
        => c > 'Z' ? (return c - CaseFix) : (c);
}

In this way you should save one shift << (which isn't super-fast in all .NET environments). Also direct access to string items without value.Length - 1 should be slightly faster. Bitwise OR | may be faster than sum + but it depends on an huge amount of details (specific CPU, in primis, and how uop will be fused with surrounding code)...not something we can determine without more details. Here I like it only because of clarity.

It would be nice if we may get the JIT compiler to drop bounds checking here, is unsafe code allowed here?

I added few Debug.Assert(), not a penalty price you want to pay in released code but probably useful when running tests on your own development machine.

About Decode(): "9Z".Encode() might be saved in a static readonly field (in my case it seems it's not optimized away by compiler/JIT).

Answer 2

Upper case and lower case Ascii chars differ by 0x20. A fast way to ignore case is to either OR every char with 0x20 (for lower-case) or AND every char with ~0x20 (for upper-case) prior to hashing.

Answer 3

Your biggest problem is that you're calling the same method over and over again with that much entries you will most certainly have some that repeat, to improve that just use memoization or generate them beforehand, there is only a finite amount of combinations you can have, plus they are not that much and also not hard at all to generate:

//1A up to 99Z
var encodedValues = new Dictionary<string, int>();
for (int i = 1; i < 100; i++)
{
    for (char c = 'A'; c <= 'Z'; c++)
    {
        string s = $"{i}{c}";
        encodedValues.Add(s, s.Encode());
    }
}

There you go, that's all of them, your for loop is shorter, cleaner and faster now:

for (int i = 0; i < count; i++)
{
    var result = encodedValues["5A"];
}

As mentioned you can use memoization too, but that would probably turn out to be slower and if you really have records >= 40 millions than the approach shown above should be faster.

This should bring your method to about 600ms ahead of the string version.

Answer 4

I don't think there is a way to do this faster. You might want to experiment with unsafe shenanigans, but I doubt you'll get a significant performance improvement if any. Since your strings have varying size direct mapping is extremely unsafe:

 fixed(char* res = str)
 {
     return *((int*)res);
 }

therefore it is not an option. And any type of memory copying will probably be slower than what you have.

My only suggestion is to move CaseFix to equality comparer instead of "fixing" the codes directly. Leave the codes unique, but compare them as:

var res = code1 - code2;
return res == 0 || res == CaseFix;

Logically, this makes more sense to me, not sure if it makes a difference performance-wise.