Unnecessary dictionaries

[guest]

The attached program (unzip, untar, read Main.hs) contains dictionary building and taking apart despite all types being known. To find the dictionary search for dMonad inside QS.qsort. I've tried putting INLINE on everything I can think of, but even so there is a constant dictionary being used in a pattern match. And then the method calls are slow and non-inlined, of course.

[chevalier@…]

If you look at the Core, you can see that the definition of the $dMonad inside qsort looks like this:

$dMonad_s5Hx :: forall s_a5pv.
		GHC.Base.Monad (CTBase.E' CTBase.RValue (GHC.ST.ST s_a5pv))
[]
$dMonad_s5Hx =
  \ (@ s_a5pv) ->
    case CT.$wic
	   @ (GHC.ST.ST s_a5pv)
	   @ (GHC.STRef.STRef s_a5pv)
	   @ GHC.Base.Int
	   (MonadRef.$f1 @ s_a5pv)
    of ww_s3pb [Dead Nothing] { (# ww1_s3pd, ww2_s3pe, ww3_s3pf, ww4_s3pg #) ->
    GHC.Base.:DMonad
      @ (CTBase.E' CTBase.RValue (GHC.ST.ST s_a5pv))
      ww1_s3pd
      ww2_s3pe
      ww3_s3pf
      ww4_s3pg
    }

Because the rhs of $dMonad_s5Hx isn't cheap, it doesn't get inlined inside a lambda (e.g., in the body of qsort. If the call to CT.$wic inside $dMonad_s5Hx were inlined, then $dMonad_s5Hx would be inlined as well. But by default, GHC thinks CT.$wic is too big to inline. If you pass in the flag -funfolding-use-threshold36 to increase the threshold for the allowable size of an unfolding, then you get the results you want, but I haven't measured whether that actually increases performance here.

-Tim

[guest]

Tim, thanks for the analysis!

But dictionaries are special, you always know that they will contain a tuple (and if they take arguments the computation is terminating). So they should be treated specially (even hbc did that). When the compiler sees a known dictionary it should never be scrutinized; the methods should be accessed directly.

If this is too complicated to implement special dictionary treatment in ghc, then it would be nice to have an INLINE pragma for the instance itself, since it's sometimes crucial that it gets inlined. And mucking around special compiler flags is a bit scary. :)

[guest]

BTW, I tried the -funfolding-use-threshold36 and saw a 5-fold speedup.

[duncan]

The ghc flag -fdicts-cheap (and possibly -fno-method-sharing) may also be relevant here.

[chevalier@…]

-fdicts-cheap does the trick as well. I notice there's a comment on line 1045 of coreSyn/CoreUtils.lhs that says:

" -- One could go further and make exprIsCheap reply True to any

-- dictionary-typed expression, but that's more work."

[simonpj]

Ah I see -- it's to do with (the new) implication constraints. I'm snowed this week, but I'll look at it after that.

Simon

[simonpj]

Reminder to self: ~/tmp/lennart-1643. The problem is that the dict-fun generated from the instance decl is marked INLINE; but an implication constraint is floated out from it, and that is not marked INLINE. It's only mentioned once, but we don't inline inside INLINE things.

The right thing is to mark all implication constraint as INLINE.

Simon

[igloo]

Depending on how invasive the fix is, this might not be suitable for the 6.8 branch, but I'll put it there for now anyway.

[simonpj]

I've finally gotten around to fixing this. (Wasn't hard in the end.)

Ian: the patch should merge onto the branch fine if you feel like doing so:

Mon Nov  5 22:08:07 GMT Standard Time 2007  simonpj@microsoft.com
  * Inline implication constraints
Mon Nov  5 22:06:27 GMT Standard Time 2007  simonpj@microsoft.com
  * Wibble to earlier case-merge fix

Lennart: can you confirm fix?

Simon

[guest]

It looks good now in my code.

[simonpj]

Closing this since Lennart is happy now.

Simon