Thursday, March 10, 2011

Never leave well enough alone…until you understand what’s going on!

 

We now have built a fast generator for predictably unique but ordered Guids.

Before the profiler indicated that DateTime.Now.Ticks was quite an expensive call, I suspected the process of reversing the bytes in a 64-bit integer was too unwieldy.

Having addressed the Ticks counter issue, I decided to investigate the byte-reversing operation anyway. They don’t call me a geek for nuthin’!

This is the code I had my suspicions about:

public static byte[] GetReversedBytesSlow(this Int64 value)
{
var rgb = BitConverter.GetBytes(value);
Array.Reverse(rgb);

return rgb;
}


You can tell that I was looking back fondly to my C/C++ days, where we could cast the integer to an array of 8 bytes and do some pointer math!



Entering ‘unsafe’ territory…



I created a new Class Library project, and marked it as containing unsafe code.



UnsafeProject



Then I went at the unsafe code leaving caution to the winds:

public static unsafe class Convert
{
private static byte[] GetReversedBytesFor64BitValue(byte * rgb)
{
return new[]
{
rgb[7], rgb[6], rgb[5], rgb[4], rgb[3], rgb[2], rgb[1], rgb[0]
};

}

public static byte[] GetReversedBytes(this UInt64 _this)
{
return GetReversedBytesFor64BitValue((byte*)&_this);
}

public static byte[] GetReversedBytes(this Int64 _this)
{
return GetReversedBytesFor64BitValue((byte*)&_this);
}
}


Now, that felt really good to do Smile



By hand-unrolling the pointer arithmetic, I was sure that I would definitely be faster than the general reversal algorithm that Array.Reverse would use.



The proof of the pudding…



First, we need to make sure we’re doing the right thing in our unsafe speed-demon.



We write a test:

private static void EnsureArraysAreIdentical(byte[] expected, byte[] actual)
{
Assert.AreEqual(expected.Length, actual.Length);

for (var i=0;i<expected.Length; i++)
{
Assert.AreEqual(expected[i], actual[i]);
}
}

private const long TEST_MIN = -10000000L;
private const long TEST_MAX = 10000000L;

[TestMethod]
public void TestReverseBytes64Bit()
{
for(var l = TEST_MIN; l < TEST_MAX; l++)
{
EnsureArraysAreIdentical(GetReversedBytesSlow(l), l.GetReversedBytes());
}
}



which tests both reversal methods for identical results from –10 million to +10 million, zero inclusive.



The results speak for themselves:



UnsafeProjectTestsPassed



Now to see if we’ve actually made any difference in the performance!



FastByteReversal



Nice!



We’ve improved the performance almost 3x – it’s just that the results only become noticeable after 20 million integer reversals!



Now that’s what I call a productive afternoon!

No comments:

Post a Comment