Containers and strictness

[Milan Straka]

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