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 |