[Haskell-cafe] fundata1 -- Karmic Social Capital Benchmark and Shootout

[Johan Tibell]

On Fri, Oct 29, 2010 at 1:17 PM, Daryoush Mehrtash <dmehrtash at gmail.com> wrote:
> In the lessons you say:
>
>> Haskell proved too slow with String Map, so we ended up interning strings
>> and working with an IntMap and a dictionary to disintern back to strings as
>> a last step.  Daniel Fisher was instrumental in bringing Haskell up to speed
>> with OCaml and then beating it.  Don Stewart provided awesome leadership and
>> amazing modification of Haskell's core data structured before your very
>> eyes.

A quick tip for anyone who needs to work on large maps with string
keys in the future: try Milan Straka's hashmap package. String
comparison is expensive and using a size balanced tree causes O(log n)
of them. The HashMap data type uses an IntMap internally and typically
(in the absence of collisions) needs to traverse the string only once,
to compute the hash, and can then perform O(log n) cheap Int
comparisons.

I'm working on a more efficient hash function for ByteString and Text:
an implementation of MurmurHash. The HashMap data type and the need
hash function together should give us good performance for maps with
string keys.

Johan