As a side issue I've been doing some work on hashing. These results were produced on Linux on 1007U/x64 CPU...
Time Hits Hash U Scatter (E) 17765 95 e3bf408c U OneAtATime (E) 24078 91 c89a1410 A RabinKarp 5840 91 8a2bee68 U RabinKarp 5867 96 f2e8958c A Bernstein 6438 96 764b8998 U Bernstein 6220 91 ed3197fc A Hseih 9464 91 f62f7790 U Hseih 9954 101 4a7dffd4 A Fnv1aMeiyan 4956 101 63b87c78 U Fnv1aMeiyan 6105 97 1ff4fd14 A CrapWow 6243 97 dea09e44 U CrapWow 6705 94 15e59b0c A Default 6589 94 8a2bee68 U Default 7178 96 f2e8958c
The A/U is if it is an aligned or unaligned implementation. The A means 32 bit alignment, U is unaligned. On x86 cpus you can do unaligned reads, and they are actually surprisingly fast. On other CPUs that would cause a fault, and there is another code path which does the alignment in software.
The (E) means that the algorithm is endian independent - generally meaning it reads data in byte order. As seen from the results it's typically 1/4 of the speed. That's not very surprising when you consider most other hashes are working with 32 bit reads, so can do 4 times as much work per iteration.
The results for 64 bit hashes...
U Scatter 17303 96 e520d643ba36f0d0 A RabinKarp 6358 96 55a767b88a2bee68 U RabinKarp 6399 96 17481ff7f2e8958c A Bernstein 6195 96 70b01560764b8998 U Bernstein 5051 91 ab135279ed3197fc A Default 6740 91 55a767b88a2bee68 U Default 7120 96 17481ff7f2e8958c
The hits column is a fairly crude measure of how many times a bucket is hit using the hash. The hash is most often used with set/maps. In my implementation these are generally power of 2 sized. Approximately take the closest larger power of 2 and double it. The hits value measures how many times a power of 2 bucket was hit. In terms of hash usage, lower is generally better.
I liked this hash function article, and was interested in improving endian independent hashing - something that will be useful for serialization. I tired OneAtATime as it recommended but the performance is terrible. The scatter algorithm is very simple - it just reads a byte does a random table lookup and mixes by rotating and xoring. It's performance was better but still pretty slow.
So I decided to see if I could use RabinKarp. I already had code which allows it to work with unaligned data. As RabinKarp works by reading int32s there needs to be byte swap on one of the endian types - I chose big endian as it's more unusual.
In terms of more general usage my actual raw data may not be in 'byte order' in memory - an array of int16s for example will already have each int16 byte swapped for the endianess of the machine.You could do the endian flip for the uint16, and then endian flip the int32 you read, but you can do it more efficiently by just doing the int32 read, and doing short swap on that. With int32 data, no swap is needed (it's already in the right order), and on int64 - you need to do a int32 swap on the int64.
It took a while to get this all to work. I also wrote code to shift around, and resize chunks of data to hash, as well as some code to reorganise memory such that a block of memory when read would appear as it would on a flipped endian machine. This was important because I don't have an easy setup for testing big endian code. I could pull out the PowerPC mac mini - but that's going to be painful :)
In conclusion I'm pleased with the reorganisation, and it's good to have code that can give good analytic results to decide which code path is best to use. That said retrospectively the work on improving endian independent hashing was probably not really worth it. It's a fairly rare code path - just something about it got in my craw. It seemed simple enough, but there are lots of annoying details when you mix arbitrary endianess/alignment/length. Hey ho.