Opened 8 years ago

Closed 4 years ago

Last modified 4 years ago

#3924 closed bug (fixed)

Strictness analyser missing useful strictness

Reported by: simonpj Owned by:
Priority: low Milestone: 7.6.2
Component: Compiler Version: 6.12.1
Keywords: Cc: beroal@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case: callarity/perf/T3924
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Roman Beslik (beroal@…) 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

Change History (14)

comment:1 Changed 8 years ago by simonpj

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?

comment:2 Changed 7 years ago by igloo

Milestone: 6.14.1

comment:3 Changed 7 years ago by simonpj

Cc: beroal@… added

comment:4 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:5 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:6 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:7 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: normallow

comment:8 Changed 5 years ago by igloo

Milestone: 7.6.17.6.2

comment:9 Changed 4 years ago by nomeata

difficulty: Unknown

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.

comment:10 Changed 4 years ago by nomeata

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.

comment:11 Changed 4 years ago by Joachim Breitner <mail@…>

In d3c579c75ffec4346a043582d89205998790145e/ghc:

Call arity testcase for #3924

nice numbers coming from these micro-benchmarks.

comment:12 Changed 4 years ago by nomeata

Resolution: fixed
Status: newclosed
Test Case: callarity/perf/T3924

Allright, pushed (mostly 2ab00bf and f347bfe) and testcase added.

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

comment:13 Changed 4 years ago by simonpj

Terrific. What were the "nice numbers"?

Simon

comment:14 Changed 4 years ago by nomeata

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.

Note: See TracTickets for help on using tickets.