Hi folks, sorry for multiple copies of this email, but my mailserver had a problem and thought I am sending spam which is hopefully not true. Since I got a replay allready I modified my mail a bit. I was wondering why we don't have an annotation or pragma for function to tell the compiler that we _need_ this particular recursive function to be unfolded. If the compiler cannot do this for some reason it should produce an error message to help you modifying your code. I have regularly problems that my code is either not strict enough or my functions are not unfolded. I find it annoying that this is a regular show stopper and consumes much time to fix. Here is an example: a search function for strings, which should return the index and the rest of the string after the first occurrence: search0 will not be unfolded by ghc -O even with {#- INLINE search0 -#} (I don't know why, it looks tail-recursive to me) whereas search1 is just fine. search0 :: Int -> String -> String -> (String, Int) search0 i [] _ = ([],i) search0 i haystack needle = let len = length needle in if isPrefixOf needle haystack then (drop len haystack, i+len) else search0 (seq i (i+1)) (drop 1 haystack) needle search1 :: Int -> String -> String -> (String, Int) search1 i [] _ = ([],i) search1 i haystack needle = let i = elemIndex True $ map (isPrefixOf needle) $ tails haystack len = length needle in case i of Just index -> (drop (index+len) haystack, index + len) Nothing -> ([],0) Regards! Georg -- ---- Georg Martius, Tel: +49 177 6413311 ----- ------- http://www.flexman.homeip.net ----------
| I was wondering why we don't have an annotation or pragma for function to tell | the compiler that we _need_ this particular recursive function to be unfolded. | If the compiler cannot do this for some reason it should produce an error | message to help you modifying your code. I have regularly problems that my | code is either not strict enough or my functions are not unfolded. I find it | annoying that this is a regular show stopper and consumes much time to fix. | Here is an example: a search function for strings, which should return the | index and the rest of the string after the first occurrence: search0 will not | be unfolded by ghc -O even with {#- INLINE search0 -#} (I don't know why, it | looks tail-recursive to me) GHC never inlines recursive functions. Why not? Because doing so exposes a new inline opportunity. How many times would you like it inlined? Not forever, I assume! Some compilers unroll recursive functions by inlining them N times, for some fixed N (say 3 or so). This reduces the loop overheads. GHC doesn't do this, although it'd be nice, because it makes repeated traversals of the code, and it's hard to spot when the function has been unrolled 3 times and then stop. If you look at the code after unrolling 3 times, from scratch, there's another call just waiting to be inlined. I'm not saying this couldn't be improved -- but I don't see an easy way to improve it. Simon
Hello Simon, Tuesday, July 31, 2007, 1:22:14 PM, you wrote:
GHC never inlines recursive functions. Why not? Because doing so exposes a new inline opportunity. How many times would you like it inlined? Not forever, I assume!
really, state of things in this area is not pleasant. making polymorphic function recursive kills the performance because it's no more inlined nor specialized - it may be called only with real dictionary. because i'm wrote polymorphic i/o library, i had many situations when in rare cases functions should call itself recursively like this: getChar = if bufferEmpty then fillBuffer; getChar else return *p++ (sorry for some pseudocode) and it was very inefficient. at the last end, i was need to create special functions to handle recursive calls and call it when buffer empty so that main function becomes non-recursive: getChar = if bufferEmpty then getChar' else return *p++ getChar' = fillBuffer; getChar it will be great if specifying INLINE for recursive function will mean that it should be inlined at least once and then call to non-polymorphic specialized version should be made. at least it will be ideal for code like this -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
Hi Simon, thanks for the answer! I see why inlining is not a good idea, but why is it not unfolded. I mean we don't need any true recursion if the function is tail-recursive or am I mistaken? However my point was more on a semantic point of view: If I write a function in a recursive way, but actually do nothing else than a loop, I would like a) that the compiler unrolls it to a loop and b) that I can specify such a requirement, while violating it emits an error. I believe it would help to write the intended code straight away, especially for less advanced Haskell programmers, which don't know about the optimization details of the compiler. Cheers, Georg On Tuesday 31 July 2007 11:22, you wrote:
| I was wondering why we don't have an annotation or pragma for function to | tell the compiler that we _need_ this particular recursive function to be | unfolded. If the compiler cannot do this for some reason it should | produce an error message to help you modifying your code. I have | regularly problems that my code is either not strict enough or my | functions are not unfolded. I find it annoying that this is a regular | show stopper and consumes much time to fix. Here is an example: a search | function for strings, which should return the index and the rest of the | string after the first occurrence: search0 will not be unfolded by ghc -O | even with {#- INLINE search0 -#} (I don't know why, it looks | tail-recursive to me)
GHC never inlines recursive functions. Why not? Because doing so exposes a new inline opportunity. How many times would you like it inlined? Not forever, I assume!
Some compilers unroll recursive functions by inlining them N times, for some fixed N (say 3 or so). This reduces the loop overheads. GHC doesn't do this, although it'd be nice, because it makes repeated traversals of the code, and it's hard to spot when the function has been unrolled 3 times and then stop. If you look at the code after unrolling 3 times, from scratch, there's another call just waiting to be inlined.
I'm not saying this couldn't be improved -- but I don't see an easy way to improve it.
Simon
| However my point was more on a semantic point of view: If I write a function | in a recursive way, but actually do nothing else than a loop, I would like | a) that the compiler unrolls it to a loop and | b) that I can specify such a requirement, while violating it emits an error. What does it mean to say "the compiler unrolls it to a loop". If GHC sees a tail recursive function, it certainly compiles it to a loop! (But that's not called "unrolling".) Simon
On Jul 31, 2007, at 10:20 AM, Simon Peyton-Jones wrote:
| However my point was more on a semantic point of view: If I write a function | in a recursive way, but actually do nothing else than a loop, I would like | a) that the compiler unrolls it to a loop and | b) that I can specify such a requirement, while violating it emits an error.
What does it mean to say "the compiler unrolls it to a loop". If GHC sees a tail recursive function, it certainly compiles it to a loop! (But that's not called "unrolling".)
I think what's meant here is translating something like this: {-# INLINE f #-} f x y z = ... f x' y' z' ... into this: {-# INLINE f #-} f x y z = f' x y z where f' x y z = ... f' x' y' z' ... That is, shoving (all of) the recursion in a level. Then inlining f results in a fresh loop, which presumably can be specialized or optimized in various ways. I did this in pH, mostly because it was less irritating than performing the same transformation by hand on key bits of the Prelude. Whether it's actually beneficial on a large scale probably depends on the effectiveness of transformations that can specialise f' to the site where it was inlined; invariant argument elimination comes to mind here, and I never did a good job with that. It does remove one irritant from performance tuning, though, by letting us write a simple top-level recursive function and have it inlined. -Jan
Simon _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
On Tue, 2007-07-31 at 10:36 -0400, Jan-Willem Maessen wrote:
I think what's meant here is translating something like this:
{-# INLINE f #-} f x y z = ... f x' y' z' ...
into this:
{-# INLINE f #-} f x y z = f' x y z where f' x y z = ... f' x' y' z' ...
That is, shoving (all of) the recursion in a level. Then inlining f results in a fresh loop, which presumably can be specialized or optimized in various ways.
This transformation is critical for performance of foldr and foldl('). The versions in GHC's libraries are manually written in the latter style. Duncan
| > {-# INLINE f #-} | > f x y z = ... f x' y' z' ... | > | > into this: | > | > {-# INLINE f #-} | > f x y z = f' x y z | > where f' x y z = ... f' x' y' z' ... | > | > That is, shoving (all of) the recursion in a level. Then inlining f | > results in a fresh loop, which presumably can be specialized or | > optimized in various ways. | | This transformation is critical for performance of foldr and foldl('). | The versions in GHC's libraries are manually written in the latter | style. It's important if and only if one or more of the parameters is static -- that is, passed on unchanged. HTis is not the case in the example above. If you have g x y z = .... (g x y' z') ....x... then indeed it's sometimes a good plan to transform to g x y z = g' y z where g' y z = ....(g' y' z')...x.... because now you can inline g, and thereby specialise for the value of x at the call site. This is esp good if x is a function. Simon
Hi, I am sorry for using the wrong terminology here. Let me ask again: Does it sound reasonable to extend the compiler with a pragma that specifies that a certain function should be compiled to a loop? And if the compiler can not do it, it helps with some error message. Regards! Georg On Tuesday 31 July 2007 16:20, Simon Peyton-Jones wrote:
| However my point was more on a semantic point of view: If I write a | function in a recursive way, but actually do nothing else than a loop, I | would like a) that the compiler unrolls it to a loop and | b) that I can specify such a requirement, while violating it emits an | error.
What does it mean to say "the compiler unrolls it to a loop". If GHC sees a tail recursive function, it certainly compiles it to a loop! (But that's not called "unrolling".)
Simon
-- ---- Georg Martius, Tel: +49 177 6413311 ----- ------- http://www.flexman.homeip.net ----------
On Wed, Aug 01, 2007 at 09:42:54AM +0200, Georg Martius wrote:
Hi,
I am sorry for using the wrong terminology here. Let me ask again: Does it sound reasonable to extend the compiler with a pragma that specifies that a certain function should be compiled to a loop? And if the compiler can not do it, it helps with some error message.
Unfortunately, that's still almost useless in the presence of laziness. Take the following (contrived) example: fib :: Int -> (Int,Int) -> (Int,Int) fib 0 p = p fib k p = fib (k-1) (snd p, fst p + snd p) That compiles to a perfectly reasonable loop: (minor code rearrangement and bounds-checks deleted for clarity) X_zdszdwfib_info: Hp = Hp + 16; _sjD = I32[Sp + 8]; if (_sjD == 0) goto clk; _sjF = _sjD - 1; I32[Hp - 12] = sjC_info; I32[Hp - 4] = I32[Sp + 4]; I32[Hp] = I32[Sp]; I32[Sp + 8] = _sjF; I32[Sp + 4] = I32[Sp]; I32[Sp] = Hp - 12; jump X_zdszdwfib_info (); clk: I32[Hp - 12] = base_DataziTuple_Z2T_con_info; I32[Hp - 8] = I32[Sp + 4]; I32[Hp - 4] = I32[Sp]; R1 = Hp - 12; Sp = Sp + 12; Hp = Hp - 4; jump I32[Sp] (); Yet still: Prelude X> fib 10000000 (1,1) (*** Exception: stack overflow Since while *your function* may be a loop, the thunks it builds are evaluated in a way that isn't. Stefan
If it's tail recursive it'll be compiled to a loop. You don't need a pragma. Of course if it does evaluation along the way, it'll have to make a call do to that evaluation. E.g. f x = if x>0 then 0 else f (g x) Here f is tail-rec but it'll have to call g inside the loop. Simon | -----Original Message----- | From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users-bounces@haskell.org] On | Behalf Of Georg Martius | Sent: 01 August 2007 08:43 | To: Simon Peyton-Jones; Glasgow-haskell-users@haskell.org | Subject: Re: Annotation for unfolding wanted | | Hi, | | I am sorry for using the wrong terminology here. Let me ask again: | Does it sound reasonable to extend the compiler with a pragma that specifies | that a certain function should be compiled to a loop? And if the compiler can | not do it, it helps with some error message. | | Regards! | Georg | | On Tuesday 31 July 2007 16:20, Simon Peyton-Jones wrote: | > | However my point was more on a semantic point of view: If I write a | > | function in a recursive way, but actually do nothing else than a loop, I | > | would like a) that the compiler unrolls it to a loop and | > | b) that I can specify such a requirement, while violating it emits an | > | error. | > | > What does it mean to say "the compiler unrolls it to a loop". If GHC sees | > a tail recursive function, it certainly compiles it to a loop! (But that's | > not called "unrolling".) | > | > Simon | | -- | ---- Georg Martius, Tel: +49 177 6413311 ----- | ------- http://www.flexman.homeip.net ----------
Simon Peyton-Jones wrote:
If it's tail recursive it'll be compiled to a loop. You don't need a pragma.
The ~pragma is in order to make an error if it's not a loop. Same way as we don't need type-signatures in export lists and their only purpose is to cause errors when something unexpected and undesirable happens. Isaac
Some compilers unroll recursive functions by inlining them N times, for some fixed N (say 3 or so). This reduces the loop overheads. GHC doesn't do this, although it'd be nice, because it makes repeated traversals of the code, and it's hard to spot when the function has been unrolled 3 times and then stop. If you look at the code after unrolling 3 times, from scratch, there's another call just waiting to be inlined.
couldn't the number of unfoldings be encoded in the name of the function? f x = if p x then x else f (g x) f x = if p x then x else let x' = (g x) in if p x' then x' else f#1 (g x') where f#1 would be f for all other purposes, but with one unfolding used up, and N being the bound for the f#i. claus
participants (8)
-
Bulat Ziganshin -
Claus Reinke -
Duncan Coutts -
Georg Martius -
Isaac Dupree -
Jan-Willem Maessen -
Simon Peyton-Jones -
Stefan O'Rear