Chandler Carruth
2012-Feb-28 11:34 UTC
[LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
Hello folks, 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. 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]. ---- API concerns 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. 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). 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. Howard, high-level feedback from you would be particularly appreciated as I would love to contribute this to libc++ when the time is right. I'm hoping to package up tests and convert clients to the new interface tomorrow. ---- Implementation concerns 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. 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. 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. 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. 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. That said, I think there remain two significant implementation problems I want to solve in the near-term: 1) Performance of hashing very small keys should be better than it is. 8-bytes and smaller have room for improvement. 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. 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. 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. ---- 1: http://www.open-std.org/Jtc1/sc22/wg21/docs/papers/2012/n3333.html -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120228/f5d1b153/attachment.html> -------------- next part -------------- ------------------------------------------------------------------------------- --- Testing bernstein (Bernstein, 32-bit) [[[ Speed Tests ]]] Bulk speed test - 262144-byte keys Alignment 0 - 0.279 bytes/cycle - 603.67 MiB/sec @ 2.268 ghz Alignment 1 - 0.279 bytes/cycle - 603.65 MiB/sec @ 2.268 ghz Alignment 2 - 0.279 bytes/cycle - 603.66 MiB/sec @ 2.268 ghz Alignment 3 - 0.279 bytes/cycle - 603.66 MiB/sec @ 2.268 ghz Alignment 4 - 0.279 bytes/cycle - 603.65 MiB/sec @ 2.268 ghz Alignment 5 - 0.279 bytes/cycle - 603.65 MiB/sec @ 2.268 ghz Alignment 6 - 0.279 bytes/cycle - 603.65 MiB/sec @ 2.268 ghz Alignment 7 - 0.279 bytes/cycle - 603.65 MiB/sec @ 2.268 ghz Small key speed test - 1-byte keys - 2.50 cycles/hash 1.10 nanos/hash Small key speed test - 2-byte keys - 4.77 cycles/hash 2.10 nanos/hash Small key speed test - 3-byte keys - 7.79 cycles/hash 3.43 nanos/hash Small key speed test - 4-byte keys - 7.78 cycles/hash 3.43 nanos/hash Small key speed test - 5-byte keys - 9.25 cycles/hash 4.07 nanos/hash Small key speed test - 6-byte keys - 12.23 cycles/hash 5.39 nanos/hash Small key speed test - 7-byte keys - 15.24 cycles/hash 6.71 nanos/hash Small key speed test - 8-byte keys - 21.45 cycles/hash 9.45 nanos/hash Small key speed test - 9-byte keys - 25.03 cycles/hash 11.03 nanos/hash Small key speed test - 10-byte keys - 28.61 cycles/hash 12.61 nanos/hash Small key speed test - 11-byte keys - 32.20 cycles/hash 14.19 nanos/hash Small key speed test - 12-byte keys - 30.35 cycles/hash 13.37 nanos/hash Small key speed test - 13-byte keys - 39.30 cycles/hash 17.32 nanos/hash Small key speed test - 14-byte keys - 42.91 cycles/hash 18.91 nanos/hash Small key speed test - 15-byte keys - 46.67 cycles/hash 20.57 nanos/hash Small key speed test - 16-byte keys - 52.23 cycles/hash 23.02 nanos/hash Small key speed test - 18-byte keys - 61.57 cycles/hash 27.14 nanos/hash Small key speed test - 20-byte keys - 66.62 cycles/hash 29.37 nanos/hash Small key speed test - 22-byte keys - 74.32 cycles/hash 32.76 nanos/hash Small key speed test - 24-byte keys - 78.95 cycles/hash 34.80 nanos/hash Small key speed test - 28-byte keys - 93.78 cycles/hash 41.34 nanos/hash Small key speed test - 32-byte keys - 108.05 cycles/hash 47.64 nanos/hash Small key speed test - 36-byte keys - 122.46 cycles/hash 53.99 nanos/hash Small key speed test - 40-byte keys - 136.66 cycles/hash 60.25 nanos/hash Small key speed test - 48-byte keys - 165.25 cycles/hash 72.85 nanos/hash Small key speed test - 56-byte keys - 193.87 cycles/hash 85.48 nanos/hash Small key speed test - 64-byte keys - 219.79 cycles/hash 96.90 nanos/hash ------------------------------------------------------------------------------- -------------- next part -------------- A non-text attachment was scrubbed... Name: Hashing.h Type: text/x-chdr Size: 27596 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120228/f5d1b153/attachment.h> -------------- next part -------------- ------------------------------------------------------------------------------- --- Testing superfast (Paul Hsieh's SuperFastHash) [[[ Speed Tests ]]] Bulk speed test - 262144-byte keys Alignment 0 - 0.558 bytes/cycle - 1206.82 MiB/sec @ 2.268 ghz Alignment 1 - 0.557 bytes/cycle - 1204.25 MiB/sec @ 2.268 ghz Alignment 2 - 0.558 bytes/cycle - 1207.09 MiB/sec @ 2.268 ghz Alignment 3 - 0.557 bytes/cycle - 1204.47 MiB/sec @ 2.268 ghz Alignment 4 - 0.558 bytes/cycle - 1206.87 MiB/sec @ 2.268 ghz Alignment 5 - 0.557 bytes/cycle - 1204.24 MiB/sec @ 2.268 ghz Alignment 6 - 0.558 bytes/cycle - 1207.08 MiB/sec @ 2.268 ghz Alignment 7 - 0.557 bytes/cycle - 1204.48 MiB/sec @ 2.268 ghz Small key speed test - 1-byte keys - 23.21 cycles/hash 10.23 nanos/hash Small key speed test - 2-byte keys - 24.10 cycles/hash 10.62 nanos/hash Small key speed test - 3-byte keys - 24.14 cycles/hash 10.64 nanos/hash Small key speed test - 4-byte keys - 25.03 cycles/hash 11.03 nanos/hash Small key speed test - 5-byte keys - 31.29 cycles/hash 13.79 nanos/hash Small key speed test - 6-byte keys - 31.24 cycles/hash 13.77 nanos/hash Small key speed test - 7-byte keys - 32.17 cycles/hash 14.18 nanos/hash Small key speed test - 8-byte keys - 32.16 cycles/hash 14.17 nanos/hash Small key speed test - 9-byte keys - 38.44 cycles/hash 16.94 nanos/hash Small key speed test - 10-byte keys - 38.49 cycles/hash 16.96 nanos/hash Small key speed test - 11-byte keys - 37.55 cycles/hash 16.55 nanos/hash Small key speed test - 12-byte keys - 39.33 cycles/hash 17.34 nanos/hash Small key speed test - 13-byte keys - 46.59 cycles/hash 20.54 nanos/hash Small key speed test - 14-byte keys - 45.61 cycles/hash 20.10 nanos/hash Small key speed test - 15-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 16-byte keys - 46.48 cycles/hash 20.49 nanos/hash Small key speed test - 18-byte keys - 55.42 cycles/hash 24.43 nanos/hash Small key speed test - 20-byte keys - 53.63 cycles/hash 23.64 nanos/hash Small key speed test - 22-byte keys - 59.88 cycles/hash 26.40 nanos/hash Small key speed test - 24-byte keys - 60.78 cycles/hash 26.79 nanos/hash Small key speed test - 28-byte keys - 67.93 cycles/hash 29.94 nanos/hash Small key speed test - 32-byte keys - 74.20 cycles/hash 32.71 nanos/hash Small key speed test - 36-byte keys - 82.23 cycles/hash 36.25 nanos/hash Small key speed test - 40-byte keys - 89.38 cycles/hash 39.40 nanos/hash Small key speed test - 48-byte keys - 98.97 cycles/hash 43.63 nanos/hash Small key speed test - 56-byte keys - 117.99 cycles/hash 52.02 nanos/hash Small key speed test - 64-byte keys - 133.12 cycles/hash 58.69 nanos/hash ------------------------------------------------------------------------------- -------------- next part -------------- ------------------------------------------------------------------------------- --- Testing llvm (LLVM Hashing) [[[ Speed Tests ]]] Bulk speed test - 262144-byte keys Alignment 0 - 0.888 bytes/cycle - 1921.36 MiB/sec @ 2.268 ghz Alignment 1 - 0.883 bytes/cycle - 1910.54 MiB/sec @ 2.268 ghz Alignment 2 - 0.883 bytes/cycle - 1910.54 MiB/sec @ 2.268 ghz Alignment 3 - 0.883 bytes/cycle - 1910.55 MiB/sec @ 2.268 ghz Alignment 4 - 0.889 bytes/cycle - 1921.82 MiB/sec @ 2.268 ghz Alignment 5 - 0.883 bytes/cycle - 1910.54 MiB/sec @ 2.268 ghz Alignment 6 - 0.883 bytes/cycle - 1910.57 MiB/sec @ 2.268 ghz Alignment 7 - 0.883 bytes/cycle - 1910.53 MiB/sec @ 2.268 ghz Small key speed test - 1-byte keys - 41.99 cycles/hash 18.51 nanos/hash Small key speed test - 2-byte keys - 42.00 cycles/hash 18.51 nanos/hash Small key speed test - 3-byte keys - 42.90 cycles/hash 18.91 nanos/hash Small key speed test - 4-byte keys - 16.77 cycles/hash 7.39 nanos/hash Small key speed test - 5-byte keys - 47.37 cycles/hash 20.88 nanos/hash Small key speed test - 6-byte keys - 47.38 cycles/hash 20.88 nanos/hash Small key speed test - 7-byte keys - 48.27 cycles/hash 21.28 nanos/hash Small key speed test - 8-byte keys - 25.93 cycles/hash 11.43 nanos/hash Small key speed test - 9-byte keys - 53.57 cycles/hash 23.61 nanos/hash Small key speed test - 10-byte keys - 53.63 cycles/hash 23.64 nanos/hash Small key speed test - 11-byte keys - 55.42 cycles/hash 24.43 nanos/hash Small key speed test - 12-byte keys - 30.39 cycles/hash 13.39 nanos/hash Small key speed test - 13-byte keys - 59.00 cycles/hash 26.01 nanos/hash Small key speed test - 14-byte keys - 58.99 cycles/hash 26.00 nanos/hash Small key speed test - 15-byte keys - 59.89 cycles/hash 26.40 nanos/hash Small key speed test - 16-byte keys - 30.18 cycles/hash 13.30 nanos/hash Small key speed test - 18-byte keys - 63.45 cycles/hash 27.97 nanos/hash Small key speed test - 20-byte keys - 39.33 cycles/hash 17.34 nanos/hash Small key speed test - 22-byte keys - 67.93 cycles/hash 29.95 nanos/hash Small key speed test - 24-byte keys - 44.70 cycles/hash 19.70 nanos/hash Small key speed test - 28-byte keys - 49.17 cycles/hash 21.68 nanos/hash Small key speed test - 32-byte keys - 52.80 cycles/hash 23.27 nanos/hash Small key speed test - 36-byte keys - 56.33 cycles/hash 24.83 nanos/hash Small key speed test - 40-byte keys - 61.67 cycles/hash 27.18 nanos/hash Small key speed test - 48-byte keys - 71.18 cycles/hash 31.38 nanos/hash Small key speed test - 56-byte keys - 93.30 cycles/hash 41.13 nanos/hash Small key speed test - 64-byte keys - 103.73 cycles/hash 45.73 nanos/hash ------------------------------------------------------------------------------- -------------- next part -------------- ------------------------------------------------------------------------------- --- Testing Murmur2A (MurmurHash2A for x86, 32-bit) [[[ Speed Tests ]]] Bulk speed test - 262144-byte keys Alignment 0 - 1.093 bytes/cycle - 2363.78 MiB/sec @ 2.268 ghz Alignment 1 - 1.005 bytes/cycle - 2173.73 MiB/sec @ 2.268 ghz Alignment 2 - 1.005 bytes/cycle - 2173.72 MiB/sec @ 2.268 ghz Alignment 3 - 1.005 bytes/cycle - 2173.82 MiB/sec @ 2.268 ghz Alignment 4 - 1.093 bytes/cycle - 2363.53 MiB/sec @ 2.268 ghz Alignment 5 - 1.005 bytes/cycle - 2174.42 MiB/sec @ 2.268 ghz Alignment 6 - 1.005 bytes/cycle - 2174.40 MiB/sec @ 2.268 ghz Alignment 7 - 1.005 bytes/cycle - 2174.42 MiB/sec @ 2.268 ghz Small key speed test - 1-byte keys - 20.53 cycles/hash 9.05 nanos/hash Small key speed test - 2-byte keys - 21.45 cycles/hash 9.45 nanos/hash Small key speed test - 3-byte keys - 22.35 cycles/hash 9.85 nanos/hash Small key speed test - 4-byte keys - 26.82 cycles/hash 11.82 nanos/hash Small key speed test - 5-byte keys - 28.61 cycles/hash 12.61 nanos/hash Small key speed test - 6-byte keys - 29.48 cycles/hash 12.99 nanos/hash Small key speed test - 7-byte keys - 29.50 cycles/hash 13.00 nanos/hash Small key speed test - 8-byte keys - 30.39 cycles/hash 13.39 nanos/hash Small key speed test - 9-byte keys - 31.28 cycles/hash 13.79 nanos/hash Small key speed test - 10-byte keys - 32.15 cycles/hash 14.17 nanos/hash Small key speed test - 11-byte keys - 32.19 cycles/hash 14.19 nanos/hash Small key speed test - 12-byte keys - 33.06 cycles/hash 14.57 nanos/hash Small key speed test - 13-byte keys - 37.54 cycles/hash 16.55 nanos/hash Small key speed test - 14-byte keys - 38.45 cycles/hash 16.95 nanos/hash Small key speed test - 15-byte keys - 39.32 cycles/hash 17.33 nanos/hash Small key speed test - 16-byte keys - 37.54 cycles/hash 16.55 nanos/hash Small key speed test - 18-byte keys - 39.33 cycles/hash 17.34 nanos/hash Small key speed test - 20-byte keys - 39.33 cycles/hash 17.34 nanos/hash Small key speed test - 22-byte keys - 42.91 cycles/hash 18.91 nanos/hash Small key speed test - 24-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 28-byte keys - 49.15 cycles/hash 21.66 nanos/hash Small key speed test - 32-byte keys - 53.63 cycles/hash 23.64 nanos/hash Small key speed test - 36-byte keys - 55.41 cycles/hash 24.43 nanos/hash Small key speed test - 40-byte keys - 60.78 cycles/hash 26.79 nanos/hash Small key speed test - 48-byte keys - 69.72 cycles/hash 30.73 nanos/hash Small key speed test - 56-byte keys - 77.20 cycles/hash 34.03 nanos/hash Small key speed test - 64-byte keys - 101.61 cycles/hash 44.80 nanos/hash ------------------------------------------------------------------------------- -------------- next part -------------- ------------------------------------------------------------------------------- --- Testing Murmur3A (MurmurHash3 for x86, 32-bit) [[[ Speed Tests ]]] Bulk speed test - 262144-byte keys Alignment 0 - 0.819 bytes/cycle - 1771.02 MiB/sec @ 2.268 ghz Alignment 1 - 0.808 bytes/cycle - 1747.14 MiB/sec @ 2.268 ghz Alignment 2 - 0.808 bytes/cycle - 1747.18 MiB/sec @ 2.268 ghz Alignment 3 - 0.808 bytes/cycle - 1747.21 MiB/sec @ 2.268 ghz Alignment 4 - 0.819 bytes/cycle - 1770.55 MiB/sec @ 2.268 ghz Alignment 5 - 0.808 bytes/cycle - 1747.06 MiB/sec @ 2.268 ghz Alignment 6 - 0.808 bytes/cycle - 1747.11 MiB/sec @ 2.268 ghz Alignment 7 - 0.808 bytes/cycle - 1747.07 MiB/sec @ 2.268 ghz Small key speed test - 1-byte keys - 27.19 cycles/hash 11.98 nanos/hash Small key speed test - 2-byte keys - 30.38 cycles/hash 13.39 nanos/hash Small key speed test - 3-byte keys - 31.31 cycles/hash 13.80 nanos/hash Small key speed test - 4-byte keys - 28.11 cycles/hash 12.39 nanos/hash Small key speed test - 5-byte keys - 33.08 cycles/hash 14.58 nanos/hash Small key speed test - 6-byte keys - 31.76 cycles/hash 14.00 nanos/hash Small key speed test - 7-byte keys - 38.44 cycles/hash 16.94 nanos/hash Small key speed test - 8-byte keys - 30.18 cycles/hash 13.30 nanos/hash Small key speed test - 9-byte keys - 38.44 cycles/hash 16.94 nanos/hash Small key speed test - 10-byte keys - 40.25 cycles/hash 17.74 nanos/hash Small key speed test - 11-byte keys - 44.75 cycles/hash 19.72 nanos/hash Small key speed test - 12-byte keys - 39.33 cycles/hash 17.33 nanos/hash Small key speed test - 13-byte keys - 41.12 cycles/hash 18.12 nanos/hash Small key speed test - 14-byte keys - 43.99 cycles/hash 19.39 nanos/hash Small key speed test - 15-byte keys - 49.16 cycles/hash 21.67 nanos/hash Small key speed test - 16-byte keys - 43.79 cycles/hash 19.30 nanos/hash Small key speed test - 18-byte keys - 51.84 cycles/hash 22.85 nanos/hash Small key speed test - 20-byte keys - 47.34 cycles/hash 20.87 nanos/hash Small key speed test - 22-byte keys - 57.21 cycles/hash 25.22 nanos/hash Small key speed test - 24-byte keys - 53.55 cycles/hash 23.60 nanos/hash Small key speed test - 28-byte keys - 58.13 cycles/hash 25.63 nanos/hash Small key speed test - 32-byte keys - 64.35 cycles/hash 28.37 nanos/hash Small key speed test - 36-byte keys - 69.72 cycles/hash 30.73 nanos/hash Small key speed test - 40-byte keys - 72.71 cycles/hash 32.05 nanos/hash Small key speed test - 48-byte keys - 82.43 cycles/hash 36.34 nanos/hash Small key speed test - 56-byte keys - 94.75 cycles/hash 41.77 nanos/hash Small key speed test - 64-byte keys - 105.47 cycles/hash 46.50 nanos/hash ------------------------------------------------------------------------------- -------------- next part -------------- ------------------------------------------------------------------------------- --- Testing City64 (Google CityHash128WithSeed) [[[ Speed Tests ]]] Bulk speed test - 262144-byte keys Alignment 0 - 2.593 bytes/cycle - 5609.20 MiB/sec @ 2.268 ghz Alignment 1 - 2.591 bytes/cycle - 5603.16 MiB/sec @ 2.268 ghz Alignment 2 - 2.591 bytes/cycle - 5603.24 MiB/sec @ 2.268 ghz Alignment 3 - 2.591 bytes/cycle - 5603.13 MiB/sec @ 2.268 ghz Alignment 4 - 2.590 bytes/cycle - 5602.73 MiB/sec @ 2.268 ghz Alignment 5 - 2.590 bytes/cycle - 5603.08 MiB/sec @ 2.268 ghz Alignment 6 - 2.591 bytes/cycle - 5603.13 MiB/sec @ 2.268 ghz Alignment 7 - 2.590 bytes/cycle - 5602.88 MiB/sec @ 2.268 ghz Small key speed test - 1-byte keys - 36.62 cycles/hash 16.14 nanos/hash Small key speed test - 2-byte keys - 36.63 cycles/hash 16.15 nanos/hash Small key speed test - 3-byte keys - 36.73 cycles/hash 16.19 nanos/hash Small key speed test - 4-byte keys - 41.12 cycles/hash 18.12 nanos/hash Small key speed test - 5-byte keys - 41.12 cycles/hash 18.12 nanos/hash Small key speed test - 6-byte keys - 41.12 cycles/hash 18.12 nanos/hash Small key speed test - 7-byte keys - 41.11 cycles/hash 18.12 nanos/hash Small key speed test - 8-byte keys - 41.12 cycles/hash 18.12 nanos/hash Small key speed test - 9-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 10-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 11-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 12-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 13-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 14-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 15-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 16-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 18-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 20-byte keys - 44.70 cycles/hash 19.70 nanos/hash Small key speed test - 22-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 24-byte keys - 42.91 cycles/hash 18.91 nanos/hash Small key speed test - 28-byte keys - 42.91 cycles/hash 18.91 nanos/hash Small key speed test - 32-byte keys - 42.91 cycles/hash 18.91 nanos/hash Small key speed test - 36-byte keys - 50.98 cycles/hash 22.47 nanos/hash Small key speed test - 40-byte keys - 51.02 cycles/hash 22.49 nanos/hash Small key speed test - 48-byte keys - 50.93 cycles/hash 22.45 nanos/hash Small key speed test - 56-byte keys - 50.96 cycles/hash 22.46 nanos/hash Small key speed test - 64-byte keys - 50.95 cycles/hash 22.46 nanos/hash ------------------------------------------------------------------------------- -------------- next part -------------- ------------------------------------------------------------------------------- --- Testing std64 (LLVM Standard-baed Hashing) [[[ Speed Tests ]]] Bulk speed test - 262144-byte keys Alignment 0 - 3.077 bytes/cycle - 6655.33 MiB/sec @ 2.268 ghz Alignment 1 - 3.048 bytes/cycle - 6591.80 MiB/sec @ 2.268 ghz Alignment 2 - 3.047 bytes/cycle - 6590.83 MiB/sec @ 2.268 ghz Alignment 3 - 3.047 bytes/cycle - 6590.68 MiB/sec @ 2.268 ghz Alignment 4 - 3.046 bytes/cycle - 6587.97 MiB/sec @ 2.268 ghz Alignment 5 - 3.046 bytes/cycle - 6588.15 MiB/sec @ 2.268 ghz Alignment 6 - 3.046 bytes/cycle - 6588.33 MiB/sec @ 2.268 ghz Alignment 7 - 3.046 bytes/cycle - 6588.16 MiB/sec @ 2.268 ghz Small key speed test - 1-byte keys - 41.99 cycles/hash 18.51 nanos/hash Small key speed test - 2-byte keys - 42.00 cycles/hash 18.51 nanos/hash Small key speed test - 3-byte keys - 42.00 cycles/hash 18.51 nanos/hash Small key speed test - 4-byte keys - 40.22 cycles/hash 17.73 nanos/hash Small key speed test - 5-byte keys - 40.21 cycles/hash 17.72 nanos/hash Small key speed test - 6-byte keys - 40.22 cycles/hash 17.73 nanos/hash Small key speed test - 7-byte keys - 40.23 cycles/hash 17.73 nanos/hash Small key speed test - 8-byte keys - 40.24 cycles/hash 17.73 nanos/hash Small key speed test - 9-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 10-byte keys - 44.70 cycles/hash 19.70 nanos/hash Small key speed test - 11-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 12-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 13-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 14-byte keys - 44.70 cycles/hash 19.70 nanos/hash Small key speed test - 15-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 16-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 18-byte keys - 50.95 cycles/hash 22.46 nanos/hash Small key speed test - 20-byte keys - 50.95 cycles/hash 22.46 nanos/hash Small key speed test - 22-byte keys - 50.95 cycles/hash 22.46 nanos/hash Small key speed test - 24-byte keys - 50.95 cycles/hash 22.46 nanos/hash Small key speed test - 28-byte keys - 50.95 cycles/hash 22.46 nanos/hash Small key speed test - 32-byte keys - 50.95 cycles/hash 22.46 nanos/hash Small key speed test - 36-byte keys - 58.75 cycles/hash 25.90 nanos/hash Small key speed test - 40-byte keys - 58.99 cycles/hash 26.01 nanos/hash Small key speed test - 48-byte keys - 58.99 cycles/hash 26.00 nanos/hash Small key speed test - 56-byte keys - 58.99 cycles/hash 26.00 nanos/hash Small key speed test - 64-byte keys - 59.00 cycles/hash 26.01 nanos/hash ------------------------------------------------------------------------------- -------------- next part -------------- ------------------------------------------------------------------------------- --- Testing spooky64 (SpookyHash 64-bit) [[[ Speed Tests ]]] Bulk speed test - 262144-byte keys Alignment 0 - 3.305 bytes/cycle - 7147.92 MiB/sec @ 2.268 ghz Alignment 1 - 3.278 bytes/cycle - 7090.76 MiB/sec @ 2.268 ghz Alignment 2 - 3.279 bytes/cycle - 7091.50 MiB/sec @ 2.268 ghz Alignment 3 - 3.278 bytes/cycle - 7091.10 MiB/sec @ 2.268 ghz Alignment 4 - 3.279 bytes/cycle - 7091.38 MiB/sec @ 2.268 ghz Alignment 5 - 3.279 bytes/cycle - 7091.71 MiB/sec @ 2.268 ghz Alignment 6 - 3.279 bytes/cycle - 7091.72 MiB/sec @ 2.268 ghz Alignment 7 - 3.278 bytes/cycle - 7090.54 MiB/sec @ 2.268 ghz Small key speed test - 1-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 2-byte keys - 45.61 cycles/hash 20.10 nanos/hash Small key speed test - 3-byte keys - 46.48 cycles/hash 20.49 nanos/hash Small key speed test - 4-byte keys - 43.80 cycles/hash 19.31 nanos/hash Small key speed test - 5-byte keys - 45.58 cycles/hash 20.09 nanos/hash Small key speed test - 6-byte keys - 47.37 cycles/hash 20.88 nanos/hash Small key speed test - 7-byte keys - 47.39 cycles/hash 20.89 nanos/hash Small key speed test - 8-byte keys - 45.57 cycles/hash 20.09 nanos/hash Small key speed test - 9-byte keys - 46.48 cycles/hash 20.49 nanos/hash Small key speed test - 10-byte keys - 47.37 cycles/hash 20.88 nanos/hash Small key speed test - 11-byte keys - 47.37 cycles/hash 20.88 nanos/hash Small key speed test - 12-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 13-byte keys - 44.69 cycles/hash 19.70 nanos/hash Small key speed test - 14-byte keys - 47.38 cycles/hash 20.88 nanos/hash Small key speed test - 15-byte keys - 48.27 cycles/hash 21.28 nanos/hash Small key speed test - 16-byte keys - 69.72 cycles/hash 30.73 nanos/hash Small key speed test - 18-byte keys - 71.25 cycles/hash 31.41 nanos/hash Small key speed test - 20-byte keys - 69.72 cycles/hash 30.73 nanos/hash Small key speed test - 22-byte keys - 71.17 cycles/hash 31.38 nanos/hash Small key speed test - 24-byte keys - 71.93 cycles/hash 31.71 nanos/hash Small key speed test - 28-byte keys - 71.14 cycles/hash 31.36 nanos/hash Small key speed test - 32-byte keys - 72.71 cycles/hash 32.05 nanos/hash Small key speed test - 36-byte keys - 71.20 cycles/hash 31.39 nanos/hash Small key speed test - 40-byte keys - 71.94 cycles/hash 31.71 nanos/hash Small key speed test - 48-byte keys - 100.11 cycles/hash 44.13 nanos/hash Small key speed test - 56-byte keys - 93.32 cycles/hash 41.14 nanos/hash Small key speed test - 64-byte keys - 99.21 cycles/hash 43.74 nanos/hash -------------------------------------------------------------------------------
Tobias Grosser
2012-Feb-28 13:35 UTC
[LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
On 02/28/2012 12:34 PM, Chandler Carruth wrote:> Hello folks, > > 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. > > > 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].Hi Chandler, I just skimmed over the proposal and it seems very interesting to me. Unfortunately I did not have time to look further into it. One point that I found surprising is that your hashing is in most cases notably faster than the old LLVM hashing, except for key sizes which are a modulo of 4. Here the existing hash function is a lot faster than your new solution. If keys that are multiple of 4 bytes are common in LLVM, it might be worth to check if this change does not cause performance regressions.> old_llvm_performance.txt > > > ------------------------------------------------------------------------------- > --- Testing llvm (LLVM Hashing) > > [[[ Speed Tests ]]] > > Small key speed test - 4-byte keys - 16.77 cycles/hash 7.39 nanos/hash > Small key speed test - 8-byte keys - 25.93 cycles/hash 11.43 nanos/hash > Small key speed test - 12-byte keys - 30.39 cycles/hash 13.39 nanos/hash > Small key speed test - 16-byte keys - 30.18 cycles/hash 13.30 nanos/hash > Small key speed test - 20-byte keys - 39.33 cycles/hash 17.34 nanos/hash > Small key speed test - 24-byte keys - 44.70 cycles/hash 19.70 nanos/hash > Small key speed test - 28-byte keys - 49.17 cycles/hash 21.68 nanos/hash> new_llvm_performance.txt > > > ------------------------------------------------------------------------------- > --- Testing std64 (LLVM Standard-baed Hashing) > > [[[ Speed Tests ]]] > > Small key speed test - 4-byte keys - 40.22 cycles/hash 17.73 nanos/hash > Small key speed test - 8-byte keys - 40.24 cycles/hash 17.73 nanos/hash > Small key speed test - 12-byte keys - 44.69 cycles/hash 19.70 nanos/hash > Small key speed test - 16-byte keys - 44.69 cycles/hash 19.70 nanos/hash > Small key speed test - 24-byte keys - 50.95 cycles/hash 22.46 nanos/hash > Small key speed test - 28-byte keys - 50.95 cycles/hash 22.46 nanos/hashCheers Tobi
Howard Hinnant
2012-Feb-28 15:20 UTC
[LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
On Feb 28, 2012, at 6:34 AM, Chandler Carruth wrote:> Howard, high-level feedback from you would be particularly appreciated as I would love to contribute this to libc++ when the time is right.Does the enclosed implementation implement this part of N3333: http://www.open-std.org/Jtc1/sc22/wg21/docs/papers/2012/n3333.html#per.process.seed ? That to me seems like potentially the most controversial part. I scanned Hashing.h but did not immediately see that support (I could've easily missed it). Howard
Chandler Carruth
2012-Feb-28 18:21 UTC
[LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
Will post an updated (and cleaned up, thanks Nadav!) patch shortly, but wanted to answer this question: On Tue, Feb 28, 2012 at 7:20 AM, Howard Hinnant <hhinnant at apple.com> wrote:> On Feb 28, 2012, at 6:34 AM, Chandler Carruth wrote: > > > Howard, high-level feedback from you would be particularly appreciated > as I would love to contribute this to libc++ when the time is right. > > Does the enclosed implementation implement this part of N3333: > > > http://www.open-std.org/Jtc1/sc22/wg21/docs/papers/2012/n3333.html#per.process.seed > > ? > > That to me seems like potentially the most controversial part. I scanned > Hashing.h but did not immediately see that support (I could've easily > missed it).This is definitely the most controversial part, and as such I've separated it out for implementation purposes. The mechanism to implement this is in place, but currently it uses a fixed large prime and has a comment about the plan to potentially switch to a per-execution seed. (see ::llvm::hashing::detail::get_execution_seed() if you're curious where) My plan was first to get the interface and implementation worked out, and then to try flipping on the per-execution seed, seeing what breaks, tracking down the places we depend on the hash-table ordering, etc. Hopefully there aren't many places, but that's something we'll learn with this. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120228/13cdce39/attachment.html>
Chandler Carruth
2012-Feb-29 09:35 UTC
[LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
Thanks for the feedback thus far! I've updated the header file, and enclosed a complete patch against LLVM. This passes all the regtests, and I'll be doing more thorough testing of LLVM itself with the patch. I've included some basic unit tests, but could probably do more here... Not sure it's worth delaying the initial submission though, as the best testing is to use a hash testing suite... I've addressed the comments from Nadav, but there may be more minor stylistic issues or typos. Please keep pointing them out! I appreciate the help there. I've also corrected my stub for the execution-seed to be more correct and to include the ability to override it during program startup. It still doesn't go the final step to make it actually change on each execution, but is now otherwise identical. (In particular, it is no longer a compile-time constant that can be folded.) This regressed the performance a tiny bit, however... There are several improvements to the implementation of the hashing algorithm itself. The way the hashing included the seed hurt performance quite a bit. I've re-worked it to be much lighter weight, and even after the execution seed fix above slowed things down, this speeds everything up more. We shave 4ns off the 4 to 8 byte case, bringing performance above that of essentially every high quality hashing algorithm... I still think we can do more, but it's already much faster than the existing LLVM one except for the issue Tobias pointed out w/ modulo-4 key sizes. I'm going to investigate this, but it may be a consequence of a weakness in that algorithm. I've re-run the SMHasher quality testing suite and the results are very good. There are a few problems identified, but these are long-known problems with CityHash in general, and have proven to thus far not be a cause of real-world issues... I'd like to fix them, but it doesn't seem a high priority yet. Finally, I've run some rough initial numbers for x86 32-bit, and it's surprisingly good. The relative speeds of this algorithm and others don't seem to change much. A bit suspicious of that, so going to do more thorough analysis. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120229/31e44981/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: Hashing.h Type: text/x-chdr Size: 28547 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120229/31e44981/attachment.h> -------------- next part -------------- A non-text attachment was scrubbed... Name: hashing.diff.gz Type: application/x-gzip Size: 13558 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120229/31e44981/attachment.bin>
Jay Foad
2012-Feb-29 10:52 UTC
[LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
On 29 February 2012 09:35, Chandler Carruth <chandlerc at google.com> wrote:> I still think we can do more, but it's already much faster than the existing LLVM one except for the issue Tobias pointed out w/ modulo-4 key sizes. I'm going to investigate thisOK, but this is a VERY big exception! Almost any non-string data anyone wants to hash will be a multiple of 4 bytes in length.> //===-- llvm/ADT/Hashing.h - Utilities for hashing --------------*- C++ -*-===//Doesn't this belong in ../Support/ ? No-one's ever explained the difference to me; I just assumed that generic data types go in ADT/ and everything else goes in Support/.> // > // The LLVM Compiler Infrastructure > // > // This file is distributed under the University of Illinois Open Source > // License. See LICENSE.TXT for details. > // > //===----------------------------------------------------------------------===// > // > // This file implements the newly proposed standard C++ interfaces for hashing > // arbitrary data and building hash functions for user-defined types. This > // interface was originally proposed in N3333[1] and is currently under review > // for inclusion in a future TR and/or standard. > // > // The primary interfaces provide are comprised of one type and three functions:"provided"> // > // -- 'hash_code' class is an opaque type representing the hash code for some > // data. It is the intended product of hashing, and can be used to implement > // hash tables, checksumming, and other common uses of hashes. It is not an > // integer type (although it can be converted to one) because it is risky > // to assume much about the internals of a hash_code. In particular, each > // execution of the program has a high probability of producing a different > // hash_code for a given input. Thus their values are not stable to save or > // persist, and should only be used during the execution for the > // construction of hashing datastructures. > // > // -- 'hash_value' is a function designed to be overloaded for each > // user-defined type which wishes to be used within a hashing context. It > // should be overloaded within the user-defined type's namespace and found via > // ADL. Overloads for primitive types are provided by this library. > // > // -- 'hash_combine' and 'hash_combine_range' are functions designed to aid > // programmers in easily and intuitively combining a set of data into a single > // hash_code for their object. They should only logically be used within the > // implementation of a 'hash_value' routine or similar context. > // > // Note that 'hash_combine_range' contains very special logic for hashing > // a contiguous array of integers or pointers. This logic is *extremely* fast, > // on a modern Intel "Gainestown" Xeon (Nehalem uarch) @2.2 GHz, these were > // benchmarked at over 8.5 GiB/s for large keys, and <20 cycles/20 cycles per what? Don't keep us in suspense!> // > //===----------------------------------------------------------------------===// > > #ifndef LLVM_ADT_HASHING_H > #define LLVM_ADT_HASHING_H > > #include "llvm/ADT/STLExtras.h" > #include "llvm/Support/DataTypes.h" > #include "llvm/Support/type_traits.h" > #include <cassert> > #include <cstring> > #include <algorithm> > #include <utility> > #include <iterator> > > namespace llvm { > > /// \brief An opaque object representing a hash code. > /// > /// This object represents the result of hashing some entity. It is intended to > /// be used to implement hashtables or other hashing-based data structures. > /// While it wraps and exposes a numeric value, this value should not be > /// trusted to be stable or predictable across processes or executions. > /// > /// In order to obtain the hash_code for an object 'x': > /// \code > /// using llvm::hash_value; > /// llvm::hash_code code = hash_value(x); > /// \endcode > /// > /// Also note that there are two numerical values which are reserved, and the > /// implementation ensures will never be produced for real hash_codes. These > /// can be used as sentinels within hashing data structures. > class hash_code { > size_t value; > > public: > /// \brief Default construct a hash_code. Constructs a null code. > hash_code() : value() {} > > /// \brief Form a hash code directly from a numerical value. > hash_code(size_t value) : value(value) {} > > /// \brief Convert the hash code to its numerical value for use. > /*explicit*/ operator size_t() const { return value; } > > /// \brief Get a hash_code object which corresponds to a null code. > /// > /// The null code must never be the result of any 'hash_value' calls and can > /// be used to detect an unset hash_code. > static hash_code get_null_code() { return 0; } > > /// \brief Get a hash_code object which corresponds to an invalid code. > /// > /// The invalid code must never be the result of any 'hash_value' calls. This > /// can be used to flag invalid hash_codes or mark entries in a hash table. > static hash_code get_invalid_code() { return -1; }I'm sure there's a compiler out there just waiting to warn you that you're implicitly converting -1 to an unsigned type. :-)> friend bool operator==(const hash_code &lhs, const hash_code &rhs) { > return lhs.value == rhs.value; > } > friend bool operator!=(const hash_code &lhs, const hash_code &rhs) { > return lhs.value != rhs.value; > } > > /// \brief Allow a hash_code to be directly run through hash_value. > friend size_t hash_value(const hash_code &code) { return code.value; } > }; > > > // All of the implementation details of actually computing the various hash > // code values are held within this namespace. These routines are included in > // the header file mainly to allow inlining and constant propagation. > namespace hashing { namespace detail {My only comment on the implementation is that, on CPUs that have different instruction sequences for aligned and unaligned loads, you want to be careful that the 8-byte memcpys turn into aligned loads when hashing naturally aligned data. (But if we only care about running on x86-64, this won't be a problem.) Jay.
Jay Foad
2012-Feb-29 12:24 UTC
[LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
On 29 February 2012 11:47, James Molloy <james.molloy at arm.com> wrote:>> (But if we only care about >> running on x86-64, this won't be a problem.) > > Please, no. We have a cortex-a9 native buildbot already in lab.llvm.org and > as manufacturers emit faster ARM chips we (ARM) will want to have LLVM run > native on them. > > You've also got the OpenCL use case etc. > > Please bear ARM in mind.Right. (But ARMv7 uses the same ldr instruction for aligned and unaligned loads (doesn't it?) so it's not an issue there.) Jay.
James Molloy
2012-Feb-29 12:30 UTC
[LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
That is true! -----Original Message----- From: Jay Foad [mailto:jay.foad at gmail.com] Sent: 29 February 2012 12:25 To: James Molloy Cc: Chandler Carruth; LLVM Developers Mailing List Subject: Re: [LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++) On 29 February 2012 11:47, James Molloy <james.molloy at arm.com> wrote:>> (But if we only care about >> running on x86-64, this won't be a problem.) > > Please, no. We have a cortex-a9 native buildbot already in lab.llvm.org and > as manufacturers emit faster ARM chips we (ARM) will want to have LLVM run > native on them. > > You've also got the OpenCL use case etc. > > Please bear ARM in mind.Right. (But ARMv7 uses the same ldr instruction for aligned and unaligned loads (doesn't it?) so it's not an issue there.) Jay.
Jim Grosbach
2012-Feb-29 16:46 UTC
[LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
On Feb 29, 2012, at 4:24 AM, Jay Foad wrote:> On 29 February 2012 11:47, James Molloy <james.molloy at arm.com> wrote: >>> (But if we only care about >>> running on x86-64, this won't be a problem.) >> >> Please, no. We have a cortex-a9 native buildbot already in lab.llvm.org and >> as manufacturers emit faster ARM chips we (ARM) will want to have LLVM run >> native on them. >> >> You've also got the OpenCL use case etc. >> >> Please bear ARM in mind. > > Right. (But ARMv7 uses the same ldr instruction for aligned and > unaligned loads (doesn't it?) so it's not an issue there.) >Sorta. It's the same instruction, but on some implementations, unaligned loads will cause an exception, so the compiler may need to generate LDRB sequences instead. There's also the VLD* instructions to consider. Depending on what's being loaded, there's all sorts of potential tricks that can be played. We should try to be careful and give the compiler as many hints about alignment as we can. -Jim> Jay. > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Nick Lewycky
2012-Mar-01 05:22 UTC
[LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
// -- 'hash_code' class is an opaque type representing the hash code
for
some
// data. It is the intended product of hashing, and can be used to
implement
vs.
// -- 'hash_value' is a function designed to be overloaded for each
// user-defined type which wishes to be used within a hashing context. It
The first paragraph has a hanging indent but the second and third don't.
// benchmarked at over 8.5 GiB/s for large keys, and <20 cycles/
Trailing punctuation.
#include <cassert>
#include <cstring>
#include <algorithm>
#include <utility>
#include <iterator>
Sort.
/// \brief Form a hash code directly from a numerical value.
hash_code(size_t value) : value(value) {}
why not assert that the value is not the null or invalid value? I realize
you'd need to have a private constructor for the null and invalid ones then.
// All of the implementation details of actually computing the various hash
// code values are held within this namespace. These routines are included
in
// the header file mainly to allow inlining and constant propagation.
namespace hashing { namespace detail {
One namespace per line please, in LLVM.
[I only skimmed the implementation details of the hashing. It all looks
plausible enough.]
} } // End hashing detail namespaces.
Again, one per line. You do this multiple times in Hashing.h, please fix
them all.
/// reproduce *exactly* a specific behavior. To that end, we provide a
function
/// which will forcible set the seed to a fixed value. This must be done at
the
forcible -> forcibly
template <typename T> struct is_hashable_data
: integral_constant<bool, ((is_integral<T>::value ||
is_pointer<T>::value)
&& 64 % sizeof(T) == 0)> {};
Optional: I object to the leading && and propose this reflowed text:
template <typename T> struct is_hashable_data
: integral_constant<bool,
((is_integral<T>::value ||
is_pointer<T>::value) &&
64 % sizeof(T) == 0)> {};
.
#if __has_feature(__cxx_variadic_templates__)
I'm pretty sure non-clang compilers will bark at that unless you
#define'd
__has_feature(X) to 0?
--- a/unittests/ADT/HashingTest.cpp
+++ b/unittests/ADT/HashingTest.cpp
@@ -13,45 +13,295 @@
#include "gtest/gtest.h"
#include "llvm/ADT/Hashing.h"
+#include "llvm/Support/DataTypes.h"
+#include <vector>
+#include <list>
+#include <deque>
+#include <map>
Sort.
+ // Helper for test code to print hash codes.
+ void PrintTo(const hash_code &code, ::std::ostream *os) {
What's with the extra leading :: before std::?
+ namespace hashing { namespace detail {
+ template <> struct is_hashable_data<LargeTestInteger> : true_type
{};
+ } } // End hashing detail namespace.
+} // End LLVM namespace.
A reminder about 1 namespace-per-line, but also the comments on ending
namespaces are odd. They usually look like "} // end namespace llvm"
or "}
// namespace llvm", and I prefer the latter.
Nick
On 29 February 2012 01:35, Chandler Carruth <chandlerc at google.com>
wrote:
> Thanks for the feedback thus far!
>
> I've updated the header file, and enclosed a complete patch against
LLVM.
> This passes all the regtests, and I'll be doing more thorough testing
of
> LLVM itself with the patch. I've included some basic unit tests, but
could
> probably do more here... Not sure it's worth delaying the initial
> submission though, as the best testing is to use a hash testing suite...
>
> I've addressed the comments from Nadav, but there may be more minor
> stylistic issues or typos. Please keep pointing them out! I appreciate the
> help there.
>
> I've also corrected my stub for the execution-seed to be more correct
and
> to include the ability to override it during program startup. It still
> doesn't go the final step to make it actually change on each execution,
but
> is now otherwise identical. (In particular, it is no longer a compile-time
> constant that can be folded.) This regressed the performance a tiny bit,
> however...
>
> There are several improvements to the implementation of the hashing
> algorithm itself. The way the hashing included the seed hurt performance
> quite a bit. I've re-worked it to be much lighter weight, and even
after
> the execution seed fix above slowed things down, this speeds everything up
> more. We shave 4ns off the 4 to 8 byte case, bringing performance above
> that of essentially every high quality hashing algorithm...
>
> I still think we can do more, but it's already much faster than the
> existing LLVM one except for the issue Tobias pointed out w/ modulo-4 key
> sizes. I'm going to investigate this, but it may be a consequence of a
> weakness in that algorithm.
>
> I've re-run the SMHasher quality testing suite and the results are very
> good. There are a few problems identified, but these are long-known
> problems with CityHash in general, and have proven to thus far not be a
> cause of real-world issues... I'd like to fix them, but it doesn't
seem a
> high priority yet.
>
> Finally, I've run some rough initial numbers for x86 32-bit, and
it's
> surprisingly good. The relative speeds of this algorithm and others
don't
> seem to change much. A bit suspicious of that, so going to do more thorough
> analysis.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120229/cd68bf58/attachment.html>
Reasonably Related Threads
- [LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
- [LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
- [LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
- [LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)
- [LLVMdev] ADT/Hashing.h on 32-bit platforms