<div class="gmail_quote">On Thu, Jul 1, 2010 at 12:03 AM, Milan Straka <span dir="ltr"><<a href="mailto:fox@ucw.cz">fox@ucw.cz</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hi,<br>
<div class="im"><br>
> Milan Straka wrote:<br>
> > I am working on improving containers performance and have written<br>
> > a draft paper about it <a href="http://fox.ucw.cz/papers/containers/containers.pdf" target="_blank">http://fox.ucw.cz/papers/containers/containers.pdf</a><br>
><br>
> I am a bit surprised about the types chosen for HashSet and HashMap<br>
> (section 5, p.9). Usually, hash-based containers are optimized for the case<br>
> that the hash-buckets remain small. For that case, it's hard to imagine that<br>
> the given types wouldn't be slower than the more straightforward types:<br>
><br>
> data HashSet elem = HS (IntMap [elem])<br>
> data HashMap key val = HM (IntMap [(key, val)])<br>
><br>
> Others have suggested further improvements by using strict<br>
> (unboxed?) tuples, a variant on lists that is strict and/or<br>
> non-empty.<br>
<br>
</div>I agree that my choice was not good enough. Johan Tibell also<br>
commented on this.<br>
<br>
After suggestions by others I am thinking about<br>
data Some elem = Single {-# UNPACK #-} !elem | More (Set elem)<br>
or<br>
data Some elem = Single {-# UNPACK #-} !elem | More {-# UNPACK #-} !elem (Some elem)</blockquote><div><br></div><div>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.</div>
<div><br></div><div>Johan</div><div><br></div></div>