similar to: [LLVMdev] [PATCH] FoldingSetNodeID: use MurmurHash2 instead of SuperFastHash

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

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 %

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 dominate performance? Specifically the > nightly tester includes a number

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

On Mon, Feb 08, 2010 at 10:31:23AM -0800, Chris Lattner wrote: > 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

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

On Feb 10, 2010, at 4:49 PM, Gregory Petrosyan wrote: >> >> These numbers are so noisy, that they aren't particularly useful. >> Could you try instrumenting foldingset 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

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

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

The current implementation is: void FoldingSetNodeID::AddInteger(unsigned long long I) { AddInteger(unsigned(I)); if ((uint64_t)(int)I != I) Bits.push_back(unsigned(I >> 32)); } (uint64_t)(int)I first truncates I to signed int, which causes the second cast to sign extend the value to 64 bits. The problem is that if the 31st bit of the original value is 1, the sign extended value

Hi Chris, This is a good idea and I started thinking in that direction already. But what I don't quite understand the TFs, how TFs are formed and which rules they should obey to. For example now: > PendingLoads created by the SelectionDAGLowering::getLoadFrom and then copied into the > TokenFactor node by SelectionDAGLowering::getRoot called from the >

Hi, While profiling LLVM using my test-cases with huge MBBs, I noticed that FoldingSetNodeID operations (ComputeHash,insertion,etc) may become really inefficient for the nodes, which have very many operands. I can give you an example of what is meant by "very many". In my test-case (you can fetch it from here http://llvm.org/bugs/attachment.cgi?id=1275), which is just one HUGE MBB

Hi Dan, Thanks for commenting on this topic. See my comments in-line. ----- Ursprüngliche Mail ---- > Von: Dan Gohman <gohman at apple.com> > An: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu> > Gesendet: Mittwoch, den 30. April 2008, 21:38:26 Uhr > Betreff: Re: [LLVMdev] FoldingSetNodeID operations inefficiency > > > On Apr 28, 2008, at 6:21 AM, Roman

On Fri, Jun 4, 2010 at 3:47 PM, Eli Friedman <eli.friedman at gmail.com> wrote: > On Fri, Jun 4, 2010 at 2:46 AM, Gregory Petrosyan > <gregory.petrosyan at gmail.com> wrote: >> Hello, >> >> I am working on a pass that finds identical basic blocks and abstracts >> them into functions, in order to reduce code size. >> >> To decide, whether

> 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