C# SuperFastHash and MurmurHash2 implementations
25 February 2009
I'll discuss each hash separately and discuss my different implementation, in the end I’ll post the final implementation and let you chose yourself.
SuperFastHash
This one I already knew, so I implemented this one very fast to the following simple implementation. This implementation is very standard .NET code which just a few optimizations.
public class SuperFastHashSimple : IHashAlgorithm { public UInt32 Hash(Byte[] dataToHash) { Int32 dataLength = dataToHash.Length; if (dataLength == 0) return 0; UInt32 hash = Convert.ToUInt32(dataLength); Int32 remainingBytes = dataLength & 3; // mod 4 Int32 numberOfLoops = dataLength >> 2; // div 4 Int32 currentIndex = 0; while (numberOfLoops > 0) { hash += BitConverter.ToUInt16(dataToHash, currentIndex); UInt32 tmp = (UInt32)(BitConverter.ToUInt16(dataToHash, currentIndex + 2) << 11) ^ hash; hash = (hash << 16) ^ tmp; hash += hash >> 11; currentIndex += 4; numberOfLoops--; } switch (remainingBytes) { case 3: hash += BitConverter.ToUInt16(dataToHash, currentIndex); hash ^= hash << 16; hash ^= ((UInt32)dataToHash[currentIndex + 2]) << 18; hash += hash >> 11; break; case 2: hash += BitConverter.ToUInt16(dataToHash, currentIndex); hash ^= hash << 11; hash += hash >> 17; break; case 1: hash += dataToHash[currentIndex]; hash ^= hash << 10; hash += hash >> 1; break; default: break; } /* Force "avalanching" of final 127 bits */ hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 4; hash += hash >> 17; hash ^= hash << 25; hash += hash >> 6; return hash; } }
The most performance was lost with the BitConverter.ToUInt16 which is implemented as a unsafe pointer cast, but does some checking before the cast, the next step was to inline the byte to UInt16 conversion.
public class SuperFastHashInlineBitConverter : IHashAlgorithm { public UInt32 Hash(Byte[] dataToHash) { Int32 dataLength = dataToHash.Length; if (dataLength == 0) return 0; UInt32 hash = (UInt32)dataLength; Int32 remainingBytes = dataLength & 3; // mod 4 Int32 numberOfLoops = dataLength >> 2; // div 4 Int32 currentIndex = 0; while (numberOfLoops > 0) { hash += (UInt16)(dataToHash[currentIndex++] | dataToHash[currentIndex++] << 8); UInt32 tmp = (UInt32)((UInt32)(dataToHash[currentIndex++] | dataToHash[currentIndex++] << 8) << 11) ^ hash; hash = (hash << 16) ^ tmp; hash += hash >> 11; numberOfLoops--; } switch (remainingBytes) { case 3: hash += (UInt16)(dataToHash[currentIndex++] | dataToHash[currentIndex++] << 8); hash ^= hash << 16; hash ^= ((UInt32)dataToHash[currentIndex]) << 18; hash += hash >> 11; break; case 2: hash += (UInt16)(dataToHash[currentIndex++] | dataToHash[currentIndex] << 8); hash ^= hash << 11; hash += hash >> 17; break; case 1: hash += dataToHash[currentIndex]; hash ^= hash << 10; hash += hash >> 1; break; default: break; } /* Force "avalanching" of final 127 bits */ hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 4; hash += hash >> 17; hash ^= hash << 25; hash += hash >> 6; return hash; } }
This is the fastest no-hacks managed implementation of the SuperFastHash, but the result will change if the Endianness changes. I’ve been looking for a way to cast the byte array to a int array without have to do Marshal.Copy, I found a dirty hack using FieldOffset(0), I have no idea if this hack is going to be supported on new versions of the CLR so using this is a risk. The only strange part is that the UInts.Length is the length of the bytes array, but the index is of the UInt16 array, so the max index for that array is UInts.Length / sizeof(UInt16). Below is the implementation of this hack.
public class SuperFastHashUInt16Hack : IHashAlgorithm { [StructLayout(LayoutKind.Explicit)] // no guarantee this will remain working struct BytetoUInt16Converter { [FieldOffset(0)] public Byte[] Bytes; [FieldOffset(0)] public UInt16[] UInts; } public UInt32 Hash(Byte[] dataToHash) { Int32 dataLength = dataToHash.Length; if (dataLength == 0) return 0; UInt32 hash = (UInt32)dataLength; Int32 remainingBytes = dataLength & 3; // mod 4 Int32 numberOfLoops = dataLength >> 2; // div 4 Int32 currentIndex = 0; UInt16[] arrayHack = new BytetoUInt16Converter { Bytes = dataToHash }.UInts; while (numberOfLoops > 0) { hash += arrayHack[currentIndex++]; UInt32 tmp = (UInt32)(arrayHack[currentIndex++] << 11) ^ hash; hash = (hash << 16) ^ tmp; hash += hash >> 11; numberOfLoops--; } currentIndex *= 2; // fix the length switch (remainingBytes) { case 3: hash += (UInt16)(dataToHash[currentIndex++] | dataToHash[currentIndex++] << 8); hash ^= hash << 16; hash ^= ((UInt32)dataToHash[currentIndex]) << 18; hash += hash >> 11; break; case 2: hash += (UInt16)(dataToHash[currentIndex++] | dataToHash[currentIndex] << 8); hash ^= hash << 11; hash += hash >> 17; break; case 1: hash += dataToHash[currentIndex]; hash ^= hash << 10; hash += hash >> 1; break; default: break; } /* Force "avalanching" of final 127 bits */ hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 4; hash += hash >> 17; hash ^= hash << 25; hash += hash >> 6; return hash; } }
The last stap was to go to unsafe land and do real pointer stuff.. This implementation looks a lot like the original c implementation
public class SuperFastHashUnsafe : IHashAlgorithm { public unsafe UInt32 Hash(Byte[] dataToHash) { Int32 dataLength = dataToHash.Length; if (dataLength == 0) return 0; UInt32 hash = (UInt32)dataLength; Int32 remainingBytes = dataLength & 3; // mod 4 Int32 numberOfLoops = dataLength >> 2; // div 4 fixed (byte* firstByte = &(dataToHash[0])) { /* Main loop */ UInt16* data = (UInt16*)firstByte; for (; numberOfLoops > 0; numberOfLoops--) { hash += *data; UInt32 tmp = (UInt32)(*(data + 1) << 11) ^ hash; hash = (hash << 16) ^ tmp; data += 2; hash += hash >> 11; } switch (remainingBytes) { case 3: hash += *data; hash ^= hash << 16; hash ^= ((UInt32)(*(((Byte*)(data))+2))) << 18; hash += hash >> 11; break; case 2: hash += *data; hash ^= hash << 11; hash += hash >> 17; break; case 1: hash += *((Byte*)data); hash ^= hash << 10; hash += hash >> 1; break; default: break; } } /* Force "avalanching" of final 127 bits */ hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 4; hash += hash >> 17; hash ^= hash << 25; hash += hash >> 6; return hash; } }
MurmurHash2
The next algorithm was MurmurHash2, the code is very simple, the only dificult part was the fall-trough case which luckely isn't supported in c#, below is the first implementation.
public class MurmurHash2Simple : IHashAlgorithm { public UInt32 Hash(Byte[] data) { return Hash(data, 0xc58f1a7b); } const UInt32 m = 0x5bd1e995; const Int32 r = 24; public UInt32 Hash(Byte[] data, UInt32 seed) { Int32 length = data.Length; if (length == 0) return 0; UInt32 h = seed ^ (UInt32)length; Int32 currentIndex = 0; while (length >= 4) { UInt32 k = BitConverter.ToUInt32(data, currentIndex); k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; currentIndex += 4; length -= 4; } switch (length) { case 3: h ^= BitConverter.ToUInt16(data, currentIndex); h ^= (UInt32)data[currentIndex + 2] << 16; h *= m; break; case 2: h ^= BitConverter.ToUInt16(data, currentIndex); h *= m; break; case 1: h ^= data[currentIndex]; h *= m; break; default: break; } // Do a few final mixes of the hash to ensure the last few // bytes are well-incorporated. h ^= h >> 13; h *= m; h ^= h >> 15; return h; } }
I've applied the same optimalizations as discussed with SuperFastHash so here is the fastest no-hacks managed implementation.
public class MurmurHash2InlineBitConverter : IHashAlgorithm { public UInt32 Hash(Byte[] data) { return Hash(data, 0xc58f1a7b); } const UInt32 m = 0x5bd1e995; const Int32 r = 24; public UInt32 Hash(Byte[] data, UInt32 seed) { Int32 length = data.Length; if (length == 0) return 0; UInt32 h = seed ^ (UInt32)length; Int32 currentIndex = 0; while (length >= 4) { UInt32 k = (UInt32)(data[currentIndex++] | data[currentIndex++] << 8 | data[currentIndex++] << 16 | data[currentIndex++] << 24); k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; length -= 4; } switch (length) { case 3: h ^= (UInt16)(data[currentIndex++] | data[currentIndex++] << 8); h ^= (UInt32)(data[currentIndex] << 16); h *= m; break; case 2: h ^= (UInt16)(data[currentIndex++] | data[currentIndex] << 8); h *= m; break; case 1: h ^= data[currentIndex]; h *= m; break; default: break; } // Do a few final mixes of the hash to ensure the last few // bytes are well-incorporated. h ^= h >> 13; h *= m; h ^= h >> 15; return h; } }
The dirty hack which I’ve already discussed worked miracles here as well. I've also added a different looping logic (stolen from SuperFastHash), this added a nice speed increase for the unsafe version.
public class MurmurHash2Unsafe : IHashAlgorithm { public UInt32 Hash(Byte[] data) { return Hash(data, 0xc58f1a7b); } const UInt32 m = 0x5bd1e995; const Int32 r = 24; public unsafe UInt32 Hash(Byte[] data, UInt32 seed) { Int32 length = data.Length; if (length == 0) return 0; UInt32 h = seed ^ (UInt32)length; Int32 remainingBytes = length & 3; // mod 4 Int32 numberOfLoops = length >> 2; // div 4 fixed (byte* firstByte = &(data[0])) { UInt32* realData = (UInt32*)firstByte; while (numberOfLoops != 0) { UInt32 k = *realData; k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; numberOfLoops--; realData++; } switch (remainingBytes) { case 3: h ^= (UInt16)(*realData); h ^= ((UInt32)(*(((Byte*)(realData)) + 2))) << 16; h *= m; break; case 2: h ^= (UInt16)(*realData); h *= m; break; case 1: h ^= *((Byte*)realData); h *= m; break; default: break; } } // Do a few final mixes of the hash to ensure the last few // bytes are well-incorporated. h ^= h >> 13; h *= m; h ^= h >> 15; return h; } }
Measurements
I've implemented the same test case for the native version of SuperFastHash and MurmurHash2, the measured speed will be used as reference speed. SuperFastHash was clocked at a rate of 1611 MB/s and MurmurHash2 was clocked at 2312 MB/s.
I've based the tests on the speed test used on the MurmurHash2 page, I'm not sure they test every property of the hash function, but it's a nice way to compare the performance.
var data = new Byte[256 * 1024]; new Random().NextBytes(data); Thread.CurrentThread.Priority = ThreadPriority.Highest; Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.RealTime; if (Environment.ProcessorCount > 1) { Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(1 << (Environment.ProcessorCount - 1)); } foreach (var testSubject in toTest) { Stopwatch timer = Stopwatch.StartNew(); for (int i = 0; i < 9999; i++) { testSubject.Value.Hash(data); } timer.Stop(); Console.WriteLine("{0}:\t\t{1:F2} MB/s ({2})", testSubject.Key, (data.Length * (1000.0 / (timer.ElapsedMilliseconds / 9999.0))) / (1024.0 * 1024.0), timer.ElapsedMilliseconds); }
The test is pretty simple, test 256k random data 9999 times and extract the MB/s from it. (A test with 1k random data 99999 times showed the same speeds, so my implementations are stable enough). Below are the results for the different c# implementations.
| Function | Speed | Relative to native |
|---|---|---|
| SuperFastHashSimple | 281 MB/s | 0.17x |
| SuperFastHashInlineBitConverter | 780 MB/s | 0.48x |
| SuperFastHashUInt16Hack | 1204 MB/s | 0.75x |
| SuperFastHashUnsafe | 1308 MB/s | 0.82x |
| MurmurHash2Simple | 486 MB/s | 0.21x |
| MurmurHash2InlineBitConverter | 759 MB/s | 0.32x |
| MurmurHash2UInt32Hack | 1430 MB/s | 0.62x |
| MurmurHash2Unsafe | 2196 MB/s | 0.95x |
In conclusion the managed SuperFastHash implementation is only 25% slower than the unmanaged implementation, and if you really like speed you can get the Unsafe implementation at only 18% slower than unmanged. The MurmurHash2 managed implementation is 38% slower than the unmanaged (but still as fast as the unmanaged SuperFastHash) and the unsafe implementation is only 5% slower than the unmanaged version, I call that a nice result!
Final code
Here is the complete unit with all the above functions, as always you can also download it directly.
IHashingAlgorithm.cs
using System; namespace HashTableHashing { public interface IHashAlgorithm { UInt32 Hash(Byte[] data); } public interface ISeededHashAlgorithm : IHashAlgorithm { UInt32 Hash(Byte[] data, UInt32 seed); } }
SuperFastHash.cs
/***** BEGIN LICENSE BLOCK ***** * Version: MPL 1.1/GPL 2.0/LGPL 2.1 * * The contents of this file are subject to the Mozilla Public License Version * 1.1 (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * http://www.mozilla.org/MPL/ * * Software distributed under the License is distributed on an "AS IS" basis, * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License * for the specific language governing rights and limitations under the * License. * * The Original Code is HashTableHashing.SuperFastHash. * * The Initial Developer of the Original Code is * Davy Landman. * Portions created by the Initial Developer are Copyright (C) 2009 * the Initial Developer. All Rights Reserved. * * Contributor(s): * * * Alternatively, the contents of this file may be used under the terms of * either the GNU General Public License Version 2 or later (the "GPL"), or * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), * in which case the provisions of the GPL or the LGPL are applicable instead * of those above. If you wish to allow use of your version of this file only * under the terms of either the GPL or the LGPL, and not to allow others to * use your version of this file under the terms of the MPL, indicate your * decision by deleting the provisions above and replace them with the notice * and other provisions required by the GPL or the LGPL. If you do not delete * the provisions above, a recipient may use your version of this file under * the terms of any one of the MPL, the GPL or the LGPL. * * ***** END LICENSE BLOCK ***** */ using System; using System.Runtime.InteropServices; namespace HashTableHashing { public class SuperFastHashSimple : IHashAlgorithm { public UInt32 Hash(Byte[] dataToHash) { Int32 dataLength = dataToHash.Length; if (dataLength == 0) return 0; UInt32 hash = Convert.ToUInt32(dataLength); Int32 remainingBytes = dataLength & 3; // mod 4 Int32 numberOfLoops = dataLength >> 2; // div 4 Int32 currentIndex = 0; while (numberOfLoops > 0) { hash += BitConverter.ToUInt16(dataToHash, currentIndex); UInt32 tmp = (UInt32)(BitConverter.ToUInt16(dataToHash, currentIndex + 2) << 11) ^ hash; hash = (hash << 16) ^ tmp; hash += hash >> 11; currentIndex += 4; numberOfLoops--; } switch (remainingBytes) { case 3: hash += BitConverter.ToUInt16(dataToHash, currentIndex); hash ^= hash << 16; hash ^= ((UInt32)dataToHash[currentIndex + 2]) << 18; hash += hash >> 11; break; case 2: hash += BitConverter.ToUInt16(dataToHash, currentIndex); hash ^= hash << 11; hash += hash >> 17; break; case 1: hash += dataToHash[currentIndex]; hash ^= hash << 10; hash += hash >> 1; break; default: break; } /* Force "avalanching" of final 127 bits */ hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 4; hash += hash >> 17; hash ^= hash << 25; hash += hash >> 6; return hash; } } public class SuperFastHashInlineBitConverter : IHashAlgorithm { public UInt32 Hash(Byte[] dataToHash) { Int32 dataLength = dataToHash.Length; if (dataLength == 0) return 0; UInt32 hash = (UInt32)dataLength; Int32 remainingBytes = dataLength & 3; // mod 4 Int32 numberOfLoops = dataLength >> 2; // div 4 Int32 currentIndex = 0; while (numberOfLoops > 0) { hash += (UInt16)(dataToHash[currentIndex++] | dataToHash[currentIndex++] << 8); UInt32 tmp = (UInt32)((UInt32)(dataToHash[currentIndex++] | dataToHash[currentIndex++] << 8) << 11) ^ hash; hash = (hash << 16) ^ tmp; hash += hash >> 11; numberOfLoops--; } switch (remainingBytes) { case 3: hash += (UInt16)(dataToHash[currentIndex++] | dataToHash[currentIndex++] << 8); hash ^= hash << 16; hash ^= ((UInt32)dataToHash[currentIndex]) << 18; hash += hash >> 11; break; case 2: hash += (UInt16)(dataToHash[currentIndex++] | dataToHash[currentIndex] << 8); hash ^= hash << 11; hash += hash >> 17; break; case 1: hash += dataToHash[currentIndex]; hash ^= hash << 10; hash += hash >> 1; break; default: break; } /* Force "avalanching" of final 127 bits */ hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 4; hash += hash >> 17; hash ^= hash << 25; hash += hash >> 6; return hash; } } public class SuperFastHashUInt16Hack : IHashAlgorithm { [StructLayout(LayoutKind.Explicit)] // no guarantee this will remain working struct BytetoUInt16Converter { [FieldOffset(0)] public Byte[] Bytes; [FieldOffset(0)] public UInt16[] UInts; } public UInt32 Hash(Byte[] dataToHash) { Int32 dataLength = dataToHash.Length; if (dataLength == 0) return 0; UInt32 hash = (UInt32)dataLength; Int32 remainingBytes = dataLength & 3; // mod 4 Int32 numberOfLoops = dataLength >> 2; // div 4 Int32 currentIndex = 0; UInt16[] arrayHack = new BytetoUInt16Converter { Bytes = dataToHash }.UInts; while (numberOfLoops > 0) { hash += arrayHack[currentIndex++]; UInt32 tmp = (UInt32)(arrayHack[currentIndex++] << 11) ^ hash; hash = (hash << 16) ^ tmp; hash += hash >> 11; numberOfLoops--; } currentIndex *= 2; // fix the length switch (remainingBytes) { case 3: hash += (UInt16)(dataToHash[currentIndex++] | dataToHash[currentIndex++] << 8); hash ^= hash << 16; hash ^= ((UInt32)dataToHash[currentIndex]) << 18; hash += hash >> 11; break; case 2: hash += (UInt16)(dataToHash[currentIndex++] | dataToHash[currentIndex] << 8); hash ^= hash << 11; hash += hash >> 17; break; case 1: hash += dataToHash[currentIndex]; hash ^= hash << 10; hash += hash >> 1; break; default: break; } /* Force "avalanching" of final 127 bits */ hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 4; hash += hash >> 17; hash ^= hash << 25; hash += hash >> 6; return hash; } } public class SuperFastHashUnsafe : IHashAlgorithm { public unsafe UInt32 Hash(Byte[] dataToHash) { Int32 dataLength = dataToHash.Length; if (dataLength == 0) return 0; UInt32 hash = (UInt32)dataLength; Int32 remainingBytes = dataLength & 3; // mod 4 Int32 numberOfLoops = dataLength >> 2; // div 4 fixed (byte* firstByte = &(dataToHash[0])) { /* Main loop */ UInt16* data = (UInt16*)firstByte; for (; numberOfLoops > 0; numberOfLoops--) { hash += *data; UInt32 tmp = (UInt32)(*(data + 1) << 11) ^ hash; hash = (hash << 16) ^ tmp; data += 2; hash += hash >> 11; } switch (remainingBytes) { case 3: hash += *data; hash ^= hash << 16; hash ^= ((UInt32)(*(((Byte*)(data))+2))) << 18; hash += hash >> 11; break; case 2: hash += *data; hash ^= hash << 11; hash += hash >> 17; break; case 1: hash += *((Byte*)data); hash ^= hash << 10; hash += hash >> 1; break; default: break; } } /* Force "avalanching" of final 127 bits */ hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 4; hash += hash >> 17; hash ^= hash << 25; hash += hash >> 6; return hash; } } }
MurmurHash2.cs
/***** BEGIN LICENSE BLOCK ***** * Version: MPL 1.1/GPL 2.0/LGPL 2.1 * * The contents of this file are subject to the Mozilla Public License Version * 1.1 (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * http://www.mozilla.org/MPL/ * * Software distributed under the License is distributed on an "AS IS" basis, * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License * for the specific language governing rights and limitations under the * License. * * The Original Code is HashTableHashing.MurmurHash2. * * The Initial Developer of the Original Code is * Davy Landman. * Portions created by the Initial Developer are Copyright (C) 2009 * the Initial Developer. All Rights Reserved. * * Contributor(s): * * * Alternatively, the contents of this file may be used under the terms of * either the GNU General Public License Version 2 or later (the "GPL"), or * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), * in which case the provisions of the GPL or the LGPL are applicable instead * of those above. If you wish to allow use of your version of this file only * under the terms of either the GPL or the LGPL, and not to allow others to * use your version of this file under the terms of the MPL, indicate your * decision by deleting the provisions above and replace them with the notice * and other provisions required by the GPL or the LGPL. If you do not delete * the provisions above, a recipient may use your version of this file under * the terms of any one of the MPL, the GPL or the LGPL. * * ***** END LICENSE BLOCK ***** */ using System; using System.Runtime.InteropServices; namespace HashTableHashing { public class MurmurHash2Simple : ISeededHashAlgorithm { public UInt32 Hash(Byte[] data) { return Hash(data, 0xc58f1a7b); } const UInt32 m = 0x5bd1e995; const Int32 r = 24; public UInt32 Hash(Byte[] data, UInt32 seed) { Int32 length = data.Length; if (length == 0) return 0; UInt32 h = seed ^ (UInt32)length; Int32 currentIndex = 0; while (length >= 4) { UInt32 k = BitConverter.ToUInt32(data, currentIndex); k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; currentIndex += 4; length -= 4; } switch (length) { case 3: h ^= BitConverter.ToUInt16(data, currentIndex); h ^= (UInt32)data[currentIndex + 2] << 16; h *= m; break; case 2: h ^= BitConverter.ToUInt16(data, currentIndex); h *= m; break; case 1: h ^= data[currentIndex]; h *= m; break; default: break; } // Do a few final mixes of the hash to ensure the last few // bytes are well-incorporated. h ^= h >> 13; h *= m; h ^= h >> 15; return h; } } public class MurmurHash2InlineBitConverter : ISeededHashAlgorithm { public UInt32 Hash(Byte[] data) { return Hash(data, 0xc58f1a7b); } const UInt32 m = 0x5bd1e995; const Int32 r = 24; public UInt32 Hash(Byte[] data, UInt32 seed) { Int32 length = data.Length; if (length == 0) return 0; UInt32 h = seed ^ (UInt32)length; Int32 currentIndex = 0; while (length >= 4) { UInt32 k = (UInt32)(data[currentIndex++] | data[currentIndex++] << 8 | data[currentIndex++] << 16 | data[currentIndex++] << 24); k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; length -= 4; } switch (length) { case 3: h ^= (UInt16)(data[currentIndex++] | data[currentIndex++] << 8); h ^= (UInt32)(data[currentIndex] << 16); h *= m; break; case 2: h ^= (UInt16)(data[currentIndex++] | data[currentIndex] << 8); h *= m; break; case 1: h ^= data[currentIndex]; h *= m; break; default: break; } // Do a few final mixes of the hash to ensure the last few // bytes are well-incorporated. h ^= h >> 13; h *= m; h ^= h >> 15; return h; } } public class MurmurHash2UInt32Hack : ISeededHashAlgorithm { public UInt32 Hash(Byte[] data) { return Hash(data, 0xc58f1a7b); } const UInt32 m = 0x5bd1e995; const Int32 r = 24; [StructLayout(LayoutKind.Explicit)] struct BytetoUInt32Converter { [FieldOffset(0)] public Byte[] Bytes; [FieldOffset(0)] public UInt32[] UInts; } public UInt32 Hash(Byte[] data, UInt32 seed) { Int32 length = data.Length; if (length == 0) return 0; UInt32 h = seed ^ (UInt32)length; Int32 currentIndex = 0; // array will be length of Bytes but contains Uints // therefore the currentIndex will jump with +1 while length will jump with +4 UInt32[] hackArray = new BytetoUInt32Converter { Bytes = data }.UInts; while (length >= 4) { UInt32 k = hackArray[currentIndex++]; k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; length -= 4; } currentIndex *= 4; // fix the length switch (length) { case 3: h ^= (UInt16)(data[currentIndex++] | data[currentIndex++] << 8); h ^= (UInt32)data[currentIndex] << 16; h *= m; break; case 2: h ^= (UInt16)(data[currentIndex++] | data[currentIndex] << 8); h *= m; break; case 1: h ^= data[currentIndex]; h *= m; break; default: break; } // Do a few final mixes of the hash to ensure the last few // bytes are well-incorporated. h ^= h >> 13; h *= m; h ^= h >> 15; return h; } } public class MurmurHash2Unsafe : ISeededHashAlgorithm { public UInt32 Hash(Byte[] data) { return Hash(data, 0xc58f1a7b); } const UInt32 m = 0x5bd1e995; const Int32 r = 24; public unsafe UInt32 Hash(Byte[] data, UInt32 seed) { Int32 length = data.Length; if (length == 0) return 0; UInt32 h = seed ^ (UInt32)length; Int32 remainingBytes = length & 3; // mod 4 Int32 numberOfLoops = length >> 2; // div 4 fixed (byte* firstByte = &(data[0])) { UInt32* realData = (UInt32*)firstByte; while (numberOfLoops != 0) { UInt32 k = *realData; k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; numberOfLoops--; realData++; } switch (remainingBytes) { case 3: h ^= (UInt16)(*realData); h ^= ((UInt32)(*(((Byte*)(realData)) + 2))) << 16; h *= m; break; case 2: h ^= (UInt16)(*realData); h *= m; break; case 1: h ^= *((Byte*)realData); h *= m; break; default: break; } } // Do a few final mixes of the hash to ensure the last few // bytes are well-incorporated. h ^= h >> 13; h *= m; h ^= h >> 15; return h; } } }
Tags: c#, optimization
Adding StructureMaps Registry functionality and a static wrapper to Unity
23 February 2009
A static (singleton) wrapper for unity
Most IoC containers allow to write statements such as IoC.Resolve<ILogger>() but for Unity the P&P team wanted support for multiple containers existing next to each other, which in large systems might be a good solution but for smaller systems is just a hassle to pass around the reference to the container. So you’ll see a lot of IoC.Instance.Resolve<ILogger>() singleton’s being created, in my opinion the .Instance. is a bit ugly and redundant. I’d like to be able to write IoC.Resolve<ILogger>(), so I had to create a static class IoC and add static methods to wrap the unity container. Below is my wrapper code.
/***** BEGIN LICENSE BLOCK ***** * Version: MPL 1.1/GPL 2.0/LGPL 2.1 * * The contents of this file are subject to the Mozilla Public License Version * 1.1 (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * http://www.mozilla.org/MPL/ * * Software distributed under the License is distributed on an "AS IS" basis, * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License * for the specific language governing rights and limitations under the * License. * * The Original Code is Unity.Single.IoC. * * The Initial Developer of the Original Code is * Davy Landman. * Portions created by the Initial Developer are Copyright (C) 2009 * the Initial Developer. All Rights Reserved. * * Contributor(s): * * * Alternatively, the contents of this file may be used under the terms of * either the GNU General Public License Version 2 or later (the "GPL"), or * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), * in which case the provisions of the GPL or the LGPL are applicable instead * of those above. If you wish to allow use of your version of this file only * under the terms of either the GPL or the LGPL, and not to allow others to * use your version of this file under the terms of the MPL, indicate your * decision by deleting the provisions above and replace them with the notice * and other provisions required by the GPL or the LGPL. If you do not delete * the provisions above, a recipient may use your version of this file under * the terms of any one of the MPL, the GPL or the LGPL. * * ***** END LICENSE BLOCK ***** */ using System; using System.Collections.Generic; using Microsoft.Practices.Unity; namespace Unity.Single { /// <include file='IoCComments.xml' path='doc/members/member[@name="T:Unity.Single.IoC"]/*'/> public sealed class IoC { #region Lazy-Singleton private IoC() { } private static IUnityContainer instance { get { return Nested.instance; } } class Nested { static Nested() { } internal static readonly IUnityContainer instance = new UnityContainer(); } #endregion #region IoC Wrapper functions /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.BuildUp``1(``0)"]/*'/> public static T BuildUp<T>(T existing) { return instance.BuildUp<T>(existing); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.BuildUp``1(``0,System.String)"]/*'/> public static T BuildUp<T>(T existing, string name) { return instance.BuildUp<T>(existing, name); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.BuildUp(System.Type,System.Object)"]/*'/> public static object BuildUp(Type t, object existing) { return instance.BuildUp(t, existing); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.BuildUp(System.Type,System.Object,System.String)"]/*'/> public static object BuildUp(Type t, object existing, string name) { return instance.BuildUp(t, existing, name); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Resolve``1"]/*'/> public static T Resolve<T>() { return instance.Resolve<T>(); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Resolve``1(System.String)"]/*'/> public static T Resolve<T>(string name) { return instance.Resolve<T>(name); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Resolve(System.Type)"]/*'/> public static object Resolve(Type t) { return instance.Resolve(t); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Resolve(System.Type,System.String)"]/*'/> public static object Resolve(Type t, string name) { return instance.Resolve(t, name); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.ResolveAll``1"]/*'/> public static IEnumerable<T> ResolveAll<T>() { return instance.ResolveAll<T>(); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.ResolveAll(System.Type)"]/*'/> public static IEnumerable<object> ResolveAll(Type t) { return instance.ResolveAll(t); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Teardown(System.Object)"]/*'/> public static void Teardown(object o) { instance.Teardown(o); } #endregion /// <summary> /// Configure the IoC /// </summary> public static class Configure { /// <summary> /// Configure the IoC using by calling the supplied configurator. /// </summary> /// <typeparam name="TConfigurator">The configurator to use</typeparam> public static void From<TConfigurator>() where TConfigurator : IUnityContainerConfigurator, new() { From(new TConfigurator()); } /// <summary> /// Configure the IoC using by calling the supplied configurator. /// </summary> /// <param name="configurationInterface">The configurator instance to use</param> public static void From(IUnityContainerConfigurator configurationInterface) { configurationInterface.Configure(instance); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterInstance``1(``0)"]/*'/> public static IUnityContainer RegisterInstance<TInterface>(TInterface instance) { return IoC.instance.RegisterInstance<TInterface>(instance); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterInstance``1(System.String,``0)"]/*'/> public static IUnityContainer RegisterInstance<TInterface>(string name, TInterface instance) { return IoC.instance.RegisterInstance<TInterface>(name, instance); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterInstance(System.Type,System.Object)"]/*'/> public static IUnityContainer RegisterInstance(Type t, object instance) { return IoC.instance.RegisterInstance(t, instance); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterInstance``1(``0,Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterInstance<TInterface>(TInterface instance, LifetimeManager lifetimeManager) { return IoC.instance.RegisterInstance<TInterface>(instance, lifetimeManager); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterInstance``1(System.String,``0,Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterInstance<TInterface>(string name, TInterface instance, LifetimeManager lifetimeManager) { return IoC.instance.RegisterInstance<TInterface>(name, instance, lifetimeManager); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterInstance(System.Type,System.Object,Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterInstance(Type t, object instance, LifetimeManager lifetimeManager) { return IoC.instance.RegisterInstance(t, instance, lifetimeManager); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterInstance(System.Type,System.String,System.Object)"]/*'/> public static IUnityContainer RegisterInstance(Type t, string name, object instance) { return IoC.instance.RegisterInstance(t, name, instance); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterInstance(System.Type,System.String,System.Object,Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterInstance(Type t, string name, object instance, LifetimeManager lifetime) { return IoC.instance.RegisterInstance(t, name, instance, lifetime); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType``2"]/*'/> public static IUnityContainer RegisterType<TFrom, TTo>() where TTo : TFrom { return instance.RegisterType<TFrom, TTo>(); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType``1(Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterType<T>(LifetimeManager lifetimeManager) { return instance.RegisterType<T>(lifetimeManager); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType``2(Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterType<TFrom, TTo>(LifetimeManager lifetimeManager) where TTo : TFrom { return instance.RegisterType<TFrom, TTo>(lifetimeManager); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType``2(System.String)"]/*'/> public static IUnityContainer RegisterType<TFrom, TTo>(string name) where TTo : TFrom { return instance.RegisterType<TFrom, TTo>(name); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType``1(System.String,Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterType<T>(string name, LifetimeManager lifetimeManager) { return instance.RegisterType<T>(name, lifetimeManager); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType``2(System.String,Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterType<TFrom, TTo>(string name, LifetimeManager lifetimeManager) where TTo : TFrom { return instance.RegisterType<TFrom, TTo>(name, lifetimeManager); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType(System.Type,Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterType(Type t, LifetimeManager lifetimeManager) { return instance.RegisterType(t, lifetimeManager); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType(System.Type,System.Type)"]/*'/> public static IUnityContainer RegisterType(Type from, Type to) { return instance.RegisterType(from, to); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType(System.Type,System.String,Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterType(Type t, string name, LifetimeManager lifetimeManager) { return instance.RegisterType(t, name, lifetimeManager); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType(System.Type,System.Type,Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterType(Type from, Type to, LifetimeManager lifetimeManager) { return instance.RegisterType(from, to, lifetimeManager); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType(System.Type,System.Type,System.String)"]/*'/> public static IUnityContainer RegisterType(Type from, Type to, string name) { return instance.RegisterType(from, to, name); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Configure.RegisterType(System.Type,System.Type,System.String,Microsoft.Practices.Unity.LifetimeManager)"]/*'/> public static IUnityContainer RegisterType(Type from, Type to, string name, LifetimeManager lifetimeManager) { return instance.RegisterType(from, to, name, lifetimeManager); } } public static class Enterprise { /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Enterprise.AddExtension(Microsoft.Practices.Unity.UnityContainerExtension)"]/*'/> public static IUnityContainer AddExtension(UnityContainerExtension extension) { return instance.AddExtension(extension); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Enterprise.AddNewExtension``1"]/*'/> public static IUnityContainer AddNewExtension<TExtension>() where TExtension : UnityContainerExtension, new() { return instance.AddNewExtension<TExtension>(); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Enterprise.Configure``1"]/*'/> public static TConfigurator Configure<TConfigurator>() where TConfigurator : IUnityContainerExtensionConfigurator { return instance.Configure<TConfigurator>(); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Enterprise.Configure(System.Type)"]/*'/> public static object Configure(Type configurationInterface) { return instance.Configure(configurationInterface); } /// <include file='IoCComments.xml' path='doc/members/member[@name="M:Unity.Single.IoC.Enterprise.CreateChildContainer"]/*'/> public static IUnityContainer CreateChildContainer() { return instance.CreateChildContainer(); } } } /// <summary> /// An interface which must be implemented to create a configurator class for the UnityContainer. /// </summary> public interface IUnityContainerConfigurator { /// <summary> /// This method will be called to actually configure the container. /// </summary> /// <param name="destination">The container to configure.</param> void Configure(IUnityContainer destination); } }
The XML comments are in a separate file because they are from unity which has a MsPL which is not compliant with the license I’ve chosen, separating them also reduces the documentation clutter. Just place the comment file in the same directory as the source (which can also be downloaded directly).
I’ve divided the functions in three parts: basic stuff (Resolving and Building), configuration and more Enterprisy (really not fond of the name, if someone knows a better name please do tell) functionality. Below is a sample of the usage of this IoC wrapper.
using System; using Unity.Single; namespace TestApplication { public interface ILogger { void Write(string message); } public class Logger1 : ILogger { public void Write(string message) { Console.Write("Logger1: {0}", message); } } public class Logger2 : ILogger { public void Write(string message) { Console.Write("Logger2: {0}", message); } } class Program { static void Main(string[] args) { IoC.Configure.RegisterType<ILogger, Logger1>(); IoC.Resolve<ILogger>().Write("First call"); Console.WriteLine(); IoC.Configure.RegisterType<ILogger, Logger2>(); IoC.Resolve<ILogger>().Write("Second call"); Console.ReadLine(); } } }
StructureMaps Registry functionality
I’ve used StructureMap for a few private projects and I really like the Registry DSL, Unity also has a DSL to do the configuration but doesn’t offer the opportunity to group the configuration in separate units of configuration as StructureMaps Registry class does. This will decrease the complexity in your application initialization, the wire-up code does not need to know which Repository should be used for the IRepository interface. The architecture just offers a default configuration for the repositories and the wire-up code passes that configuration to the IoC container. I’ve created a interface which should be implemented to be a configurator. And that just it. I’ve extracted the relevant code below.
/// <summary> /// An interface which must be implemented to create a configurator class for the UnityContainer. /// </summary> public interface IUnityContainerConfigurator { /// <summary> /// This method will be called to actually configure the container. /// </summary> /// <param name="destination">The container to configure.</param> void Configure(IUnityContainer destination); } /// <summary> /// Configure the IoC /// </summary> public static class Configure { /// <summary> /// Configure the IoC using by calling the supplied configurator. /// </summary> /// <typeparam name="TConfigurator">The configurator to use</typeparam> public static void From<TConfigurator>() where TConfigurator : IUnityContainerConfigurator, new() { From(new TConfigurator()); } /// <summary> /// Configure the IoC using by calling the supplied configurator. /// </summary> /// <param name="configurationInterface">The configurator instance to use</param> public static void From(IUnityContainerConfigurator configurationInterface) { configurationInterface.Configure(instance); } }
Below is an example usage of this. The build-up application does not need to know which repository to map to the IProductRepository, it leaves that responsibility to the Architecture itself. You can even hide the real Repository implementation because the mapping is done inside the same namespace.
namespace TestApplication.Contract { // very simple repository public interface IRepository<T> { T Get(Int32 id); void Add(T newEntity); IEnumerable<T> List(); } public interface IProductRepository : IRepository<Product> { // simple example IEnumerable<Product> ListCheaperThan(Decimal maximumPrice); } public interface IEmail { Boolean Send(MailMessage message); } } namespace TestApplication.Architecture.EntityFramework { using TestApplication.Contract; using Unity.Single; class Repository<T> : IRepository<T> { protected ObjectContext<T> context; public Repository () { context = new ObjectContext<T>(); } #region IRepository<T> Members public T Get(int id) { return context.RetrieveById(id); } public void Add(T newEntity) { context.Insert(newEntity); } public IEnumerable<T> List() { return context.EntitySet; } #endregion } class ProductRepository : Repository<Product>, IProductRepository { #region IProductRepository Members public IEnumerable<Product> ListCheaperThan(decimal maximumPrice) { return context.EntitySet.Where(prod => prod.Price < maximumPrice); } #endregion } public class DefaultConfiguration : IUnityContainerConfigurator { public void Configure(Microsoft.Practices.Unity.IUnityContainer destination) { destination.RegisterType<IProductRepository, ProductRepository>(); } } } namespace TestApplication.WebInterface { using Unity.Single; using TestApplication.Contract; using TestApplication.Architecture.EntityFramework; class ASPMailer : IEmail { public bool Send(System.Net.Mail.MailMessage message) { throw new System.NotImplementedException(); } } public class Application { public void Startup() { IoC.Configure.From<DefaultConfiguration>(); IoC.Configure.RegisterType<IEmail, ASPMailer>(); } } }
Have fun :)
Tags: architecture, c#, Design Pattern
