Hi,
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.
I agree that my choice was not good enough. Johan Tibell also commented on this. After suggestions by others I am thinking about data Some elem = Single {-# UNPACK #-} !elem | More (Set elem) or data Some elem = Single {-# UNPACK #-} !elem | More {-# UNPACK #-} !elem (Some elem) I will improve the final version of the paper and also the implementation. Cheers, Milan