similar to: [LLVMdev] We need better hashing

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

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, are fairly

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

On Feb 14, 2012, at 10:47 PM, Talin wrote: > /// Add a pointer value > template<typename T> > void add(const T *PtrVal) { > addImpl( > reinterpret_cast<const uint32_t *>(&PtrVal), > reinterpret_cast<const uint32_t *>(&PtrVal + 1)); > } > > This violates TBAA rules and looks pretty dangerous to expose as public API.

On Mon, Feb 13, 2012 at 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

OK here's a patch with the latest, including unit tests. I've also tried to make the comments clear that this is intended for the case of "generic" key types, where you are either hashing multiple data types together, or you don't know in advance what the data type will be - for cases such as strings where a tailored algorithm is available, you should use that instead of

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:

On Feb 13, 2012, at 1:27 AM, Jay Foad wrote: > On 13 February 2012 09:22, Jay Foad <jay.foad at gmail.com> wrote: >> Would it be possible to use CityHash instead for strings? >> >> http://code.google.com/p/cityhash/ > > Incidentally there was talk of using CityHash for LLVM's StringMap > last year, but I don't think it ever came to anything: >

On 13 February 2012 09:22, Jay Foad <jay.foad at gmail.com> wrote: > Would it be possible to use CityHash instead for strings? > > http://code.google.com/p/cityhash/ Incidentally there was talk of using CityHash for LLVM's StringMap last year, but I don't think it ever came to anything: http://lists.cs.uiuc.edu/pipermail/cfe-dev/2011-April/014656.html Jay.

According to... https://github.com/rurban/smhasher/blob/master/README.md Bernstein has quality problems (while xx is as good as you get in a non-crypto hash), and xx is 7x (32 bit) - 12x (64 bit) faster. That's on long strings. It would be worth checking the startup overhead for typically short identifiers in programs. See later on in the README: "When used in a hash table the

> 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

Here's my latest version of Hashing.h, which I propose to add to llvm/ADT. Comments welcome and encouraged. On Thu, Feb 9, 2012 at 11:23 AM, Talin <viridia at gmail.com> wrote: > By the way, the reason I'm bringing this up is that a number of folks are > currently working on optimizing the use of hash tables within LLVM's code > base, and unless we can come up with a

On Fri, Feb 17, 2012 at 10:58 PM, Talin <viridia at gmail.com> wrote: > However, I really do need an incremental hash for the various uniquing > maps which I'm attempting to optimize. Take for example the case of > uniquing a constant array - the key consists of a type* pointer and an > array of constant*. Those data fields are not stored contiguously in > memory, so I

On Tue, Apr 25, 2017 at 12:55 PM, Vedant Kumar via llvm-dev <llvm-dev at lists.llvm.org> wrote: > >> On Apr 24, 2017, at 5:37 PM, Scott Smith via llvm-dev <llvm-dev at lists.llvm.org> wrote: >> >> I've been working on improving the startup performance of lldb, and ran into an issue with llvm::HashString. It works a character at a time, which creates a long

On Fri, Feb 17, 2012 at 1:53 AM, Chandler Carruth <chandlerc at google.com>wrote: > Jeffrey and I are working on future standard library functionality for > hashing user defined types: > > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3333.html > > I would much rather have an interface that is close to or mirrors this > one. We already have some field

I've been working on improving the startup performance of lldb, and ran into an issue with llvm::HashString. It works a character at a time, which creates a long dependency chain in the processor. On the other hand, the function is very short, which probably works well for short identifiers. I don't know how the mix of identifier length seen by lldb compares with that seen by

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

> 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

Jeffrey and I are working on future standard library functionality for hashing user defined types: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3333.html I would much rather have an interface that is close to or mirrors this one. We already have some field experience with it, and using it in LLVM and Clang would provide more. Also, it would be possible to essentially share code

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