| Message ID | 1459834253-8291-7-git-send-email-cota@braap.org (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
Emilio G. Cota <cota@braap.org> writes: > xxhash is a fast, high-quality hashing function. The appended > brings in the 32-bit version of it, with the small modification that > it assumes the data to be hashed is made of 32-bit chunks; this increases > speed slightly for the use-case we care about, i.e. tb-hash. > > The original algorithm, as well as a 64-bit implementation, can be found at: > https://github.com/Cyan4973/xxHash > > Signed-off-by: Emilio G. Cota <cota@braap.org> > --- > include/qemu/xxhash.h | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 106 insertions(+) > create mode 100644 include/qemu/xxhash.h > > diff --git a/include/qemu/xxhash.h b/include/qemu/xxhash.h > new file mode 100644 > index 0000000..a13a665 > --- /dev/null > +++ b/include/qemu/xxhash.h > @@ -0,0 +1,106 @@ <snip> > + > +/* u32 hash of @n contiguous chunks of u32's */ > +static inline uint32_t qemu_xxh32(const uint32_t *p, size_t n, uint32_t seed) > +{ What is the point of seed here? I looked on the original site to see if there was any guidance on tuning seed but couldn't find anything. I appreciate the compiler can inline the constant away but perhaps we should #define it and drop the parameter if we are not intending to modify it? Also it might be helpful to wrap the call to avoid getting the boilerplate sizing wrong: #define qemu_xxh32(s) qemu_xxh32_impl((const uint32_t *)s, sizeof(*s)/sizeof(uint32_t), 1) Then calls become a little simpler for the user: return qemu_xxh32(&k); Do we need to include a compile time check for structures that don't neatly divide into uint32_t chunks? > + const uint32_t *end = p + n; > + uint32_t h32; > + > + if (n >= 4) { > + const uint32_t * const limit = end - 4; > + uint32_t v1 = seed + PRIME32_1 + PRIME32_2; > + uint32_t v2 = seed + PRIME32_2; > + uint32_t v3 = seed + 0; > + uint32_t v4 = seed - PRIME32_1; > + > + do { > + v1 += *p * PRIME32_2; > + v1 = XXH_rotl32(v1, 13); > + v1 *= PRIME32_1; > + p++; > + v2 += *p * PRIME32_2; > + v2 = XXH_rotl32(v2, 13); > + v2 *= PRIME32_1; > + p++; > + v3 += *p * PRIME32_2; > + v3 = XXH_rotl32(v3, 13); > + v3 *= PRIME32_1; > + p++; > + v4 += *p * PRIME32_2; > + v4 = XXH_rotl32(v4, 13); > + v4 *= PRIME32_1; > + p++; > + } while (p <= limit); > + h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + > + XXH_rotl32(v4, 18); > + } else { > + h32 = seed + PRIME32_5; > + } I don't plead any particular knowledge of hashing codes but I note the test cases we add only exercise the n == 1 path but in actual usage we exercise n = 5 (at least for arm32, I guess aarch64 would be more). > + > + h32 += n * sizeof(uint32_t); > + > + while (p < end) { > + h32 += *p * PRIME32_3; > + h32 = XXH_rotl32(h32, 17) * PRIME32_4 ; > + p++; > + } > + > + h32 ^= h32 >> 15; > + h32 *= PRIME32_2; > + h32 ^= h32 >> 13; > + h32 *= PRIME32_3; > + h32 ^= h32 >> 16; > + > + return h32; > +} > + > +#endif /* QEMU_XXHASH_H */ -- Alex Bennée
On Wed, Apr 06, 2016 at 12:39:42 +0100, Alex Bennée wrote: > > Emilio G. Cota <cota@braap.org> writes: > > > xxhash is a fast, high-quality hashing function. The appended > > brings in the 32-bit version of it, with the small modification that > > it assumes the data to be hashed is made of 32-bit chunks; this increases > > speed slightly for the use-case we care about, i.e. tb-hash. > > > > The original algorithm, as well as a 64-bit implementation, can be found at: > > https://github.com/Cyan4973/xxHash > > > > Signed-off-by: Emilio G. Cota <cota@braap.org> > > --- > > include/qemu/xxhash.h | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++ > > 1 file changed, 106 insertions(+) > > create mode 100644 include/qemu/xxhash.h > > > > diff --git a/include/qemu/xxhash.h b/include/qemu/xxhash.h > > new file mode 100644 > > index 0000000..a13a665 > > --- /dev/null > > +++ b/include/qemu/xxhash.h > > @@ -0,0 +1,106 @@ > <snip> > > + > > +/* u32 hash of @n contiguous chunks of u32's */ > > +static inline uint32_t qemu_xxh32(const uint32_t *p, size_t n, uint32_t seed) > > +{ > > What is the point of seed here? I looked on the original site to see if > there was any guidance on tuning seed but couldn't find anything. I > appreciate the compiler can inline the constant away but perhaps we > should #define it and drop the parameter if we are not intending to > modify it? The seed value would only matter if we needed consistent hashes (we don't). Any seed value should give similar performance, given xxhash's quality. I'll set a define for this seed if it is used in more than one place. > Also it might be helpful to wrap the call to avoid getting the > boilerplate sizing wrong: > > #define qemu_xxh32(s) qemu_xxh32_impl((const uint32_t *)s, sizeof(*s)/sizeof(uint32_t), 1) > > Then calls become a little simpler for the user: > > return qemu_xxh32(&k); > > Do we need to include a compile time check for structures that don't > neatly divide into uint32_t chunks? I'll give the original byte-sized function a shot and come back to this if necessary. Thanks, E.
diff --git a/include/qemu/xxhash.h b/include/qemu/xxhash.h new file mode 100644 index 0000000..a13a665 --- /dev/null +++ b/include/qemu/xxhash.h @@ -0,0 +1,106 @@ +/* + * xxHash - Fast Hash algorithm + * Copyright (C) 2012-2016, Yann Collet + * + * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * + Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * You can contact the author at : + * - xxHash source repository : https://github.com/Cyan4973/xxHash + */ +#ifndef QEMU_XXHASH_H +#define QEMU_XXHASH_H + +#define PRIME32_1 2654435761U +#define PRIME32_2 2246822519U +#define PRIME32_3 3266489917U +#define PRIME32_4 668265263U +#define PRIME32_5 374761393U + +/* + * Note : although _rotl exists for minGW (GCC under windows), performance + * seems poor. + */ +#if defined(_MSC_VER) +# define XXH_rotl32(x, r) _rotl(x, r) +#else +# define XXH_rotl32(x, r) ((x << r) | (x >> (32 - r))) +#endif + +/* u32 hash of @n contiguous chunks of u32's */ +static inline uint32_t qemu_xxh32(const uint32_t *p, size_t n, uint32_t seed) +{ + const uint32_t *end = p + n; + uint32_t h32; + + if (n >= 4) { + const uint32_t * const limit = end - 4; + uint32_t v1 = seed + PRIME32_1 + PRIME32_2; + uint32_t v2 = seed + PRIME32_2; + uint32_t v3 = seed + 0; + uint32_t v4 = seed - PRIME32_1; + + do { + v1 += *p * PRIME32_2; + v1 = XXH_rotl32(v1, 13); + v1 *= PRIME32_1; + p++; + v2 += *p * PRIME32_2; + v2 = XXH_rotl32(v2, 13); + v2 *= PRIME32_1; + p++; + v3 += *p * PRIME32_2; + v3 = XXH_rotl32(v3, 13); + v3 *= PRIME32_1; + p++; + v4 += *p * PRIME32_2; + v4 = XXH_rotl32(v4, 13); + v4 *= PRIME32_1; + p++; + } while (p <= limit); + h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + + XXH_rotl32(v4, 18); + } else { + h32 = seed + PRIME32_5; + } + + h32 += n * sizeof(uint32_t); + + while (p < end) { + h32 += *p * PRIME32_3; + h32 = XXH_rotl32(h32, 17) * PRIME32_4 ; + p++; + } + + h32 ^= h32 >> 15; + h32 *= PRIME32_2; + h32 ^= h32 >> 13; + h32 *= PRIME32_3; + h32 ^= h32 >> 16; + + return h32; +} + +#endif /* QEMU_XXHASH_H */
xxhash is a fast, high-quality hashing function. The appended brings in the 32-bit version of it, with the small modification that it assumes the data to be hashed is made of 32-bit chunks; this increases speed slightly for the use-case we care about, i.e. tb-hash. The original algorithm, as well as a 64-bit implementation, can be found at: https://github.com/Cyan4973/xxHash Signed-off-by: Emilio G. Cota <cota@braap.org> --- include/qemu/xxhash.h | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 106 insertions(+) create mode 100644 include/qemu/xxhash.h