On 2/10/06, Ketil Malde wrote:

Hmm...perhaps it is worth it, then? The benchmark may specify "hash table", but I think it is fair to interpret it as "associative data structure" - after all, people are using "associative arrays" that (presumably) don't guarantee a hash table underneath, and it can be argued that Data.Map is the canonical way to achieve that in Haskell.

Based on this advice, I wrote a k-nucleotide entry using the rough structure of the OCaml entry, but with the manual IO from Chris and Don's "Haskell #2" entry. It runs in under 4 seconds on my machine, more than ten times the speed of the fastest Data.HashTable entry. -- Brian T. Sniffen bts@alum.mit.edu or brian.sniffen@gmail.com http://www.evenmere.org/~bts

Simon Marlow wrote:

Brian Sniffen wrote:

...

On 2/10/06, Ketil Malde wrote:

...

Hmm...perhaps it is worth it, then? The benchmark may specify "hash table", but I think it is fair to interpret it as "associative data structure" - after all, people are using "associative arrays" that (presumably) don't guarantee a hash table underneath, and it can be argued that Data.Map is the canonical way to achieve that in Haskell.

Based on this advice, I wrote a k-nucleotide entry using the rough structure of the OCaml entry, but with the manual IO from Chris and Don's "Haskell #2" entry. It runs in under 4 seconds on my machine, more than ten times the speed of the fastest Data.HashTable entry.

I haven't been following this too closely, but could someone provide me with (or point me to) the badly performing Data.HashTable example, so we can measure our improvements?

Cheers, Simon

From the shooutout itself:

http://shootout.alioth.debian.org/gp4/benchmark.php?test=knucleotide&lang=ghc&id=3 and http://shootout.alioth.debian.org/gp4/benchmark.php?test=knucleotide&lang=ghc&id=2 (I forget the exact different between them)

From the wiki (the Current Entry):

http://haskell.org/hawiki/KnucleotideEntry#head-dfcdad61d34153143175bb9f8237...

On Wed, Feb 15, 2006 at 09:42:10AM +0100, Ketil Malde wrote:

Not sure how relevant this is, but I see there is a recently released hash library here that might be a candidate for FFIing?

https://sourceforge.net/projects/goog-sparsehash/

| An extremely memory-efficient hash_map implementation. 2 bits/entry | overhead! The SparseHash library contains several hash-map | implementations, including implementations that optimize for space | or speed.

If we want really fast maps, we should be using this. it beats the competition by far: http://judy.sourceforge.net/ John -- John Meacham - ⑆repetae.net⑆john⑈