search for: cityhash

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.

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: > > http://lists.cs.uiuc.edu/pipermail/cfe-dev/2011-April/014656.html...

...t;/ 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 best one out there. Look at the comparison done by Craig, Howard, and > several others when discussing what hashing function to use for libc++. > > The only downside to CityHash is code size. It is heavily tuned, and that > results in several special case ro...

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

...erred: > > >> 1. Use xxhash instead. > I'd lean towards this option as we already have a copy of xxHash in lib/Support (llvm/Support/xxhash.h). We use it for computing the --build-id in lld as fast/non-crytographic hash variant and has proven to outperform other candidates (e.g. CityHash). Vedant, what do you mean with unsupported? -- Davide "There are no solved problems; there are only problems that are more or less solved" -- Henri Poincare

...adhoc stuff :). >  That said, please do not change the hash function used by StringMap without > do careful performance analysis of the clang preprocessor.  The identifier > uniquing is a very hot path in "clang -E" performance. > >> >> Would it be possible to use CityHash instead for strings? >> >> http://code.google.com/p/cityhash/ >> > OK by me. My intention is that "Hashing.h" should contain a variety of > different hashing algorithms for various specific needs. Right now, I am > mainly focusing on hashing of mixed data types...

...most DenseMaps contain less than a few thousand entries. Even a bad hash function wouldn't hurt performance that much, and the time taken to calculate the hash is probably more of a factor in overall performance than getting the optimum distribution of hash values. Would it be possible to use CityHash instead for strings? > > http://code.google.com/p/cityhash/ > > OK by me. My intention is that "Hashing.h" should contain a variety of different hashing algorithms for various specific needs. Right now, I am mainly focusing on hashing of mixed data types - that is, you have so...

...e better than our existing adhoc stuff :). That said, please do not change the hash function used by StringMap without do careful performance analysis of the clang preprocessor. The identifier uniquing is a very hot path in "clang -E" performance. > > Would it be possible to use CityHash instead for strings? > > http://code.google.com/p/cityhash/ > > OK by me. My intention is that "Hashing.h" should contain a variety of different hashing algorithms for various specific needs. Right now, I am mainly focusing on hashing of mixed data types - that is, you have...

...raphic hash functions don't satisfy this property. What you're talking about is just being able to hash a non-contiguous set of data. That is clearly important, but there are a lot of ways to achieve it. Most of the functions I'm referring to are essentially block based. For example, CityHash is based on a 64-byte block hashing system. While this can necessitate copying the data, it should never require a malloc. You simply fill a block, and flush it out. The block can be on the stack, and modern hashing algorithms will find it much faster to memcpy mall (pointer-sized) bits of data int...

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

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

...t change the hash function used by StringMap > without do careful performance analysis of the clang preprocessor. The > identifier uniquing is a very hot path in "clang -E" performance. > > I'm not planning on touching StringMap. > >> Would it be possible to use CityHash instead for strings? >> >> http://code.google.com/p/cityhash/ >> >> OK by me. My intention is that "Hashing.h" should contain a variety of > different hashing algorithms for various specific needs. Right now, I am > mainly focusing on hashing of mixed data ty...

> 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. I did 10 tests for every version of clang...

...ue 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've run some rough initial numbers for x86 32-bit, and it's surprisingly good. The relative speeds of this algorithm and others do...

...known weaknesses here. Also, my testing seems to indicate some aspects of the adaptation made these significantly worse, but I'm not entirely certain. I'm still digging there. There are now a few hashing algorithms that do significantly better in both performance and hash quality: Murmur3, CityHash, and SpookyHash. Of these, CityHash and SpookyHash are significantly faster than Murmur3, both for large keys and for very small keys. My implementation is a variation of CityHash (the original isn't suitable for the interface) which is as high quality or higher quality, and happens to be stil...

...lo-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've run some rough initial numbers for x86 32-bit, and it's > surprisingly good. The relative speeds of this...

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