[GHC] #14816: Missed Called Arity opportunity?
#14816: Missed Called Arity opportunity?
-------------------------------------+-------------------------------------
Reporter: dfeuer | Owner: (none)
Type: bug | Status: new
Priority: normal | Milestone: 8.6.1
Component: Compiler | Version: 8.2.2
Keywords: | Operating System: Unknown/Multiple
Architecture: | Type of failure: Runtime
Unknown/Multiple | performance bug
Test Case: | Blocked By:
Blocking: | Related Tickets:
Differential Rev(s): | Wiki Page:
-------------------------------------+-------------------------------------
When I compile
{{{#!hs
test :: (a -> a -> a) -> Int -> a -> HashMap Int a -> HashMap Int a
test f k a m = insertModifying a (blink (f a)) k m
blink :: (a -> b) -> a -> (# b #)
-- Or blink g = \a -> (# g a #) ; it makes no difference.
blink g a = (# g a #)
}}}
I get
{{{
test
= \ (@ a_a9o3)
(f_a7iP :: a_a9o3 -> a_a9o3 -> a_a9o3)
(k_a7iQ :: Int)
(a1_a7iR :: a_a9o3)
(m_a7iS :: HashMap Int a_a9o3) ->
case k_a7iQ of { GHC.Types.I# ww1_sa1Z ->
RULES.$w$sinsertModifying
@ a_a9o3
a1_a7iR
(let {
g_s9E1 [Dmd=
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): Sorry. I commented here, but my comment seems to have disappeared… probably did not send it.
`insertModifying` uses its function argument at most once, so there is no possible benefit to this partial application.
but does GHC know this (non-local) fact? What is the strictness signature of `RULES.$w$sinsertModifying`. Also, what is the Core directly after Call Arity? (`-ddump-call-arity`)? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): Also, if call arity is too stupid, you might avoid the problem by using `oneShot` in the right place. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): nomeata, I finally came up with a standalone test case that exhibits the same (apparent) peculiarity. I don't really understand what you're asking, so I'm hoping this will help. {{{#!hs {-# language UnboxedTuples #-} module Fish where import Data.Array.ST import Control.Monad.ST.Strict import Control.Monad blink :: (a -> b) -> a -> (# b #) blink g a = (# g a #) test :: Int -> a -> (a -> a -> a) -> STArray s Int a -> ST s (STArray s Int a) test k a f m = insertModifyingArr k (blink (f a)) m {-# NOINLINE test #-} insertModifyingArr :: Int -> (a -> (# a #)) -> STArray s Int a -> ST s (STArray s Int a) insertModifyingArr i0 f arr0 = do rng <- range <$> getBounds arr0 go i0 rng arr0 where go i [] arr = pure arr go i (k : ks) arr | i == k = do old <- readArray arr i case f old of (# new #) -> writeArray arr i new return arr | otherwise = go i ks arr }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): It works if you don't export `insertModifyingArr`. Then it gets inlined into `test`, and CallArity, when looking at the binding of `g_s9E` in your original snippet, sees all the uses, sees that they are called at most once, and is happy to eta-expand it! But without inlining `insertModifyingArr`, this is beyond the reach of Call Arity, because it is not a higher-order analysis. Now, why does the demand analyser (which is higher-order, i.e. knows how functions call their arguments) not fix this? Because the demand analyser does not see that `insertModifyingArr` calls its argument only once, because the call is in a recursive loop. Sebastian Graf (@sgraf812) has thoughts on combining the analyses to give us the best of both worlds, maybe he can comment. For now, does {{{ import GHC.Magic blink :: (a -> b) -> a -> (# b #) blink g = oneShot $ \a -> (# g a #) }}} do what you want? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Your workaround does work. Inlining `insertModifying` (in the real-life case) is probably a bad idea. Your workaround does work. An alternative workaround does too: {{{#!hs test k a f m = insertModifyingArr k (oneShot $ blink (f a)) m }}} I'm glad to hear someone's been thinking about this issue; I'm much less glad that I've spent so much time coming up with a test case for something that's already known! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata):
I'm much less glad that I've spent so much time coming up with a test case for something that's already known!
Sorry about that – at least we have a good test case now for when someone pick this up again! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by sgraf): Hey, it seems I'm lucky I subscribed to ghc-ticket just yesterday :) I investigated a little. So, it turns out that Demand Analysis doesn't recognize `insertModifyingArr`s argument `f` to be called once (has usage `C(U(U)`). That's really weird, actually the analysis should be able to figure that out. The fact that `-ddump-stranal` doesn't mention `f` in the demand type as a free variable to `go` makes me feel like there is some conservative approximation at play here. And in fact, I believe that's how fix-pointing works for functions in DmdAnal: Completely forget about free variables and assume the most pessimistic result. You can circumvent that if you make `f` an argument to `go` (reverse static arg transform, essentially): {{{ insertModifyingArr :: Int -> (a -> (# a #)) -> STArray s Int a -> ST s (STArray s Int a) insertModifyingArr i0 f arr0 = do rng <- range <$> getBounds arr0 go f i0 rng arr0 where go f i [] arr = pure arr go f i (k : ks) arr | i == k = do old <- readArray arr i case f old of (# new #) -> writeArray arr i new return arr | otherwise = go f i ks arr }}} This makes DmdAnal propagate the usage information to the top-level: The demand signature for `inserModifyingArr` mentions `f` with usage `1*C1(U(U))`, which in theory should be enough information for the simplifier to eta-expand the `blink` expression. And sure enough, it does (somewhere inside `test`: {{{ Fish.insertModifyingArr_$spoly_go @ a_a3IX @ s_a3IY w_s4pP ww6_s4s2 ww8_s4s5 ww3_s4q2 ww4_s4q3 (GHC.Enum.eftInt ww6_s4s2 ww8_s4s5) k_a15T (\ (a2_a15S [OS=OneShot] :: a_a3IX) -> (# f_a15V a1_a15U a2_a15S #)) }}} The interactions between free vars and static args are a little counter- intuitive, I suppose... -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata):
You can circumvent that if you make f an argument to go (reverse static arg transform, essentially):
That’s smart! By making it an argument, you essentially tell GHC to apply inductive reasoning, and then the Demand Analyzer finds out that `f` is used at most once! Cool. And I presume if the recursion were non-linear, it would also do the right thing… So – can we just include the free variables in the strictness signature during fixpointing and get that optimization without the code transformation? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
So – can we just include the free variables in the strictness signature during fixpointing and get that optimization without the code
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by sgraf): Replying to [comment:8 nomeata]: transformation? Well, actually I had expected DmdAnal to just work here. Not sure why `f` doesn't end up in `go`s signature, I suspected this has something to do with this `Lazy and unleashable free variables` hack, but I'm not so sure anymore. I'll investigate. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by sgraf): * cc: sgraf (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by sgraf): OK, this is due to the call to [https://github.com/ghc/ghc/blob/81a5e05d376c075a38e55bc124ea6226c1f3bef7/com... reuseEnv here] (that function effectively duplicates every demand, so `1*C1(U(U)) -> C(U(U))`) with the explanation in `Aggregated demand for cardinality`, the gist of which is that we have to treat free variables of let-bound thunks differently in usage analysis than we would like to for strictness analysis. I think this should only be relevant for thunks, e.g. we should first `splitFVs is_thunk rhs_fv` and only then `reuseEnv` the `lazy_fv`. I'll give that a shot. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14816: Missed Called Arity opportunity?
-------------------------------------+-------------------------------------
Reporter: dfeuer | Owner: (none)
Type: bug | Status: new
Priority: normal | Milestone: 8.6.1
Component: Compiler | Version: 8.2.2
Resolution: | Keywords:
Operating System: Unknown/Multiple | Architecture:
Type of failure: Runtime | Unknown/Multiple
performance bug | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s):
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by sgraf):
OK, that didn't work, but for reasons I didn't expect. If we apply that
change, suddenly some bindings get *worse* *strictness* annotations,
although it should only make for *less conservative* (possibly unsound)
*usage* annotations, as `reuseEnv` will only affect usage information.
It turns out that this is due to the interaction between the lazy fv hack
and the fix-pointing algorithm. An example is adapted from T876:
{{{
foo :: Int -> Int
foo n = sum [ length [i..n] | i <- [1..n] ]
main = print (foo 100)
}}}
The variant that does get rid of the call to `reuseEnv` altogether will
produce something like this code:
{{{
foo
= \ (n_aYV [Dmd=
#14816: Missed Called Arity opportunity?
-------------------------------------+-------------------------------------
Reporter: dfeuer | Owner: (none)
Type: bug | Status: new
Priority: normal | Milestone: 8.6.1
Component: Compiler | Version: 8.2.2
Resolution: | Keywords:
Operating System: Unknown/Multiple | Architecture:
Type of failure: Runtime | Unknown/Multiple
performance bug | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s):
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by sgraf):
I spent some time thinking about how to implement this, but given that
`lazy_fvs` plays a largely different role for thunks (unleashes strictness
through signatures and stores usage in `lazy_fvs`) vs. non-thunks (puts
weak demands into `lazy_fvs`, e.g. `
#14816: Missed Called Arity opportunity? -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.10.1 Component: Compiler | Version: 8.2.2 Resolution: | Keywords: | DemandAnalysis Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => DemandAnalysis -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14816#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC