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

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 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 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 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:

traversehttp://hackage.haskell.org/packages/archive/base/4.6.0.0/doc/html/Data-Trave... ((k, v) -> (,) k $http://hackage.haskell.org/packages/archive/containers/latest/doc/html/$ f k v) (toListhttp://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-... m)

And I thought "toList" didn't guarantee anything (as opposed to toAscList)...

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries