strictness of unused arguments

older
undocumented cost centres with -hd...

Roman Beslik

11 Mar 2010 11 Mar '10

7:50 a.m.

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.

Show replies by date

Max Bolingbroke

11 Mar 11 Mar

4:33 p.m.

On 11 March 2010 12:50, Roman Beslik 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 2) GHC does not seem to be eta-expanding as much as it could get away with. Generally eta expansion has the following effects: a) Decreases work sharing, by pushing let-binding and case decomposition within the lambda b) Increases the efficiency of function calls and of the strictness analyser by pushing together several lambdas In this case the work that would be lost by eta expanding looks pretty minimal (its generally very cheap primops that we could easily recompute). However, to spot that this is actually safe GHC has to eta-expand all of the "f" functions simultaneously, because they are mutually recursive, and it turns out that their "cheapness" depends on the "cheapness" of every other function in the loop. The simplifier is not smart enough for this - you need a fixed point analysis. I did toy with an arity analysis that has been proposed to spot such opportunities, but I found that it could in some cases lose unbounded amounts of ostensibly "cheap" work - and it didn't seem to have much effect on nofib anyway, so this went nowhere. Looking at the Core, I think that if the arities were fixed up the strictness analyser *would* do the Right Thing here - so this might be another vote for an arity analysis :-) (See the "Arity" section of http://hackage.haskell.org/trac/ghc/wiki/Status/SLPJ-Tickets - it might be worth filing a bug on GHC Trac with your nice simple example too). Out of curiosity, did you spot this in a real program? Cheers, Max p.s. full Core output follows for those playing along at home: ==================== Demand analysis ==================== lvl_shD :: GHC.Types.Int -> GHC.Types.Int LclId [Arity 1 Str: DmdType S] lvl_shD = \ (x0_ado [ALWAYS Just S] :: GHC.Types.Int) -> x0_ado Rec { StrictUnusedArg.f4 [ALWAYS LoopBreaker Nothing] :: GHC.Types.Int -> GHC.Types.Int -> GHC.Types.Int -> GHC.Types.Int -> GHC.Types.Int LclIdX [Arity 2 Str: DmdType U(L)L] StrictUnusedArg.f4 = \ (x3_ads [ALWAYS Just U(L)] :: GHC.Types.Int) (eta_B1 [ALWAYS Just L] :: GHC.Types.Int) -> case x3_ads of _ { GHC.Types.I# x_ahS [ALWAYS Just L] -> case x_ahS of wild_X5 [ALWAYS Just L] { __DEFAULT -> let { a_sir [ALWAYS Just L] :: GHC.Prim.Int# LclId [Str: DmdType] a_sir = GHC.Prim.-# wild_X5 1 } in let { y_shm [ALWAYS Just D(L)] :: GHC.Types.Int LclId [Str: DmdType m] y_shm = GHC.Types.I# a_sir } in \ (x1_adv [ALWAYS Just L] :: GHC.Types.Int) (x0_adw [ALWAYS Just L] :: GHC.Types.Int) -> StrictUnusedArg.f4 y_shm eta_B1 x1_adv (case x0_adw of _ { GHC.Types.I# y_ai9 [ALWAYS Just L] -> GHC.Types.I# (GHC.Prim.+# a_sir y_ai9) }); 0 -> StrictUnusedArg.f3 eta_B1 } } StrictUnusedArg.f3 [ALWAYS LoopBreaker Nothing] :: GHC.Types.Int -> GHC.Types.Int -> GHC.Types.Int -> GHC.Types.Int LclIdX [Arity 1 Str: DmdType U(L)] StrictUnusedArg.f3 = \ (x2_adq [ALWAYS Just U(L)] :: GHC.Types.Int) -> case x2_adq of _ { GHC.Types.I# x_ahS [ALWAYS Just L] -> case x_ahS of wild_B1 [ALWAYS Just L] { __DEFAULT -> let { a_siv [ALWAYS Just L] :: GHC.Prim.Int# LclId [Str: DmdType] a_siv = GHC.Prim.-# wild_B1 1 } in let { y_shy [ALWAYS Just S(L)] :: GHC.Types.Int LclId [Str: DmdType m] y_shy = GHC.Types.I# a_siv } in StrictUnusedArg.f4 y_shy y_shy; 0 -> StrictUnusedArg.f2 } } StrictUnusedArg.f2 [ALWAYS LoopBreaker Nothing] :: GHC.Types.Int -> GHC.Types.Int -> GHC.Types.Int LclIdX [Arity 1 Str: DmdType U(L)] StrictUnusedArg.f2 = \ (x1_adj [ALWAYS Just U(L)] :: GHC.Types.Int) -> case x1_adj of _ { GHC.Types.I# x_ahS [ALWAYS Just L] -> case x_ahS of wild_B1 [ALWAYS Just L] { __DEFAULT -> let { a_six [ALWAYS Just L] :: GHC.Prim.Int# LclId [Str: DmdType] a_six = GHC.Prim.-# wild_B1 1 } in let { y_shB [ALWAYS Just S(L)] :: GHC.Types.Int LclId [Str: DmdType m] y_shB = GHC.Types.I# a_six } in StrictUnusedArg.f3 y_shB y_shB; 0 -> lvl_shD } } end Rec }

Roman Beslik

12 Mar 12 Mar

8:13 a.m.

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 Beslik 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.

Max Bolingbroke

8:38 a.m.

On 12 March 2010 13:13, Roman Beslik 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

Roman Beslik

11:17 a.m.

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.

5549

Age (days ago)

5550

Last active (days ago)

List overview

Download

4 comments

2 participants

participants (2)

Max Bolingbroke
Roman Beslik