<div dir="ltr">Dan, I really appreciate that you responded so quickly and took the time to explain this. Unfortunately I still don't understand.<div><br></div><div>I did think of laziness as a potential source of bad performance but to me both internal functions were lazy in the second argument. Since I couldn't explain why both weren't equally slow due to laziness, I dismissed laziness as a possible source of the problem instead of questioning my understanding of laziness. <div><br></div><div>I still don't understand why <div><br></div></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><div><font face="monospace, monospace">as'<div class="gmail_default" style="font-family:'times new roman',serif;font-size:large;display:inline"> </div>i s</font></div></div></div><div><div><div><font face="monospace, monospace"> | i >= n = s</font></div></div></div><div><div><div><font face="monospace, monospace"> | otherwise = as' (i + 2) (s + (-1) / i + 1 / (i + 1))</font></div></div></div></blockquote><div><div><br></div><div>is not lazy in its second arg as it only has to evaluate it if i >= n. This seems exactly analogous to or, ||, which only needs to evaluate its second arg if its first arg is False. || is definitely lazy in its second argument. Can you explain why as' is strict in its second arg, s? Is it due to the following from, <a href="https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Demand" target="_blank">https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Demand</a> ?</div><div><br></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px">For functions, it is assumed, that the result of the function is used strictly.</blockquote><br>I guess I should have checked my intuition against the compiler strictness analysis. I modified sum.hs to only have a definition of sumr, commenting out sumh and tried the various tools.<br><br>The user's guide, <a href="https://downloads.haskell.org/~ghc/8.0.1-rc2/docs/html/users_guide/sooner.html#faster-producing-a-program-that-runs-quicker">https://downloads.haskell.org/~ghc/8.0.1-rc2/docs/html/users_guide/sooner.html#faster-producing-a-program-that-runs-quicker</a>, recommends:<br><br><blockquote style="margin:0 0 0 40px;border:none;padding:0px">Look for your function in the interface file, then for the third field in the pragma; it should say Strictness: ⟨string⟩. The ⟨string⟩ gives the strictness of the function’s arguments: see the GHC Commentary for a description of the strictness notation.</blockquote><br>It doesn't mention that the interface file is binary and that you need to use ghc --show-iface, e.g.<br><br><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><font face="monospace, monospace">ghc --show-iface sum.hi > sum.hir</font></blockquote><br>Doing this seems to give the wrong answer, i.e. the second arg is lazy.<br><br> <font face="monospace, monospace">$was' :: Double# -> Double# -> Double#<br> {- Arity: 2, Strictness: <S,U><<b>L</b>,U>, Inline: [0] -}</font><br><br>Is this a bug?<br><br>ghc -ddump-stranal -O sum.hs gives the right answer:<br><br><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><font face="monospace, monospace">as'_s25G [Occ=LoopBreaker] :: Double -> Double -> Double<br> [LclId,<br> Arity=2,<br> CallArity=2,<br> Str=DmdType <S(S),1*U(U)><<b>S</b>,1*U(U)>m {avM-><S(S),U(U)>},<br> Unf=Unf{Src=<vanilla>, TopLvl=False, Value=True, ConLike=True,<br> WorkFree=True, Expandable=True, Guidance=IF_ARGS [20 20] 108 0}]</font></blockquote><br>Unfortunately the simplest way to find out doesn't give information on internal functions. I will file an ER for this:<br><br><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><font face="monospace, monospace"> ghc -ddump-strsigs -O sum.hs<br>[1 of 1] Compiling Main ( sum.hs, sum.o )<br>==================== Strictness signatures ====================<br>:Main.main:<br>Main.$trModule: m<br>Main.main: x<br>Main.sumr: <S(S),U(U)>m</font></blockquote><br>I really like your definition of until' as the solution to this. To me it seems analogous to foldl', in that it provides a way to avoid an optimization problem that may be subtle to many. I guess it is not general enough to be added to a library. The following world be general enough but it would probably be overkill:<br><br><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><font face="monospace, monospace">until' :: NFData a => (a -> Bool) -> (a -> a) -> a -> a<br>until' p f = go<br> where<br> go x | p $!! x = x<br> | otherwise = go (f x)</font></blockquote><br><br>Thanks again for all your help<br>George<br><div><div><br></div><div><br><div class="gmail_quote"><div dir="ltr">On Sat, Mar 26, 2016 at 5:40 PM Dan Doel <<a href="mailto:dan.doel@gmail.com" target="_blank">dan.doel@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">By the way, in case this helps your mental model, if you modify sumr to be:<br>
<br>
sumr n = snd $ as' 1 0<br>
where<br>
as' i s<br>
| i >= n = (i, s)<br>
| otherwise = ...<br>
<br>
Then it has the same problem as sumh. Your original as' for sumr is<br>
strict in s, but this modified one isn't.<br>
<br>
This shows another way to fix sumh, too. Create a version of until<br>
that separates out the part of the state that is only for testing.<br>
Then the until loop will be strict in the result part of the state,<br>
and the desired optimizations will happen (in this case):<br>
<br>
until' p step = go<br>
where<br>
go t r<br>
| p t = r<br>
| otherwise = uncurry go $ step (t, r)<br>
<br>
-- Dan<br>
<br>
On Sat, Mar 26, 2016 at 1:50 PM, George Colpitts<br>
<<a href="mailto:george.colpitts@gmail.com" target="_blank">george.colpitts@gmail.com</a>> wrote:<br>
> The following higher order function, sumh, seems to be 3 to 14 times slower<br>
> than the equivalent recursive function, sumr:<br>
><br>
> sumh :: Double -> Double<br>
> sumh n =<br>
> snd $ until ((>= n) . fst) as' (1, 0)<br>
> where<br>
> as' (i,s) =<br>
> (i + 2, s + (-1) / i + 1 / (i + 1))<br>
><br>
> sumr :: Double -> Double<br>
> sumr n =<br>
> as' 1 0<br>
> where<br>
> as' i s<br>
> | i >= n = s<br>
> | otherwise = as' (i + 2) (s + (-1) / i + 1 / (i + 1))<br>
><br>
> This is true in 7.10.3 as well as 8.0.1 so this is not a regression. From<br>
> the size usage my guess is that this is due to the allocation of tuples in<br>
> sumh. Maybe there is a straightforward way to optimize sumh but I couldn't<br>
> find it. Adding a Strict pragma didn't help nor did use of<br>
> -funbox-strict-fields -flate-dmd-anal. Have I missed something or should I<br>
> file a bug?<br>
><br>
> Timings from 8.0.1 rc2:<br>
><br>
> ghc --version<br>
> The Glorious Glasgow Haskell Compilation System, version 8.0.0.20160204<br>
> bash-3.2$ ghc -O2 -dynamic sum.hs<br>
> ghc -O2 -dynamic sum.hs<br>
> [1 of 1] Compiling Main ( sum.hs, sum.o )<br>
> Linking sum ...<br>
> bash-3.2$ ghci<br>
> Prelude> :load sum<br>
> Ok, modules loaded: Main.<br>
> (0.05 secs,)<br>
> Prelude Main> sumh (10^6)<br>
> -0.6931466805602525<br>
> it :: Double<br>
> (0.14 secs, 40,708,016 bytes)<br>
> Prelude Main> sumr (10^6)<br>
> -0.6931466805602525<br>
> it :: Double<br>
> (0.01 secs, 92,000 bytes)<br>
><br>
> Thanks<br>
> George<br>
><br>
> _______________________________________________<br>
> ghc-devs mailing list<br>
> <a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
><br>
</blockquote></div></div></div></div>