[Haskell-beginners] Newbie performance question

[Jordan Ellis]

Thanks for the reply. I have a quick follow-up question: With optimization enabled, will a value be shared between recursive function calls? For example, in the following:
myRecursiveFunction 0 m = []myRecursiveFunction n m = m : myRecursiveFunction (n - 1) m
...will 'm' be calculated 'n' times, or just once? Thanks.
> From: daniel.is.fischer at web.de
> To: beginners at haskell.org
> Subject: Re: [Haskell-beginners] Newbie performance question
> Date: Sat, 16 Oct 2010 00:57:41 +0200
> CC: hookflash at hotmail.com
> 
> On Saturday 16 October 2010 00:03:42, Jordan Ellis wrote:
> > I'm trying (really trying!) to get my head around Haskell, but one
> > (among many) significant stumbling blocks for me so far has been trying
> > to figure out how my code is actually going to perform. Here's a
> > contrived example of the sort of thing that confuses me. Let's say I
> > have a function which produces a list of odd integers from 1 to n: f n =
> > filter (odd) [1..n]
> > ...and I have another function that makes a list of all sums of pairs of
> > odd numbers from 1 to n: g n = [a + b | a <- (f n), b <- (f n)]
> > I assume that in most languages, (f n) would get called twice (once for
> > a, and once for b), but what happens in Haskell? Does GHC recognize
> > that, since f is a pure function, it only has to be evaluated once for a
> > given n?
> 
> That depends. If you compile without optimisations, the list f n won't be 
> shared (that may of course change in future versions), if you compile with 
> optimisations, it will be shared.
> 
> GHC does very little common subexpression elimination, and CSE is not 
> always a good thing.
> 
> In the case above, it's fine for small n, but consider what happens for 
> large n. If the list is not shared, for every a you get a new application 
> of f (at least, that's GHC's current behaviour), and the algorithm runs in 
> constant space. If the list is shared, the entire list remains in memory 
> after it has been constructed for the first a. Thus the algorithm runs in 
> O(n) space (but it runs faster unless n is really large).
> In such cases, you can usually suppress undesired sharing with -fno-cse.
> 
> > If not, would a 'where clause' make any difference? e.g., g n =
> > [a + b | a <- h, b <- h] where h = f n
> 
> Yes, when compiled without optimisations, no when compiled with.
> In general, when you want a value to be shared, give it a name.
> It may be shared if you don't but with a name, a decent implementation will 
> share it.
> 
> > Thanks.
> 
 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20101016/888e3786/attachment.html