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