Containers and strictness

Yitzchak Gale gale at sefer.org
Wed Jun 30 12:32:01 EDT 2010


Milan Straka wrote:
> I am working on improving containers performance and have written
> a draft paper about it http://fox.ucw.cz/papers/containers/containers.pdf

I am a bit surprised about the types chosen for HashSet and HashMap
(section 5, p.9). Usually, hash-based containers are optimized for the case
that the hash-buckets remain small. For that case, it's hard to imagine that
the given types wouldn't be slower than the more straightforward types:

    data HashSet elem = HS (IntMap [elem])
    data HashMap key val = HM (IntMap [(key, val)])

Others have suggested further improvements by using strict
(unboxed?) tuples, a variant on lists that is strict and/or
non-empty.

Thanks,
Yitz


More information about the Libraries mailing list