Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
Hi I didn't say I agree, I most certainly don't. What I meant with my comment was that a slowdown of 10x, just to preserve laziness, is perfect fuel for those who claim that laziness is good in theory but bad in practice. A bad implementation of laziness will always be slower than a bad implementation of strictness - as we have strict CPU's. However, laziness gives you some really cool opportunities for deforestation and supercompilation - so at some point Haskell will overcome the performance penalty of laziness and start to reap the performance benefits - I think... Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
| 1) Why is the Prelude mapM so slow? It seems like running 10x slower | than mapM_ when generating only 50,000 return values is a problem. All this does seem odd. I've submitted a ticket so we don't forget it http://hackage.haskell.org/trac/ghc/ticket/2236 It appears to be some bad (possibly even non-linear) run-time system or garbage collector effect, caused by the very deep stack. Thanks for persisting with this. I'd expect mapM to be a bit slower, but not *that* much. Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
2008/4/25, Niklas Broberg [EMAIL PROTECTED]: Wow. A 10x slowdown for a very commonly used function that in 99.8% of all use cases has no need for the extra laziness at all. No wonder some people say Haskell is a toy language... A toy language that is still much faster than many currently popular languages so... Is Ruby/Python/... a toy too ? Still these numbers seems odd, there's probably something that don't optimize very well here. -- Jedaï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
Wow. A 10x slowdown for a very commonly used function that in 99.8% of all use cases has no need for the extra laziness at all. No wonder some people say Haskell is a toy language... A toy language that is still much faster than many currently popular languages so... Is Ruby/Python/... a toy too ? I didn't say I agree, I most certainly don't. What I meant with my comment was that a slowdown of 10x, just to preserve laziness, is perfect fuel for those who claim that laziness is good in theory but bad in practice. And my alarm was more directed towards the fact that others seemed to find that perfectly acceptable. There are of course mitigating factors, in particular that mapM is rather uncommon over input lists that size, and for smaller list (say 50k instead of 500k) the slowdown isn't even half as bad (more like 2-3x). But I'm glad to hear that Simon is alarmed too. ;-) Cheers, /Niklas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
Hello Niklas, Friday, April 25, 2008, 1:25:39 AM, you wrote: Not that it should matter for performance any, but you really ought to reverse the result list too, or compute the accumulator in the right order. :-) unfortunately, this affects performance too. reverse costs one more scan through the list and building lot of thunks has its own space and time cost -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
On the test case i'm running the performance impacts of reversing the
return list are negligible:
mapM3 :: Monad m = (a - m b) - [a] - m [b]
{-# INLINE mapM3 #-}
mapM3 fn lst = mapM3accum fn lst []
where mapM3accum _ [] accum = return $ reverse accum
mapM3accum fn (x:xs) accum = do
r - fn x
mapM3accum fn xs (r:accum)
main5 = do
print $ length $ mapM_ (flip replicate ()) [1..11]
time ~ 18 seconds (about the same, faster on my machine probably due
to timing artifacts) and the memory was about the same (strangely less
than the non-reversing one though again that's probably an artifact.)
In any case, I have some questions:
1) Why is the Prelude mapM so slow? It seems like running 10x slower
than mapM_ when generating only 50,000 return values is a problem.
2) Is there a reason to not use mapM3 above?
Thanks and take care, Ben
On Thu, Apr 24, 2008 at 2:33 PM, Bulat Ziganshin
[EMAIL PROTECTED] wrote:
Hello Niklas,
Friday, April 25, 2008, 1:25:39 AM, you wrote:
Not that it should matter for performance any, but you really ought to
reverse the result list too, or compute the accumulator in the right
order. :-)
unfortunately, this affects performance too. reverse costs one more scan
through the list and building lot of thunks has its own space and time
cost
--
Best regards,
Bulatmailto:[EMAIL PROTECTED]
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
On Thu, Apr 24, 2008 at 11:28 PM, Ben [EMAIL PROTECTED] wrote: 2) Is there a reason to not use mapM3 above? Yes, there certainly is. mapM3 is not equivalent to mapM; it is too strict: *Main take 3 $ head $ mapM return [1,2,3,4,undefined] [1,2,3] *Main take 3 $ head $ mapM3 return [1,2,3,4,undefined] [*** Exception: Prelude.undefined So, like foldl', mapM3 seems a viable alternative for mapM, but not a replacement. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
Luke, Thanks for the nice answer. So maybe I'll give mapM3 the name mapM' and put it in my personal library. But I'm still a bit curious about the performance profile of mapM. The profiler is telling me they're allocating around the same amount of memory, so I am not clear what is making it slow. I am guessing it has something to do with extra thunks due to laziness, but a 10x slowdown? Thanks again, B On Thu, Apr 24, 2008 at 4:45 PM, Luke Palmer [EMAIL PROTECTED] wrote: On Thu, Apr 24, 2008 at 11:28 PM, Ben [EMAIL PROTECTED] wrote: 2) Is there a reason to not use mapM3 above? Yes, there certainly is. mapM3 is not equivalent to mapM; it is too strict: *Main take 3 $ head $ mapM return [1,2,3,4,undefined] [1,2,3] *Main take 3 $ head $ mapM3 return [1,2,3,4,undefined] [*** Exception: Prelude.undefined So, like foldl', mapM3 seems a viable alternative for mapM, but not a replacement. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
On Fri, Apr 25, 2008 at 12:02 AM, Ben [EMAIL PROTECTED] wrote: Luke, Thanks for the nice answer. So maybe I'll give mapM3 the name mapM' and put it in my personal library. Except the answer was wrong. I forgot the reverse in my implementation, so that undefined we were seeing was just the last element of the list. But the conclusion is still true :-) *Main take 3 $ runIdentity $ mapM return (1:2:3:4:undefined) [1,2,3] *Main take 3 $ runIdentity $ mapM3 return (1:2:3:4:undefined) *** Exception: Prelude.undefined But I'm still a bit curious about the performance profile of mapM. The profiler is telling me they're allocating around the same amount of memory, so I am not clear what is making it slow. I am guessing it has something to do with extra thunks due to laziness, but a 10x slowdown? Tail recursion can make a huge difference in strict settings: the difference between a loop and recursion in C. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
2) Is there a reason to not use mapM3 above? Yes, there certainly is. mapM3 is not equivalent to mapM; it is too strict: *Main take 3 $ head $ mapM return [1,2,3,4,undefined] [1,2,3] *Main take 3 $ head $ mapM3 return [1,2,3,4,undefined] [*** Exception: Prelude.undefined So, like foldl', mapM3 seems a viable alternative for mapM, but not a replacement. Wow. A 10x slowdown for a very commonly used function that in 99.8% of all use cases has no need for the extra laziness at all. No wonder some people say Haskell is a toy language... /Niklas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
niklas.broberg: 2) Is there a reason to not use mapM3 above? Yes, there certainly is. mapM3 is not equivalent to mapM; it is too strict: *Main take 3 $ head $ mapM return [1,2,3,4,undefined] [1,2,3] *Main take 3 $ head $ mapM3 return [1,2,3,4,undefined] [*** Exception: Prelude.undefined So, like foldl', mapM3 seems a viable alternative for mapM, but not a replacement. Wow. A 10x slowdown for a very commonly used function that in 99.8% of all use cases has no need for the extra laziness at all. No wonder some people say Haskell is a toy language... mapM_ is far more common, and optimised specially. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
