Re: strictness of unused arguments
Thanks for the answer. Sorry, I can not follow all of your thoughts because my knowledge of strictness analysis and GHC optimizations are very basic. :( I looked into GHC code once several years ago. BTW there are a lot of papers about strictness analysis, but I do not know which is relevant for GHC. Can you suggest something? On 11.03.10 23:33, Max Bolingbroke wrote: On 11 March 2010 12:50, Roman Beslikber...@ukr.net wrote: I also can force the analyzer to think that x1 and x0 are strict by eta-expanding f3: There seem to be two issues here. 1) GHC only figures out and records strictness information on lambdas that are syntactically together. I'm not sure how hard it would be to change this, but probably not totally straightforward So GHC records strictness information for lambda-abstractions, not for function types? Eta-expansion changes strictness because it adds lambda-abstractions. 2) GHC does not seem to be eta-expanding as much as it could get away with. Generally eta expansion has the following effects I think it is better to go without eta-expansion. Eta-expansion (if not optimized when compiled) do absolutely useless job. I discovered its effect by an accident. Out of curiosity, did you spot this in a real program? It may be a real program. :) From the higher-level point of view: A list of Int-s is replaced by seed+coalgebra and a coalgebra is an automaton. The program generates lists and folds them, or in other words the program is a sequence of automata which feeds each other. The special feature is that states of all automata lay in stack, the program *does not allocate in the heap*. Of course, if it uses boxed Int-s, the very goal is missed. :( However, for now I can compose automata only by hand :( , I did not figured out a (.) function. -- Best regards, Roman Beslik. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: strictness of unused arguments
On 12 March 2010 13:13, Roman Beslik ber...@ukr.net wrote: Thanks for the answer. Sorry, I can not follow all of your thoughts because my knowledge of strictness analysis and GHC optimizations are very basic. :( I looked into GHC code once several years ago. BTW there are a lot of papers about strictness analysis, but I do not know which is relevant for GHC. Can you suggest something? There is nothing *published* (Simon has a half-written one lying around though), but the general approach is similar to that shown in Projections for strictness analysis at http://homepages.inf.ed.ac.uk/wadler/topics/strictness-analysis.html. Unfortunately the weird behaviour you are seeing is due to the demand transformer technology of GHC, which is one of the unpublished bits... So GHC records strictness information for lambda-abstractions, not for function types? Eta-expansion changes strictness because it adds lambda-abstractions. It records strictness info on *binders*, and it only records strictness info about lambdas that are syntactically manifest at the binder. So you get: let f = \z. bar e_1 g = foo e_2 e_3 in e_3 (\y. baz e_4) Then f gets strictness info about one argument, g about no arguments and the (\y. baz e_4) just doesn't stand a chance of getting improved at all. Eta expansion moves lambdas towards the binders, so it makes this approximation more effective, as you say. 2) GHC does not seem to be eta-expanding as much as it could get away with. Generally eta expansion has the following effects I think it is better to go without eta-expansion. Eta-expansion (if not optimized when compiled) do absolutely useless job. I discovered its effect by an accident. Eta-expansion happens quite a bit in GHC right now, though I'm not sure how important it is pragmatically. Probably quite important though - you might want to look up the state hack for a situation where it seems to be quite necessary. Sorry that I don't have an easy answer to your problem except eta-expand by hand! Cheers, Max ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: strictness of unused arguments
Thanks again. On 12.03.10 15:38, Max Bolingbroke wrote: There is nothing *published* (Simon has a half-written one lying around though), but the general approach is similar to that shown in Projections for strictness analysis at http://homepages.inf.ed.ac.uk/wadler/topics/strictness-analysis.html. Unfortunately the weird behaviour you are seeing is due to the demand transformer technology of GHC, which is one of the unpublished bits... -- Best regards, Roman Beslik. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
strictness of unused arguments
Hi all.
I provide a sample program which causes a strange behavior of strictness
analyzer.
variant 1 {{{
module StrictUnusedArg (main) where
f2 :: Int - Int - Int
f2 x1 = if x1 == 0 then (\x0 - x0) else let
y = x1 - 1
in f3 y y
f3 :: Int - Int - Int - Int
f3 x2 = if x2 == 0 then f2 else let
y = x2 - 1
in f4 y y
f4 :: Int - Int - Int - Int - Int
f4 x3 = if x3 == 0 then f3 else let
y = x3 - 1
in \x2 x1 x0 - f4 y x2 x1 (y + x0)
main = print (f2 100 0)
}}}
I expect that all arguments will be unboxed. -ddump-simpl reveals that
actually types are
{{{
f2 :: Int# - Int - Int
f3 :: Int# - Int - Int - Int
}}}
So when f3 calls f2 it unboxes the argument named x1 and when f2
calls f3 it boxes the argument named x1. -ddump-stranal knows
strictness only for the x2 of f3 and x1 of f2.
{{{
f2:
[Arity 1
Str: DmdType U(L)]
f3:
[Arity 1
Str: DmdType U(L)]
}}}
I also can force the analyzer to think that x1 and x0 are strict by
eta-expanding f3:
variant 2 {{{
f3 x2 x1 x0 = if x2 == 0 then f2 x1 x0 else let
y = x2 - 1
in f4 y y x1 x0
}}}
-ddump-stranal yields:
{{{
f3:
[Arity 3
Str: DmdType U(L)U(L)U(L)m]
f2:
[Arity 2
Str: DmdType U(L)U(L)m]
}}}
I even do not use ($!).
So, the questions: Is it possible to change the strictness analyzer so
it will treat variant 1 as variant 2? Are these changes big?
Compiled with options:
$ ghc --make -fstrictness -fPIC -O3 -fforce-recomp blah-blah-blah
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.12.1
--
Best regards,
Roman Beslik.
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
