#1147: Quadratic behaviour in the compacting GC
-------------------------------+--------------------------------------------
Reporter: simonmar | Owner:
Type: bug | Status: new
Priority: normal | Milestone: _|_
Component: Runtime System | Version: 6.6
Severity: normal | Keywords:
Difficulty: Unknown | Testcase:
Architecture: Unknown | Os: Unknown
-------------------------------+--------------------------------------------
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.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1147>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
