RE: Annotation for unfolding wanted
| 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
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re[2]: Annotation for unfolding wanted
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, Bulatmailto:[EMAIL PROTECTED] ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Ticky Ticky profiling
Hi all!. I modified build.mk in order to allow Ticky-Ticky profiling (GhcLibWays=t). Now, when I try to make I get this error: == make way=t all; PWD = (the_whole_path)/ghc-6.6.1/rts ../compiler/ghc-inplace -H32m -O -fasm -W -fno-warn-unused-matches -fwarn-unused-imports -optc-O2 -static -I. -#include HCIncludes.h -fvia-C -dcmm-lint -hisuf t_hi -hcsuf t_hc -osuf t_o -ticky -#include posix/Itimer.h -c PrimOps.cmm -o PrimOps.t_o ghc-6.6.1: panic! (the 'impossible' happened) (GHC version 6.6.1 for i386-unknown-linux): ToDo: tickyAllocThunk Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug Any clue? Thanks in advance. Cristian Perfumo. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Annotation for unfolding wanted
| 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 ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Annotation for unfolding wanted
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
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Annotation for unfolding wanted
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
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Annotation for unfolding wanted
| {-# 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
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Ticky Ticky profiling
On 7/31/07, Cristian Perfumo [EMAIL PROTECTED] wrote: Hi all!. I modified build.mk in order to allow Ticky-Ticky profiling (GhcLibWays=t). Now, when I try to make I get this error: == make way=t all; PWD = (the_whole_path)/ghc-6.6.1/rts ../compiler/ghc-inplace -H32m -O -fasm -W -fno-warn-unused-matches -fwarn-unused-imports -optc-O2 -static -I. -#include HCIncludes.h -fvia-C -dcmm-lint -hisuf t_hi -hcsuf t_hc -osuf t_o -ticky -#include posix/Itimer.h -c PrimOps.cmm -o PrimOps.t_o ghc-6.6.1: panic! (the 'impossible' happened) (GHC version 6.6.1 for i386-unknown-linux): ToDo: tickyAllocThunk Hi, Cristian-- To get ticky to work, you need the HEAD (or a recent nightly build snapshot). If it's still not working after that, post again. Cheers, Tim -- Tim Chevalier* catamorphism.org *Often in error, never in doubt More than at any other time in history, mankind faces a crossroads. One path leads to despair and utter hopelessness. The other, to total extinction. Let us pray we have the wisdom to choose correctly.--Woody Allen ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
