Opened 4 years ago

Closed 3 years ago

#11383 closed bug (fixed)

CAFs lose sharing due to implicit call stacks

Reported by: simonmar Owned by: gridaphobe
Priority: normal Milestone: 8.0.1
Component: Compiler Version: 8.0.1-rc1
Keywords: Cc: simonpj, chak, j.waldmann
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: #11298 Differential Rev(s): Phab:D1912
Wiki Page:

Description

The implicit call stack machinery adds a constraint to CAFs, which loses sharing in some cases. The regression is fixed by -O (actually -ffull-laziness), but it is surprising nonetheless, and might cause problems for people using GHCi or other places where -O is turned off.

For example:

{-# LANGUAGE NoMonomorphismRestriction #-}
module Main where

import System.Environment

fib :: Integer -> Integer
fib n = if n < 2 then 1 else fib (n-1) + fib (n-2)

x = if fib 3 > 20 then error "x" else fib 30

main = do
  [n] <- getArgs
  case n of
    "a" -> print (x + x)
    "b" -> print x

Try it as follows (requires 8.0+):

$ ghc imp.hs -fforce-recomp -O -fno-full-laziness
$ ./imp a +RTS -t
2692538
<<ghc: 430859568 bytes, 822 GCs, 36580/44384 avg/max bytes residency (2 samples), 1M in use, 0.000 INIT (0.000 elapsed), 0.156 MUT (0.203 elapsed), 0.018 GC (0.009 elapsed) :ghc>>
$ ./imp b +RTS -t
1346269
<<ghc: 215456192 bytes, 411 GCs, 36580/44384 avg/max bytes residency (2 samples), 1M in use, 0.000 INIT (0.000 elapsed), 0.073 MUT (0.119 elapsed), 0.008 GC (0.004 elapsed) :ghc>>

With GHC 7.10 and earlier both commands perform the same.

Note that this only uses error, and doesn't require ImplicitParams. It does require NoMonomorphismRestriction, however.

Change History (10)

comment:1 Changed 4 years ago by simonmar

We may or may not consider this a bug, so I'm reporting it for discussion. Arguably it's the same as using any overloaded function in a CAF together with NoMonomorphismRestriction, the surprising bit is that error is now "overloaded".

comment:2 Changed 4 years ago by gridaphobe

As you said, this is really just the monomorphism restriction (or in this case the lack thereof) at work. The two pieces that contribute to this behavior are:

  1. error is now overloaded with an implicit parameter, the call-stack.
  2. GHC infers implicit parameters (including call-stacks) as needed, unless there's an explicit signature or the monomorphism restriction applies.

There's a similar report in #11298, see the two definitions of fooHelper.

We could avoid this (potentially confusing) behavior for the most part by not inferring call-stacks for top-level definitions. I'm a bit reluctant to do so because it makes call-stacks less like implicit parameters, and would require another special case in the type-checker. One of the things I like about the current version of the call-stack solver is how similar implicit call-stacks are to regular implicit parameters.

---

I'm actually more concerned about the fact that -ffull-laziness changes the behavior. Does this mean we're caching the first call-stack? That would be completely wrong; it would be wrong for any implicit parameter.

comment:3 Changed 4 years ago by simonmar

-ffull-laziness lifts the expensive computation outside the implicit parameter, so recovering the sharing that was lost by the introduction of the implicit parameter constraint. It doesn't change the meaning.

This is only an issue for CAFs, because functions already have a lambda at the outside so there's no sharing to lose. (CAFs are a notorious problem for stack tracing, incidentally, because you get to choose between losing sharing and losing information)

comment:4 Changed 4 years ago by simonmar

I suppose if what you were trying to share was itself something that had an implicit call stack parameter, then full-laziness wouldn't be able to fix it. Which is a bigger problem, but still arguably the same issue that the monomorphism restriction was intended to fix. The user gets to choose between having sharing or a call stack when they write the type signature.

comment:5 Changed 4 years ago by thomie

Type of failure: None/UnknownRuntime performance bug

comment:6 Changed 4 years ago by chak

Cc: chak added

Haskell performance is tricky to reason about as it is. Adding more complexity seems worrying.

comment:7 Changed 4 years ago by gridaphobe

Differential Rev(s): Phab:D1912
Status: newpatch

This will be (partially) fixed by D1912, which prevents GHC from inferring CallStack constraints for top-level definitions. You could still create the issue by making x a local binder inside main, but then again, the monomorphism restriction will usually be turned on and will prevent the inference.

On a related note, do we have a warning (or less severely, a note) for when we infer a polymorphic type that the monomorphism restriction would have prevented? That might be useful to pair with NoMonomorphismRestriction.

comment:8 in reply to:  7 Changed 4 years ago by rwbarton

Replying to gridaphobe:

On a related note, do we have a warning (or less severely, a note) for when we infer a polymorphic type that the monomorphism restriction would have prevented? That might be useful to pair with NoMonomorphismRestriction.

I agree this would be nice; I've always wished the monomorphism restriction was instead a warning like this.

There is -fwarn-monomorphism-restriction, but it does the reverse: when the monomorphism restriction is on, it warns about bindings that it applies to.

comment:9 Changed 4 years ago by j.waldmann

Cc: j.waldmann added

comment:10 Changed 3 years ago by bgamari

Resolution: fixed
Status: patchclosed

Phab:D1912 has been merged.

Note: See TracTickets for help on using tickets.