Quadratic behaviour in the compacting GC

Run the following program under GHCi with +RTS -c -RTS:

module Main where

break2 p (x:xs) = if p x then 
                    ([],x:xs)
                  else
                    let (b1,b2) = break2 p xs
                    in  (x : b1, b2)
break2 p []     = ([],[])

surprise xs = b1 ++ "\n surprise " ++ b2
               where
               (b1,b2) = break2 (=='\n') xs

test n = length $ surprise $ [head (show i) | i <-[1..n] ] ++ "\n the end"

main = print $ test 1000000

Notice how it hangs.

This is because of the call to get_threaded_info() in thread_PAP_payload() in the compacting GC. We have a lot of APs pointing to the same BCO, so the thread gets really long, and needs to be unravelled for every AP. One partial fix would be to cache the fun's info table in the spare field of an AP during the mark phase; this fixes the problem for APs, but not for PAPs (which don't have a spare field).

Related to this is the get_threaded_info() call in update_fwd_compact(), which is inefficient, but not quadratic. It would be nice to fix this too.

Trac metadata

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