Hello folks,<div><br></div><div>TL;DR: This is my proposed hashing interface based on a proposed standard hashing interface. It also is implemented with a much faster and higher quality algorithm than the current one. This is an *early draft* of the code, looking for initial feedback.</div>
<div><br></div><div><br></div><div>There has been recent interest in improving the quality and consistency of LLVM's approach to hashing. In particular, getting a single API and a high quality implementation in one place that other parts of the codebase can use to hash custom data structures. As it happens, Jeffrey Yasskin and I have been working on a proposal with similar goals to the the C++ standard library[1].</div>
<div><br></div><div>----</div><div>API concerns</div><div><br></div><div>This interface is a bit heavyweight for LLVM's needs alone. It was designed with the input of Matt Austern, and two hashing experts, Geoff Pike and Austin Appleby, to be as easy to use and simple for user-defined types as possible, while composing cleanly with the STL and other C++ standard library concepts.</div>
<div><br></div><div>That said, we are working actively on getting this (quite possibly modified during the process) into the standard, and so it seems reasonable to just implement what we expect people to have available with their standard library. I'm planning to continue working on this, and hope to contribute it to libc++ to implement the proposed library extension when appropriate (both the code is sufficiently mature, and the committee/Howard is happy with the state of the interface).</div>
<div><br></div><div>The attached implementation is, I must emphasize, an early draft. I'm mostly looking for feedback, thoughts, concerns, etc. In particular, I'm not satisfied with the organization of the header file. There are a *lot* of implementation details. Ideas on the best organization welcome, otherwise I'll try to forward declare and shuffle the user-facing functions to at least be declared toward the top.</div>
<div><br></div><div>Howard, high-level feedback from you would be particularly appreciated as I would love to contribute this to libc++ when the time is right.</div><div><br></div><div>I'm hoping to package up tests and convert clients to the new interface tomorrow.</div>
<div><br></div><div>----</div><div>Implementation concerns</div><div><br></div><div>The current hashing implementation simply isn't high-enough quality. I'm working on extensive quality testing reports using the SMHasher test suite which uses a large number of keysets known to cause problems for real-world hashing algorithms in real-world applications. The current implementation is used to hash potentially long vectors of data, and so it is very likely to be subject to the collision patterns being tested for.</div>
<div><br></div><div>This isn't terribly surprising -- murmur2, the algorithm it is based upon has some known weaknesses here. Also, my testing seems to indicate some aspects of the adaptation made these significantly worse, but I'm not entirely certain. I'm still digging there.</div>
<div><br></div><div>There are now a few hashing algorithms that do significantly better in both performance and hash quality: Murmur3, CityHash, and SpookyHash. Of these, CityHash and SpookyHash are significantly faster than Murmur3, both for large keys and for very small keys.</div>
<div><br></div><div>My implementation is a variation of CityHash (the original isn't suitable for the interface) which is as high quality or higher quality, and happens to be still faster for large keys and no slower for small keys. SpookyHash is still faster for large keys, but is slower for small keys, and those dominate LLVM's (and typical application's) hash tables.</div>
<div><br></div><div>In particular the implementation I propose *scales* very well through the small (8-byte) to medium (64- to 128-byte) key space that seems not unheard of for folding sets and other LLVM data structures. For example, it should be faster than FoldingSet's current solution for 2-pointers worth of key by just a bit, but by the time there are 8-pointers worth of key, it is over 2x faster.</div>
<div><br></div><div><br></div><div>That said, I think there remain two significant implementation problems I want to solve in the near-term:</div><div>1) Performance of hashing very small keys should be better than it is. 8-bytes and smaller have room for improvement.</div>
<div>2) Performance on 32-bit hosts, ARM, and Atom hosts needs to be measured. I've not done this yet, and it may necessitate either changes to the implementation, or alternate implementations on those hosts.</div><div>
<br></div><div>Again, as I'm hoping this will be the standard hashing implementation for libc++ and others going forward, I'm planning on doing this legwork anyways.</div><div><br></div><div>I'll try to post the rest of my benchmarks and a nice chart, 32-bit benchmarks, some compile-time benchmarks of various pieces of the system, and the quality evaluation of these algorithms tomorrow.</div>
<div><br></div><div>----</div><div>1: <a href="http://www.open-std.org/Jtc1/sc22/wg21/docs/papers/2012/n3333.html">http://www.open-std.org/Jtc1/sc22/wg21/docs/papers/2012/n3333.html</a></div>