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

[Ryan Newton]

Well, with Haskell we *depend* on optimizations, right?  It's a not a
performance-by-construction, but rather
performance-by-awesome-rewriting-and-other-tricks approach.

I set -O2 for my packages, mostly.  But I imagine that since it is NOT the
default ~/.cabal/config setting, that most people installing Haskell
packages are getting the default (-O0), and most packages are not
specifying otherwise.  In fact, Hackage specifically discourages you when
you upload a package with -O2 set!

Anyway, personally I don't care much about -O0 performance.  But I do get a
little nervous when radical changes in asymptotic complexity (rather than
just constant factors) come from optimization settings.  For example, as an
idiom, "forM_ [1..10^9] $ ..." makes me extremely nervous as opposed to
writing a proper non-allocating for-loop construct.


On Fri, Jul 5, 2013 at 2:18 AM, John Lato <jwlato at gmail.com> wrote:

> 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 gmail.com> 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 gmail.com> 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<http://hackage.haskell.org/packages/archive/base/4.6.0.0/doc/html/Data-Traversable.html#v:traverse> ((k,
>>> v) -> (,) k $<http://hackage.haskell.org/packages/archive/containers/latest/doc/html/$> f
>>> k v) (toList<http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Map-Strict.html#v:toList>
>>>  m)
>>>
>>> And I thought "toList" didn't guarantee anything (as opposed to
>>> toAscList)...
>>>
>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries at haskell.org
>>> http://www.haskell.org/mailman/listinfo/libraries
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130729/0d631dc1/attachment.htm>