Strictness signature blowup

The following code takes a lot of memory (556MB) to compile:

data A = A A A A A A deriving (Eq)

More As result in more memory consumption during compilation. Using ghc -O A.hs -v -dverbose-core2core -c -ddump-simpl +RTS -s it seems like the strictness signatures of (==) and (/=) blow up quite a bit.

A less silly example could be the following:

data QuadTree a = QuadTree !Int [a] (QuadTree a) (QuadTree a) (QuadTree a) (QuadTree a)

foldQuadTree :: (a -> b -> b) -> Int -> b -> QuadTree a -> b
foldQuadTree f maxSize = go
    where
        go z (QuadTree size elems t1 t2 t3 t4)
            | size <= maxSize = foldr f z elems
            | otherwise       = go (go (go (go z t4) t3) t2) t1

Trac metadata

Trac field	Value
Version	7.10.3
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

changed weight to 5

added Tbug Trac import labels

Attached file A.log.gz (download).

Output when compiling (22MB when uncompressed!)

So every QuadTree is infinite? As is every value of type A.

But yes, it'd be much better not to blow up.

This is because of demand analysis -- the usage part of the demand signature of (/=) isn't reaching to a fixpoint, so it's looping 10 times (because that's the hard-coded upper bound for fixpoint iterations), each time generating a bigger usage type.

I'm a bit confused about why this is happening though. First, strictness type is reaching to a fixpoint very fast (maybe in the first iteration), but why? Second, (/=) is actually defined as not (a == b), and (==) is demand type is top (i.e. (Lazy, Used)). This looks wrong to me, because the definition has case expressions on arguments and recursively calls itself. The strictness part should be more precise than that..

(more on this later...)

(oh.. I just realized the bug title already says that this is due to demand type explosion... late night debugging)

added compiler perf label

added Pnormal label

Closing as fixed.

closed

Matthew do we have a regression test? Could we, pls?

reopened

mentioned in commit 4a87bb60

mentioned in merge request !5433 (closed)

@simonpj I added a test and turns out I tested with an older version of the compiler (8.8.3) by accident. It has regressed in HEAD. Good job I added the test!

cc @sgraf812 ?

Test in !5433 (closed)

No idea yet why it regresses. We don't hit the 10 iterations limit anymore, though. Maybe it's that trimming by type shape is expensive for big tuples?

Note that not the QuadTree code is what regresses, it's the Eq instance for A. You don't really notice a huge blowup anymore for

data B = B B B B B B deriving (Eq)

which finishes in 1ms. But it is clearly scaling badly, because Matt's test case

data A = A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A deriving (Eq)

with ~30ish fields takes 1.2s and 800MB or allocs in the first DmdAnal run.

Here's are a few data points, relating the number of fields to allocations:

24	25	26	27	28	29	30	31	32	33	50
272	318	369	427	491	641	723	823	927	1040	4685

That's approx. quadratic: https://www.desmos.com/calculator/wnbrx94msv

Here's the succession of signatures for (==) and 3 fields:

0. b, which is just like <B><B>b
1. <1B><1B>b
2. <1P(1B,1B,1B)><1P(1B,1B,1B)>b
3. <1P(1P(1B,1B,1B),1P(1B,1B,1B),1P(1B,1B,1B))><1P(1P(1B,1B,1B),1P(1B,1B,1B),1P(1B,1B,1B))>b
4. <1P(1P(1L,1L,1L),1P(1L,1L,1L),1P(1L,1L,1L))><1P(1P(1L,1L,1L),1P(1L,1L,1L),1P(1L,1L,1L))>b

The two levels of nesting lead to n^2 many field demands. Ultimately, I think the signature could just be b, e.g. what we started with. Edit: Although that would make the parameters absent and maybe not what we want. So (4) is actually the first sound signature. on the other hand, (==) will never terminate, so we might just as well segfault? Hmm. Better not do that, I suppose.

By contrast, we appear to give == a sig of <L,U><L,U> in 8.10, e.g. top. I think that's only possible by passing the 10 iteration limit and abort. We do less iterations today (probably as a result of the type shape stuff), but each iteration seems to have become more costly, possibly due to the type shape checks?.

Not sure what we can do. Note that this test really needs a huge amount of recursive fields for the regression to show up.

Provided we stop reasonably promptly (as we do), I don't think we should worry too much about a corner case like this.

But it is puzzling that four iterations costs more than ten, when ten involves and exponentially larger demand signature. Very strange indeed. Is that worth investigating? Perhaps we are doing something stupid...

mentioned in commit 12ef24ee

mentioned in commit b726b6a6

mentioned in commit 4b205fb0

mentioned in commit 83654240