Opened 13 years ago

Last modified 7 years ago

#1147 new bug

Quadratic behaviour in the compacting GC

Reported by: simonmar Owned by:
Priority: normal Milestone:
Component: Runtime System Version: 6.6
Keywords: ghci compacting Cc: SamB
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Change History (9)

comment:1 Changed 11 years ago by SamB

Cc: SamB added
Keywords: ghci compacting added
Type: bugrun-time performance bug

comment:2 Changed 11 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:3 Changed 11 years ago by simonmar

Operating System: UnknownUnknown/Multiple

comment:4 Changed 10 years ago by simonmar

Type of failure: Runtime performance bug

comment:5 Changed 7 years ago by morabbin

Bump; still relevant?

comment:6 Changed 7 years ago by simonmar

Bug still exists. Would be nice to know if the program still demonstrates it though.

comment:7 Changed 7 years ago by morabbin

Running with +RTS -c -RTS does not hang (on x86_64 Mac, 8Gb RAM). Trying with larger test values.

comment:8 Changed 7 years ago by morabbin

Testing with 100x, no hang. Slower than the default, but no hang. Bug fixed accidentally?

comment:9 in reply to:  8 Changed 7 years ago by simonmar

Replying to morabbin:

Testing with 100x, no hang. Slower than the default, but no hang. Bug fixed accidentally?

No, bug is still there, but now we don't have a test case :(

Note: See TracTickets for help on using tickets.