Speculative evaluation can cause a large increase in allocations

added Phigh Tbug core prep and lowering runtime perf labels and removed needs triage label

We've found that for cardano-node speculative evaluation introduced in the coreprep stage can cause a large increase in allocations. Some dictionaries get created a lot more because of this transformation.

That is pretty strange. It implies that much of the time:

The dictionary is large, or expensive to construct
It is mostly 100% unused, not evaluated at all.

It would be very helpful to have more insight into what is going on, in case there really is a bug of some kind. If the increase is "enormous" it can't be hard to find!

What happens with -XDictStrict?

If the dictionary is 100% unused, I wonder if it'd be helpful to inline or specialise the "outer shell" of the function, to inline the path that discards the dictionary -- if it is indeed in the outer shell.

The dictionaries being created are very large indeed (at least the ones that drew our attention in the ticky profiles). I'll collect a bit more information and report back.

added info needed label

changed the description

mentioned in merge request !13556 (merged)

It would indeed be great to have this reproduced in a minimal example.

Perhaps it is something like this:

We have a dictionaries $dA :: C A and $dB :: C B of 100 fields for class C.
We have instance (C a, C b) => C (a, b) where ..., giving rise to a DFun $dfPairC da db = MkC (op1 ... da .. db) (op2 ... da ... db) ....
We need to call a function which needs C (A,B), which is constructed using $dfPairC $dA $dB. Note that this expression has quite a small closure, because there are only 2 free variables.
We speculate the call to $dfPairC. Result: A value MkC (op1 ... $dA ... $dB) (op2 .. $dA .. $dB) ... etc. This leads to 100 closures with 2 free variables each! Quite wasteful.

I think we could prevent such waste by doing a quick analysis of the DFun. Say, if there are more than 10 occurrences in distinct fields of one of the parameters, don't speculate.

But adding a flag as in !13556 (merged) is a simple solution as well.

I've experimented a bit with a size cutoff for the dictionary size vs the number of free vars in the closure, but the results weren't conclusive for our testcase (perhaps I made some mistake). Unfortunately our test code is rather complicated and a rest run takes 45 minutes.

I think it would be useful to have the flags "just in case", to be able to measure/mitigate the effect of the optimisation. My main concern is that the -fcoreprep-spec-eval-dictfun might be superseded by a numerical flag that controls some growth factor.

I marked the !13556 (merged) MR as draft since I'd like to also implement a numerical cutoff for speculating dfuns and get some feedback on that approach.

Here's testcase that's hopefully a somewhat faithful representation of what happens in our codebase.

Normally GHC tries very hard to partially apply polymorphic functions to the typeclass args so it doesn't have to recompute dictionaries. But if that fails (because of a higher ranked type in the test), speculative evaluation can be costly if the dictionary goes unused.

output:

...
456
8
123
8
A (spec) allocated: 32007104
456
8
123
8
B (no spec) allocated: 19207408

A allocates a lot more because it always creates the HasConst10 dictionary because of speculative evaluation.

Cls.hs

