search for: murmurhash

Some additional info can be found at: http://murmurhash.googlepages.com/ http://en.wikipedia.org/wiki/MurmurHash http://www.codeproject.com/KB/recipes/hash_functions.aspx as well as in the patch description itself. Patch and benchmark attached. Gregory -------------- next part -------------- A non-text attachment was scrubbed... Name: 0001...

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. > > L...

...1:22 AM, Jay Foad <jay.foad at gmail.com> wrote: > 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/ > > The main reason is because there's no incremental version of 3. If you look...

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,...

On 13:05 Tue 27 Mar , Apollon Oikonomopoulos wrote: > On 11:31 Tue 27 Mar , Apollon Oikonomopoulos wrote: > It turns out there's a missing byte-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 ui...

...use: void add(double Data) { union { double D; uint64_t I; }; D = Data; add(I); } > > void add(StringRef StrVal) { > addImpl(StrVal.data(), StrVal.size()); > } > > I'm contradicting my stance above about not caring about the implementation :), but is MurmurHash a good hash for string data? The Bernstein hash function works really well and is much cheaper to compute than Murmur. It is used by HashString (and thus by StringMap). > > So, MurmurHash is intended for blocks of arbitrary binary data, which may contain character data, integers, or whatev...

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 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

...gset to keep track track of the # > collisions and # hash table resizes and compare those? They should > be much more stable and still correlate directly to performance. OK, now with real numbers :-) First, the main thing: SuperFastHash appears to be the hash with best distribution. Use of MurmurHash instead generates 1.28% more collisions while doing nightly test in MultiSource/Applications. Second: I've also tested lookup3 hash, and its use generated 0.1% more collisions, compared to SFH. These results were a bit surprising for me! Number of hash table resizes is independent of used ha...

On 2010-02-06 17:09, Gregory Petrosyan wrote: > Some additional info can be found at: > > http://murmurhash.googlepages.com/ > http://en.wikipedia.org/wiki/MurmurHash > http://www.codeproject.com/KB/recipes/hash_functions.aspx > > as well as in the patch description itself. Patch and benchmark attached. > > +/// This version additionally assumes that 'len % 4 == 0'. Below...

...n't dominate performance? Specifically the nightly tester includes a number of real programs and machinery to measure total compile time. On Sat, Feb 6, 2010 at 7:09 AM, Gregory Petrosyan <gregory.petrosyan at gmail.com> wrote: > Some additional info can be found at: > >  http://murmurhash.googlepages.com/ >  http://en.wikipedia.org/wiki/MurmurHash >  http://www.codeproject.com/KB/recipes/hash_functions.aspx > > as well as in the patch description itself. Patch and benchmark attached. > >        Gregory > > _______________________________________________ >...

...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 (murmurhas...

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.

> On Jan 10, 2017, at 9:36 AM, Bruce Hoult <bruce at hoult.org> wrote: > > Both are not very sophisticated. > You should also look at the different MurmurHash versions, and descendants such as CityHash. I did a few benchmark this morning, trying to tweak the hashing for pointers (as many people seem to use pointers as keys). The hash function in LLVM is quite simple, but it gives very good results. The benchmark I did was compiling a C++ file with clang...

...>> collisions and # hash table resizes and compare those? They should >> be much more stable and still correlate directly to performance. > > OK, now with real numbers :-) > > First, the main thing: SuperFastHash appears to be the hash with best > distribution. Use of MurmurHash instead generates 1.28% more collisions while > doing nightly test in MultiSource/Applications. > > Second: I've also tested lookup3 hash, and its use generated 0.1% more > collisions, compared to SFH. > > These results were a bit surprising for me! > > Number of hash...

...lerc at google.com> wrote: > On Tue, Feb 14, 2012 at 2:44 AM, Chris Lattner<clattner at apple.com <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>> wrote: > > >/ I'm contradicting my stance above about not caring about the > />/ implementation :), but is MurmurHash a good hash for string data? > />/ The Bernstein hash function works really well and is much cheaper to > />/ compute than Murmur. It is used by HashString (and thus by StringMap). > / > > If you want a good string hashing function, CityHash is by a fair margin > the bes...

.... 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 > murmurh...

..., Apollon Oikonomopoulos wrote: > On 13:05 Tue 27 Mar , Apollon Oikonomopoulos wrote: > > On 11:31 Tue 27 Mar , Apollon Oikonomopoulos wrote: > > It turns out there's a missing byte-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 +2...

...ulos wrote: > > On 13:05 Tue 27 Mar , Apollon Oikonomopoulos wrote: > > > On 11:31 Tue 27 Mar , Apollon Oikonomopoulos wrote: > > > It turns out there's a missing byte-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/murmu...

On Feb 7, 2010, at 1:03 PM, Gregory Petrosyan wrote: > On Sat, Feb 06, 2010 at 04:51:15PM -0800, Chandler Carruth wrote: >> While I've not reviewed the patch in too much detail, it looks >> promising. Can you run some end-to-end benchmarks to make sure that >> cache pressure in the full program or other variables not accounted >> for in a micro-benchmark don't