Adding profiling code from Joaqin M Lopez Munos blog (http://bannalia.blogspot.de/2014/01/a-better-hash-table-clang.html) and doing some small maintenance work to make my code faster. It needs more invasive surgery though to fix the bad performance, which I will start on after this commit.
sherwood_map now caches the distance to the initial bucket for a given entry to make it faster to determine when to stop iterating. I also tried implementing a version that uses powers of two for bucket counts instead of prime numbers, but it's very easy to come up with situations where it performs badly, so I will remove it again. Powers of two are much faster if you have random data, but if you have random data multiplied by 16 (for example pointers which are often 16 byte aligned) then it performs worse than prime numbers.
Attempted to optimize by storing more information about the buckets. It doesn't really make the code faster though so I'll back this out. Also this is not finished: erase() is currently n^2 with number of elements erased. So I'll go back to the previous version and try to optimize in a different way.
More fruitless optimization attempts. I'll go back to the version where I store more information and try ot optimize that one again.
This is finally a state that I am happy with. It's pretty damn fast and I will upload this. There is only one minor annoyance: Range erase and range insert are O(n^2) in the number of conflicting elements. Meaning if a lot of elements would end up in the same bucket those functions all of a sudden become very slow. This will pretty much only happen if you are actually preparing data to specifically cause bucket conflicts, but I think that I can fix this at least for the range erase function. Not sure if it is worth it because this will be pretty rare, and the state handling in the erase function is what killed me the last time that I tried this approach.
I decided to use the one-array version (thin_sherwood_map) after all because it's faster for successful lookups than the two-array version (fat_sherwood_map). And I want lookups to be fast.