Containers and strictness

[Johan Tibell]

On Thu, Jul 1, 2010 at 12:03 AM, Milan Straka <fox at ucw.cz> wrote:

> 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)


Unfortunately unpacking doesn't work for polymorphic fields (the new warning
for ineffective unpack pragmas in GHC head should warn about this). Given
this you might as well use a standard list.

Johan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100630/8eb7de45/attachment.html