Performance
Performance matters! Otherwise we would all be using MD5 and SHA-1 instead of trying out supposedly fast, supposedly good
hash functions. Performance numbers are fairly hard to come across, and, from everything I have found up to this point, never representative of
anything other than a very specific situation.
Methodology
- Hash functions are called inline and statically, not with function pointers! I would do pure inlining, but the Murmur hash functions can
paradoxically be faster when statically called vs inlining. The fastest time between both methods is reported.
- Hash functions are marked fastcall when appropriate.
- A variety of key sizes are tested, not just a large fixed size. For smaller key sizes, the values are random within a specified
range to simulate hashing variable-length keys. The smaller keys are where inlining becomes important, and hash functions which are speed demons
on very long stretches may not do as well on short ones.
- The length of the keys to hash are read from an array, not hardcoded. Compilers can optimize the hash functions for a hardcoded length and give
highly bogus results.
- An 8mb buffer is walked through for the keys, and keys are aligned to 4 byte boundaries inside the buffer. Unaligned access is safe on x86, but it
is a touch slower and if you are worried about speed, you are not hashing unaligned buffers. All memory allocators allocate on at least 4 byte boundaries,
so there is no reason to assume keys will not be.
- Timings are taken using rdtsc (I don't have any non-x86 machines to work with) and reported in terms of cycles per byte. Each pass of the keys
is done over the 8mb buffer 96 times for each hash function (inline and statically called), and the lowest time is reported.
Even with testing being as detailed as it is, there is still some variance that can show up when you tweak the parameters: Don't increase the key position over
the 8mb buffer and the results change; increase the byte boundary the key is on (4, 16, 32, 64, etc) and the results change; alter the variable sizes of the keys to hash
and the results change; call with a function pointer / virtual function and the results change; etc, etc. That said, I hope the chosen settings cover enough ground for this
not to matter.
Source Code
hashspeed.zip is (mostly) self-contained so there is no need for other files. Project settings in Visual Studio are setting everything to
fast/any suitable/omit frame pointers.
gcc/icc are "g++ hashspeed[32/64].cpp -O3 -o hashspeed" with the appropriate specifiers for the target CPU. Default output is a .csv with the cycles per byte for each hash/test and the compiler version and cpu identifer.
Performance Graphs
Each graph represents a single system/compiler combination. Hash functions are sorted left to right based on the lowest combined time for all tests for that
combination.
The combination format is [Processor Brand String], [Compiler Version], [System Bits].
CPU speeds may differ from the brand strings, I will need to see if the work to find actual speeds is relevant or not.
32 bits
- Pentium(R) Dual-Core CPU E5200 @ 2.50GHz, gcc 4.3.2, 32 bit
- Pentium(R) Dual-Core CPU E5200 @ 2.50GHz, icc 10.0, 32 bit
- Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz, gcc 4.3.3, 64 bit
- Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz, icc 11.1, 64 bit
- Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz, MSVC 2005, 32 bit
- Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz, MSVC 2010, 32 bit
- Intel(R) Pentium(R) D CPU 2.80GHz, gcc 4.3.2, 32 bit
- Intel(R) Pentium(R) D CPU 2.80GHz, icc 10.0, 32 bit
- Performance Averages
64 bits
Pentium(R) Dual-Core CPU E5200 @ 2.50GHz, gcc 4.3.2, 32 bit
Pentium(R) Dual-Core CPU E5200 @ 2.50GHz, icc 10.0, 32 bit
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz, gcc 4.3.3, 64 bit
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz, icc 11.1, 64 bit
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz, MSVC 2005, 32 bit
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz, MSVC 2010, 32 bit
Intel(R) Pentium(R) D CPU 2.80GHz, gcc 4.3.2, 32 bit
Intel(R) Pentium(R) D CPU 2.80GHz, icc 10.0, 32 bit
32 Bits Performance Averages
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz, gcc 4.3.3, 64 bit
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz, icc 11.1, 64 bit
64 Bits Performance Averages