search for: smhasher

...urmurHash a good hash for string data?  The Bernstein hash > function works really well and is much cheaper to compute than Murmur. Have you seen benchmarks saying that, or are you just guessing from the length of the code? The benchmarks I've seen say the opposite: http://code.google.com/p/smhasher/wiki/MurmurHash3#Bulk_speed_test,_hashing_an_8-byte-aligned_256k_block and http://code.google.com/p/cityhash/source/browse/trunk/README. > It > is used by HashString (and thus by StringMap). > >   // Add a possibly unaligned sequence of bytes. >   void addImpl(const char *I, size_t...

...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, an array of machine words whose star...

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

...apInfo, > 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, an array of...

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

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

...e 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 in...

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

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

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 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 >>&g...

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

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