{-# LANGUAGE UndecidableInstances #-}

module Cls where

class HasConst a where constVal :: a

instance Cls.HasConst Word where constVal = 123

instance Cls.HasConst Int where constVal = 456

-- this class has a big dictionary
class HasConst10 a where
  constA :: a
  constInt1 :: a -> Int
  constInt1 _ = 1
  constInt2 :: a -> Int
  constInt2 _ = 2
  constInt3 :: a -> Int
  constInt3 _ = 3
  constInt4 :: a -> Int
  constInt4 _ = 4
  constInt5 :: a -> Int
  constInt5 _ = 5
  constInt6 :: a -> Int
  constInt6 _ = 6
  constInt7 :: a -> Int
  constInt7 _ = 7
  constInt8 :: a -> Int
  constInt8 _ = 8
  constInt9 :: a -> Int
  constInt9 _ = 9

instance HasConst a => HasConst10 a where 
    constA = constVal

-- this doesn't use the big dictionary most of the time
printConst :: forall a. (Show a, HasConst10 a)
           => a -> Int -> IO ()
printConst x 5000  = print @a constA >> print (constInt8 x)
printConst _  _    = pure ()

A.hs

{-# OPTIONS_GHC -fspec-eval #-}
module A (testX) where

import qualified Cls

-- this creates the big dictionary strictly because of speculative evaluation
testX :: (Show a, Cls.HasConst a) => a -> Int -> IO ()
testX a b = Cls.printConst a b

B.hs

{-# OPTIONS_GHC -fno-spec-eval #-}
module B (testX) where

import qualified Cls

-- this creates the big dictionary lazily
testX :: (Show a, Cls.HasConst a) => a -> Int -> IO ()
testX a b = Cls.printConst a b

Main.hs

module Main where

import qualified A
import qualified B
import qualified Cls

import Data.Word
import System.Mem (performGC)
import GHC.Stats
import Control.Monad

{-# NOINLINE getAllocated #-}
getAllocated :: IO Word64
getAllocated = do
  performGC
  allocated_bytes <$> getRTSStats

withAllocated :: String -> IO a -> IO a
withAllocated name x = do
  alloc0 <- getAllocated 
  result <- x
  alloc1 <- getAllocated
  putStrLn $ name ++ " allocated: " ++ show (alloc1 - alloc0)
  pure result

main :: IO ()
main = replicateM_ 2 $ do  
    testMain A.testX "A (spec)"
    testMain B.testX "B (no spec)"

iter :: (Int -> IO ()) -> Int -> Int -> IO ()
iter m !i !j
  | i < j = m i >> iter m (i+1) j
  | otherwise = pure () 

{-# NOINLINE testMain #-}
testMain :: (forall b. (Show b, Cls.HasConst b) => b -> Int -> IO ())
         -> String
         -> IO ()
testMain f name = do
  alloc0 <- getAllocated 
  iter (\i -> f (0::Int) i >> f (0::Word) i) 1 100000
  alloc1 <- getAllocated
  putStrLn $ name ++ " allocated: " ++ show (alloc1 - alloc0)

changed the description

I think your question is this.

You have a local let-binding
```
 d = $df d1 d2 d3
```
where d, d1, d2, d3 are dictionaries and $df is a dictionary function arising from an instance decl.
You have -XStrictDicts switched off, otherwise you'd compute d regardless.
But speculative evaluation evaluates d strictly anyway, on the grounds that doing so is cheap.
In your case, however, speculative evaluation is not cheap, because
- d has many, many components
- d turns out not to be used; it is seldom evaluated

How much can $df d1 d2 d3 allocate? It'll allocate

A tuple for the dictionary itself
A closure for each component of the dictionary, capturing none, some, or all of d1, d2, d3.
And similarly for each of the dicionary's superclass dictionaries.

In your particular case the $df is

  $df :: forall a. HasConst a => HasConst10 a

This function builds a 10-tuple. All its fields are constants except one, which is gotten from HasConst.

In allocation terms, a dictionary will almost always be bigger than a thunk, because each component of the dictionary will likely capture some or all of the free variables of the thunk. So maybe we should switch off speculative evaluation of dictionaries altogether? What is the perf hit of that?

I suppose we could get some measure of the size of a dictionary by looking at how many fields it has. Something like

dictSize :: PredType -> Int
dictSize pred = length (classOpItems cls) + sum (map dictSize (classSCTheta cls))
  where
   (cls,_) = getClassPredTys pred

This isn't quite good enough because of recursive superclasses; you need to bale out if you see the same class again. But it'd be a start.

mentioned in commit b17fc06a

mentioned in commit 23099752

mentioned in merge request !13812 (closed)

mentioned in commit 96a4d0e2

mentioned in commit 810bb351

mentioned in commit ab3ab3e3

Speculative evaluation can cause a large increase in allocations

Child items ...

Activity