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
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.