Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

John Lato jwlato at
Fri Jul 5 08:18:56 CEST 2013

Upon re-reading, this was much more terse than I intended, mostly because I
didn't want to get bogged down in an off-topic tangent.  What I mean is
that I think it's quite rare indeed to be in a situation where you care
about performance, code with -O2 performs acceptably well, but being
performance-bound at -O0 is a serious hindrance.

But that's my own experience, and I'm sure that others have had different
experiences.  And this issue in particular comes up often enough that I'm
sure there's something I'm missing.  Hence my question.

On Fri, Jul 5, 2013 at 10:48 AM, John Lato <jwlato at> wrote:

> Slightly off-topic, but why do you care about the performance of code
> compiled with -O0?  I can think of at least one valid reason for doing so,
> but even for that particular instance I doubt that changing the code is the
> proper solution.
> Aside from that, I definitely agree that most packages could do a better
> job documenting the heap usage of functions.
> On Fri, Jul 5, 2013 at 8:41 AM, Ryan Newton <rrnewton at> wrote:
>> After playing a bit with Ryan's benchmark, I no longer think that the
>>> order matters much for the total number of allocations. Nor do I believe
>>> in first-class vs non-first-class IO actions. All that should matter is
>>> how many allocations we can move to the stack. But I haven't yet figured
>>> out why exactly different versions differ so drastically in this regard.
>> Yeah, it's all rather different to predict in advance, isn't it?
>> I tried your alternate foldrWithKey and I saw it heap allocating as well.
>> Further, -O0 vs. -O2 can make a big difference.  It's a little
>> frustrating because for dealing efficiently with big data sets, especially
>> in parallel.  It would be nice to have big-O numbers in the docs for heap
>> allocation as well as time cost -- and ones you could trust irrespective of
>> optimize level.
>> By the way, is traverse/traverseWithKey supposed to guarantee a specific
>> order?  The doc uses this code in the definition:
>>     traverse<> ((k,
>> v) -> (,) k $<$> f
>> k v) (toList<>
>>  m)
>> And I thought "toList" didn't guarantee anything (as opposed to
>> toAscList)...
>> _______________________________________________
>> Libraries mailing list
>> Libraries at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list