search for: murmurhash3

Hi, The dovecot 2.3.0.1 Debian package currently fails to build on all big-endian architectures[1], due to murmurhash3 tests failing. The relevant output from e.g. s390x is: test-murmurhash3.c:22: Assert(#8) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 test-murmurhash3.c:22: Assert(#11) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 test-murmurhash3.c:22: Assert(#12) failed: m...

On 26.03.2018 15:49, Apollon Oikonomopoulos wrote: > Hi, > > The dovecot 2.3.0.1 Debian package currently fails to build on all > big-endian architectures[1], due to murmurhash3 tests failing. The > relevant output from e.g. s390x is: > > test-murmurhash3.c:22: Assert(#8) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > test-murmurhash3.c:22: Assert(#11) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > test-murmurhash3.c:2...

Hi Aki, On 15:55 Mon 26 Mar , Aki Tuomi wrote: > On 26.03.2018 15:49, Apollon Oikonomopoulos wrote: > > Hi, > > > > The dovecot 2.3.0.1 Debian package currently fails to build on all > > big-endian architectures[1], due to murmurhash3 tests failing. The > > relevant output from e.g. s390x is: > > > > test-murmurhash3.c:22: Assert(#8) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#11) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > &...

...nal diff that'll end up getting committed. It'd be good to know if > it actually fixes the issue for you - sadly, I don't have a big endian > system to play with.) Thanks for the quick response! Unfortunately still fails, although with fewer assertion errors than before: test-murmurhash3.c:34: Assert(#8) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 test-murmurhash3.c:34: Assert(#11) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 test-murmurhash3.c:34: Assert(#12) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 murmurhash3 (murmurhash...

.... It'd be good to know if > > it actually fixes the issue for you - sadly, I don't have a big endian > > system to play with.) > > Thanks for the quick response! > > Unfortunately still fails, although with fewer assertion errors than > before: > > test-murmurhash3.c:34: Assert(#8) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > test-murmurhash3.c:34: Assert(#11) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > test-murmurhash3.c:34: Assert(#12) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > murmurha...

...e-inversion when loading the blocks > which should be addressed in getblock{32,64}. Murmurhash treats each > block as an integer expecting little-endian storage. Applying this > additional change fixes the build on s390x (and does not break it on > x864_64): > > --- b/src/lib/murmurhash3.c > +++ b/src/lib/murmurhash3.c > @@ -23,7 +23,7 @@ > > static inline uint32_t getblock32(const uint32_t *p, int i) > { > - return p[i]; > + return cpu32_to_le(p[i]); ? or perhaps le32_to_cpu, although it should be the same in the end. > } > > //------------...

...sue for you - sadly, I don't have a big endian system to play with.) Thanks, Jeff. -- The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers. - Bill Gates, The Road Ahead, pg. 265 -------------- next part -------------- diff --git a/src/lib/murmurhash3.c b/src/lib/murmurhash3.c index 45dcc22..d0336a1 100644 --- a/src/lib/murmurhash3.c +++ b/src/lib/murmurhash3.c @@ -94,6 +94,8 @@ void murmurhash3_32 (const void *key, size_t len, uint32_t seed, h1 = fmix32(h1); + h1 = cpu32_to_be(h1); + memcpy(out, &h1, sizeof(h1)); } @@ -206,6 +...

...locks > > which should be addressed in getblock{32,64}. Murmurhash treats each > > block as an integer expecting little-endian storage. Applying this > > additional change fixes the build on s390x (and does not break it on > > x864_64): > > > > --- b/src/lib/murmurhash3.c > > +++ b/src/lib/murmurhash3.c > > @@ -23,7 +23,7 @@ > > > > static inline uint32_t getblock32(const uint32_t *p, int i) > > { > > - return p[i]; > > + return cpu32_to_le(p[i]); > > ? or perhaps le32_to_cpu, although it should be the same in...

...ould be addressed in getblock{32,64}. Murmurhash treats each > > > block as an integer expecting little-endian storage. Applying this > > > additional change fixes the build on s390x (and does not break it on > > > x864_64): > > > > > > --- b/src/lib/murmurhash3.c > > > +++ b/src/lib/murmurhash3.c > > > @@ -23,7 +23,7 @@ > > > > > > static inline uint32_t getblock32(const uint32_t *p, int i) > > > { > > > - return p[i]; > > > + return cpu32_to_le(p[i]); > > > > ? or perhaps le...

...r every version of clang/llvm compiled with the hash function, and here are the best timings: - Original LLVM: hash(k) = (k >> 4) ^ (k >> 9) 3.40s - Stupid hash: hash(k) = k 3.55s - A bit less stupid: hash(k) = k >> unused_bits (defined by sizeof(T) = 2^unused_bits) 3.47s - Murmurhash3 3.47s So different hashing functions make a difference. For pointers, it seems that the one used by LLVM is quite good. It gives the best performance here. It is quite surprising that Murmurhash3 does not behave better than the “A bit less stupid” hash. My guess is that the LLVM hash function is...

On Tue, Feb 14, 2012 at 2:44 AM, Chris Lattner <clattner at apple.com> wrote: > On Feb 13, 2012, at 2:00 AM, Talin wrote: >> >> Just out of curiosity, why not MurmurHash3 ? This page seems to >> suggest that #2 has some flaw, and #3 is better all round: >> >> https://sites.google.com/site/murmurhash/ >> > The main reason is because there's no incremental version of 3. > > > I think that that is a great reason. > > LLVM...

On 13 February 2012 00:59, Talin <viridia at gmail.com> wrote: > Here's my latest version of Hashing.h, which I propose to add to llvm/ADT. > Comments welcome and encouraged. > /// Adapted from MurmurHash2 by Austin Appleby Just out of curiosity, why not MurmurHash3 ? This page seems to suggest that #2 has some flaw, and #3 is better all round: https://sites.google.com/site/murmurhash/ Would it be possible to use CityHash instead for strings? http://code.google.com/p/cityhash/ Thanks, Jay.

...ve a custom DenseMapInfo, >> and that's where having a good hash function comes in. >> >> There are a bunch of hash functions out there (FNV1, SuperFastHash, and >> many others). The best overall hash function that I am currently aware of >> is Austin Appleby's MurmurHash3 (http://code.google.com/p/smhasher/). >> >> For LLVM's use, we want a hash function that can handle mixed data - that >> is, pointers, ints, strings, and so on. Most of the high-performance hash >> functions will work well on mixed data types, but you have to put >&gt...

...ruary 2012 00:59, Talin <viridia at gmail.com> wrote: > > Here's my latest version of Hashing.h, which I propose to add to > llvm/ADT. > > Comments welcome and encouraged. > > > /// Adapted from MurmurHash2 by Austin Appleby > > Just out of curiosity, why not MurmurHash3 ? This page seems to > suggest that #2 has some flaw, and #3 is better all round: > > https://sites.google.com/site/murmurhash/ > > The main reason is because there's no incremental version of 3. If you look at the source, you'll notice that the very first thing that 3 does i...

...for complex key types, you really need to have a custom DenseMapInfo, and that's where having a good hash function comes in. There are a bunch of hash functions out there (FNV1, SuperFastHash, and many others). The best overall hash function that I am currently aware of is Austin Appleby's MurmurHash3 (http://code.google.com/p/smhasher/). For LLVM's use, we want a hash function that can handle mixed data - that is, pointers, ints, strings, and so on. Most of the high-performance hash functions will work well on mixed data types, but you have to put everything into a flat buffer - that is, a...

On Feb 13, 2012, at 2:00 AM, Talin wrote: > Just out of curiosity, why not MurmurHash3 ? This page seems to > suggest that #2 has some flaw, and #3 is better all round: > > https://sites.google.com/site/murmurhash/ > > The main reason is because there's no incremental version of 3. I think that that is a great reason. > LLVM's needs, on the other hand, a...

> On Jan 10, 2017, at 8:56 AM, Mehdi Amini <mehdi.amini at apple.com> wrote > > Some tests I can suggest is to replace the hash function with your favorite and: Thanks. I’ll give it a try. It will take some time as I need to rewrite DenseMap if I want to use the Knuth multiplicative hash. > ultimately I believe real-world impact is the best way to get a change in. That’s

...ou really need to have a custom DenseMapInfo, > and that's where having a good hash function comes in. > > There are a bunch of hash functions out there (FNV1, SuperFastHash, and > many others). The best overall hash function that I am currently aware of > is Austin Appleby's MurmurHash3 (http://code.google.com/p/smhasher/). > > For LLVM's use, we want a hash function that can handle mixed data - that > is, pointers, ints, strings, and so on. Most of the high-performance hash > functions will work well on mixed data types, but you have to put > everything into a...

...Info, >>> and that's where having a good hash function comes in. >>> >>> There are a bunch of hash functions out there (FNV1, SuperFastHash, and >>> many others). The best overall hash function that I am currently aware of >>> is Austin Appleby's MurmurHash3 (http://code.google.com/p/smhasher/). >>> >>> For LLVM's use, we want a hash function that can handle mixed data - >>> that is, pointers, ints, strings, and so on. Most of the high-performance >>> hash functions will work well on mixed data types, but you hav...

On Tue, Feb 14, 2012 at 2:44 AM, Chris Lattner <clattner at apple.com> wrote: > On Feb 13, 2012, at 2:00 AM, Talin wrote: > > Just out of curiosity, why not MurmurHash3 ? This page seems to >> suggest that #2 has some flaw, and #3 is better all round: >> >> https://sites.google.com/site/murmurhash/ >> >> The main reason is because there's no incremental version of 3. > > > I think that that is a great reason. > > LL...