Opened 4 years ago

Last modified 3 years ago

#11545 new bug

Strictness signature blowup

Reported by: jscholl Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.10.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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

Attachments (1)

A.log.gz (125.3 KB) - added by jscholl 4 years ago.
Output when compiling (22MB when uncompressed!)

Download all attachments as: .zip

Change History (3)

Changed 4 years ago by jscholl

Attachment: A.log.gz added

Output when compiling (22MB when uncompressed!)

comment:1 Changed 4 years ago by simonpj

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

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

comment:2 Changed 3 years ago by osa1

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)

Last edited 3 years ago by osa1 (previous) (diff)
Note: See TracTickets for help on using tickets.