search for: superfasthash

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

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

...er 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. Ok, now with some kinda-hard numbers! murmurhash2 | superfasthash | - 6.6404 seconds (6.6697 wall clock) | 6.6204 seconds (6.8557 wall clock) + 2.6722 seconds (2.7064 wall clock) | 2.7962 seconds (2.7502 wall clock) + 8.6725 seconds (8.6662 wall clock) | 8.7526 seconds (8.7162 wall clock) + 2.7362 seconds (2.7729 wall clock)...

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 %

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:

...n'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 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 surprisin...

...en replacing std::map and FoldingSet with DenseMap in a number of places, and plan to do more of this. The thing is, for complex key types, you really need 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-performanc...

...d FoldingSet > with DenseMap in a number of places, and plan to do more of this. The thing > is, for complex key types, you really need 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. Mos...

I'm working on a bug where LLVM takes over six minutes to compile a module. After some hand-editing, the module looks like this: class half { private: union uif { unsigned int i; float f; }; static const uif _toFloat[1 << 16]; }; const half::uif half::_toFloat[1 << 16] = { {0x00000000}, {0x33800000}, {0x34000000}, {0x34400000}, {0x34800000},

...; with DenseMap in a number of places, and plan to do more of this. The thing >> is, for complex key types, you really need 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, str...

...in a number of places, and plan to do more of this. The thing >>> is, for complex key types, you really need 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,...

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

...laces, and plan to do more of this. The thing >>>> is, for complex key types, you really need 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 - >&...

...chdr Size: 27596 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120228/f5d1b153/attachment.h> -------------- next part -------------- ------------------------------------------------------------------------------- --- Testing superfast (Paul Hsieh's SuperFastHash) [[[ Speed Tests ]]] Bulk speed test - 262144-byte keys Alignment 0 - 0.558 bytes/cycle - 1206.82 MiB/sec @ 2.268 ghz Alignment 1 - 0.557 bytes/cycle - 1204.25 MiB/sec @ 2.268 ghz Alignment 2 - 0.558 bytes/cycle - 1207.09 MiB/sec @ 2.268 ghz Alignment 3 - 0.557 bytes/cycle - 1204.47 MiB/s...