Context reduction stack overflow can take very long

[dreixel]

The following code, taken from the "Haskell Type Constraints Unleashed" paper:

{-# LANGUAGE TypeFamilies #-}

type family TF a :: *
type instance TF (a,b) = (TF a, TF b)

t :: (a ~ TF (a,Int)) => Int
t = undefined

fails almost immediately with Context reduction stack overflow on GHC 7.2, but seems to loop forever with 7.4.1-rc2. Setting -fcontext-stack to 20 results in near immediate termination with the same error. But #5395 raised the context stack size default to 200, which makes this code (that does not use -XUndecidableInstances) take "forever" to compile.

[simonpj]

OK so the underlying problem is #4296, which we do not know how to solve. But we hope that we will fairly quickly get some kind of context-stack overflow, and you say we aren't. Worth looking into, thanks.

[dimitris]

In the ghc-new-flavor branch (which I have not yet merged to master) I get this program complaining in ~ 2 seconds using the default 200 context stack. Is this a better behavior? There is still something super-linear as the context stack increases but that's because there are many bi-products (all intermediate family applications are named by flatten skolems, this can't be helped), but I am wondering if this is better than the comment "takes `forever' to compile" you wrote above?

[dreixel]

2s is certainly much better than "forever"! :-)

[simonpj]

OK, yes, this is much better. With HEAD:

simonpj@cam-05-unx:~/tmp$ ~/5builds/HEAD/inplace/bin/ghc-stage1 -c -ddump-cs-trace -fcontext-stack=5 T5837.hs
1>[0] Top react: Fun/Top (given)
2>[0] Top react: Fun/Top (given)
3>[1] Top react: Fun/Top (given)
4>[0] Top react: Fun/Top (given)
5>[1] Top react: Fun/Top (given)
6>[2] Top react: Fun/Top (given)
7>[0] Top react: Fun/Top (given)
8>[1] Top react: Fun/Top (given)
9>[2] Top react: Fun/Top (given)
10>[3] Top react: Fun/Top (given)
11>[0] Top react: Fun/Top (given)
12>[1] Top react: Fun/Top (given)
13>[2] Top react: Fun/Top (given)
14>[3] Top react: Fun/Top (given)
15>[4] Top react: Fun/Top (given)
16>[0] Top react: Fun/Top (given)
17>[1] Top react: Fun/Top (given)
18>[2] Top react: Fun/Top (given)
19>[3] Top react: Fun/Top (given)
20>[4] Top react: Fun/Top (given)
21>[5] Top react: Fun/Top (given)

T5837.hs:8:6:
    Context reduction stack overflow; size = 6
    Use -fcontext-stack=N to increase stack size to N
      cobox :: TF (TF (TF (TF (TF a))))
               ~ (TF (TF (TF (TF (TF (TF a))))), TF (TF (TF (TF (TF (TF Int))))))

Notice that the context stack is set to 5, but the trace goes

  0
  0, 1
  0, 1, 2
  0, 1, 2, 3
  0, 1, 2, 3, 4 
  etc

This quadratic behaviour is bad with a depth of 200!

But with the new ghc-new-flavor branch we see

simonpj@cam-05-unx:~/tmp$  ~/5builds/ghc-solver/inplace/bin/ghc-stage1 -c -ddump-cs-trace -fcontext-stack=5 T5837.hs
1>[0] Top react: Fun/Top
2>[1] Top react: Fun/Top
3>[2] Top react: Fun/Top
4>[3] Top react: Fun/Top
5>[4] Top react: Fun/Top
6>[5] Top react: Fun/Top

T5837.hs:8:6:
    Context reduction stack overflow; size = 6
    Use -fcontext-stack=N to increase stack size to N
      (TF (TF (TF (TF (TF (TF a))))), TF (TF (TF (TF (TF (TF Int))))))
      ~ TF (TF (TF (TF (TF a))))

Which is fine.

But there is still something wrong! If you try the above you'll see the output coming out fairly slowly. And indeed adding +RTS -s and trying with different context stack sizes gives

   -fcontext-stack=N      Bytes allocated
        100                  366M
        200                1,700M 
        300                5,041M

Badly non-linear. This is with a standard stage2 build, so no DEBUG flags on.

[dimitris]

I've improved things even more. I now get:

  100           87MB
  200          212MB
  300          394MB

Super-linear but not way-off. I will push to HEAD shortly and add this file.

[simonpj]

Performance regression test added.