<div class="gmail_quote">On Thu, Jun 24, 2010 at 12:14 PM, Milan Straka <span dir="ltr"><<a href="mailto:fox@ucw.cz">fox@ucw.cz</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi,<br>
<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 wanted to start a new thread in response to strictness issues brought<br>
up by Claus Reinke.<br>
<br>
> - IntMap and Map expose different APIs wrt strictness<br>
> <a href="http://www.haskell.org/pipermail/libraries/2009-March/011399.html" target="_blank">http://www.haskell.org/pipermail/libraries/2009-March/011399.html</a><br>
> <a href="http://www.mail-archive.com/haskell-cafe@haskell.org/msg48925.html" target="_blank">http://www.mail-archive.com/haskell-cafe@haskell.org/msg48925.html</a><br>
><br>
> - to work around the non-strict Map fold, users have to<br>
> resort to nested folds (non-strict fold to convert to list,<br>
> then strict foldl' over list) and other tricks:<br>
> <a href="http://www.haskell.org/pipermail/haskell-cafe/2010-June/079098.html" target="_blank">http://www.haskell.org/pipermail/haskell-cafe/2010-June/079098.html</a><br>
><br>
> similarly non-trivial thinking is required to work around other<br>
> no-control-over-strictness issues in the APIs, bypassing the obvious<br>
> functions and using non-obvious ones based on<br>
> knowledge about their implementation<br>
><br>
> - strictness is used inconsistently:<br>
> <a href="http://hackage.haskell.org/trac/ghc/ticket/4109" target="_blank">http://hackage.haskell.org/trac/ghc/ticket/4109</a><br>
><br>
> - strictness is not documented: !!!<br>
> search for "strict" in the Data.Map/IntMap documentation..<br>
><br>
> this is really bad - the only way for users to become aware<br>
> of strictness problems is by running into them, and the only way to fix<br>
> strictness-related performance issues is by referring<br>
> to the implementation (in theory, an implementation change<br>
> could invalidate lots of performance fixes in production code)<br>
<br>
I need some opinion:<br>
<br>
- Do you think methods like insert/lookup/delete/etc should be strict in<br>
key/element?<br></blockquote><div><br>Yes. This allows us to use associated data types to unpack keys and values directly in the constructor saving both time (as accessing keys require fewer indirections) and space (as there's less overhead per key/value pair).<br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
As Claus wrote, right now it is undocumented and inconsistent (both in<br>
the methods of one container and also in the same methods of different<br>
container).<br>
<br>
The problem is the following: a lookup on an empty container does not<br>
really have to evaluate the key. Should we honour it or should we<br>
sacrifice it to be faster and consistent with other methods (eg.,<br>
insert has to be strict in the key).<br>
<br>
- The Set/Map, IntSet/IntMap do not currently have a strict fold. Do you<br>
think it should be added to the API?<br></blockquote><div><br></div></div>Yes. I believe the recent post on storing lots amount of Twitter data in a Map ran into problems due to lack of a strict fold.<br><br>I think it's important to consider all the container types at once and find a consistent set of functions and strictness guarantees so that we don't introduce more inconsistencies in their APIs.<br>
<br>Johan<br><br>