5
\$\begingroup\$

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).

\$\endgroup\$
3
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ I like the | operator more then my += and I guess the compiler is too clever. I tried the pointer with fixed and unsafe, and | and + and even moving EncodeLetter into a new method and decorating it with the [MethodImpl(MethodImplOptions.AggressiveInlining)] attribute but there was no measurable difference. CC: @NikitaB \$\endgroup\$ – t3chb0t Jul 11 '17 at 16:30
  • \$\begingroup\$ Yes, there are good chances that compiler(s) here are very smart to rewrite our code, biggest gain is probably just switching to int keys. No difference even with pointers? Good JIT guys... \$\endgroup\$ – Adriano Repetti Jul 11 '17 at 17:05
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Great! I didn't know that. Casting by hand gone ;-) as far as performance is concerned there is no measureable difference but still, this is a nice improvement. \$\endgroup\$ – t3chb0t Jul 11 '17 at 17:04
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If this was only that easy ;-) I'm already using a dictionary to cache some values but the lookup with a string is still to slow, that's why I want to use an int becasue even if I calculate it everytime it's still faster then a case-sensitive string comparer. The code is actually more then just a hash-code. It's also used for SortedHashSet with a custom comparer but parsing the string with int.Parse etc is too slow so I use a dictionary to cache the results but now the string lookup is slowing it down :-) A dictionary is only one of the usages. On the second place is sorting. \$\endgroup\$ – t3chb0t Jul 10 '17 at 18:19
  • \$\begingroup\$ @t3chb0t eh, yeah I wondered why didn't you already wrote it like that.. Also there is a small improvement you can make return result += letter; if you replace that with return result + letter; it should run a bit faster. Besides that I cant see other way of improving the speed tbh :S \$\endgroup\$ – Denis Jul 10 '17 at 18:23
  • \$\begingroup\$ Yes, 40 million is just the beginning, I'm expecting at least two or three times that much calls at least for now. \$\endgroup\$ – t3chb0t Jul 10 '17 at 18:23
  • 1
    \$\begingroup\$ I wondered why didn't you already wrote it like that you know the rule, write the code first and optimize it later. It's hard to predict what can be the slowest part until you have the full algorithm ;-] Even though I use tons of LINQ, non of the queries is on the list. Just dictionaries, hash-sets and comparers. \$\endgroup\$ – t3chb0t Jul 10 '17 at 18:25
  • \$\begingroup\$ There is however one good thing about it ;-) If you are disciplined and apply the SRP really to everything then there is only a single place where I need to change it from string to int and the improvement is instantly noticeable ;-] \$\endgroup\$ – t3chb0t Jul 10 '17 at 18:32
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.