Strictness analyser missing useful strictness

Roman Beslik (beroal@ukr.net) writes: 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

Trac metadata

Trac field	Value
Version	6.12.1
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

changed weight to 5

added Tbug Trac import labels

Max Bolingbroke responds: 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.

1. GHC does not seem to be eta-expanding as much as it could get away

with. Generally eta expansion has the following effects:

• Decreases work sharing, by pushing let-binding and case decomposition within the lambda
• 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?

changed milestone to %7.0.2

changed milestone to %7.2.1

changed milestone to %7.4.1

changed milestone to %7.6.1

changed weight to 3

Trac metadata

Trac field	Value
Priority	normal → low

changed milestone to %7.6.2

This looks like it could be solved by the new callartiy analysis. It does not, though, because

• all the functions are top-level functions, and callartiy analysis only looks at local functions, and
• they are mutually recursive, which the callarity analysis does not handle yet.

Both could possibly be fixed, but both carry an implementation and maintenance cost, I’d like to do that lazily, i.e. depending on real-world use cases.

This looks like it can be solved by the new callartiy analysis. It does now, because

• all the functions are top-level functions, and callartiy analysis now also looks at top-level functions, and
• they are mutually recursive, which the callarity analysis does handle now.

Now we get these signatures:

$wf3 :: Int# -> Int# -> Int# -> Int#
$wf4 :: Int# -> Int# -> Int# -> Int# -> Int#

(and f2 has disappeared, by inlining I supposed).

Code is currently validating and will hit master soon after.

mentioned in commit d3c579c7

closed

Allright, pushed (mostly 2ab00bf7 and f347bfea) and testcase added.

This concludes my internship at MSRC; any further bugs introduced by me can no longer be blamed on “a microsoft employee”.

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed
Test case	→ callarity/perf/T3924

Terrific. What were the "nice numbers"?

Simon

Terrific. What were the "nice numbers"?

I was referring to the effect of call-arity to the (very artificial) code of this ticket: Allocation went from 22326544 to 51480.

added Plow label

added Arity and eta conversion label