<div class="gmail_quote">On Thu, Jul 1, 2010 at 12:03 AM, Milan Straka <span dir="ltr">&lt;<a href="mailto:fox@ucw.cz">fox@ucw.cz</a>&gt;</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>
&gt; Milan Straka wrote:<br>
&gt; &gt; I am working on improving containers performance and have written<br>
&gt; &gt; 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>
&gt;<br>
&gt; I am a bit surprised about the types chosen for HashSet and HashMap<br>
&gt; (section 5, p.9). Usually, hash-based containers are optimized for the case<br>
&gt; that the hash-buckets remain small. For that case, it&#39;s hard to imagine that<br>
&gt; the given types wouldn&#39;t be slower than the more straightforward types:<br>
&gt;<br>
&gt;     data HashSet elem = HS (IntMap [elem])<br>
&gt;     data HashMap key val = HM (IntMap [(key, val)])<br>
&gt;<br>
&gt; Others have suggested further improvements by using strict<br>
&gt; (unboxed?) tuples, a variant on lists that is strict and/or<br>
&gt; 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&#39;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>