Changes between Version 4 and Version 5 of GarbageCollectorNotes


Ignore:
Timestamp:
May 15, 2006 5:58:10 PM (9 years ago)
Author:
guest
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • GarbageCollectorNotes

    v4 v5  
    144144== Copy == 
    145145 
     146= Motivation for Parallelization =  
     147 
     148The essential idea is best described here: 
     149[refer to the flood paper] 
     150 
     151It is helpful to be aware of copy collection and mark-compact collection before you read the above paper. The Richard Jones and Raphael Lins text on Garbage Collection is a recommended resource.  
     152 
     153For our garbage collector, we are yet to work out the details of how Gen0 should be compacted. The best idea for later generations is some variant of the work stealing approach proposed in the above paper. This of course might change in the course of the project.  
     154 
    146155== Measurement of Block Distance while Scavenging == 
     156 
     157Here are some plots of block distance against the collection number and the average block distance and the collection number. Block distance is defined to be the number of links one has to follow from the scan_bd to reach the hp_bd in a step during garbage collection. If the block distance in 2 then it means that there is atleast one independent block in between the pointers that can be taken up by another thread. 
     158 
     159The essential idea behind work stealing is that free threads can steal work from busy threads. The work is essentially the work of scavenging live objects. hp_bd points to the top of the to-space where the next free object can go. scan_bd points to the block where the next object to be scanned is. All objects between scan_bd and hp_bd  are objects that are yet to be scanned. A free thread essentially steal a block of objects in this range and can scan them, essentially reducing the load of the busy thread.  
     160 
     161The following program was used to generate some the graphs below. Changing the treeDepth and the nTrees values below one can get the program to have different memory profiles.  
     162 
     163{{{ 
     164import System 
     165 
     166treeDepth = 17 
     167nTrees = 40 
     168 
     169makeList 0 d = [] 
     170makeList n d = d : (makeList (n-1) d) 
     171 
     172main :: IO () 
     173main = if (recVal (makeList nTrees treeDepth)) < 10 
     174       then print "###" 
     175       else print "##" 
     176 
     177 
     178data Tree a = L a 
     179            | B (Tree a) (Tree a) 
     180 
     181makeTree 0 = L 1 
     182makeTree n = B (makeTree (n-1)) (makeTree (n-1)) 
     183 
     184sumTree (L x) = x 
     185sumTree (B t1 t2) = 1 + (sumTree t1) + (sumTree t2) 
     186 
     187treeVal n rest = let tr1 = makeTree n in 
     188                     sumTree(tr1) + sumTree(makeTree n) + (recVal rest) + sumTree(tr1) 
     189 
     190recVal [] = 0 
     191recVal (x:xs) = treeVal x xs 
     192}}} 
     193 
     194Here are some plots: 
     195 
     196http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g0-#-block_dist.png 
     197 
     198http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g0-#-avg_block_dist.png 
     199 
     200http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g0-#-live_objs.png 
     201 
     202http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g1-#-block_dist.png 
     203 
     204http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g1-#-avg_block_dist.png 
     205 
     206http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g1-#-live_objs.png 
     207 
     208 
     209Here is how to interpret the graphs. The label ‘#’ on an axis indicates that it is time where each tick is a garbage collection. The label ‘live_objs’ indicates the total number of live objects encountered during this collection. This is not the total number of live objects in the system but only those in the generations currently collected. The value ‘block_dist’ indicates the maximum block distance encountered during a collection.  
     210 
     211The value `avg_block_dist’ indicates the average block distance encountered during a collection. If you think about the block distance a bit you realize that it essentially starts from zero increases and decreases during the duration of scavenging and finally becomes zero when the scan point catches up with the heap pointer. We wanted to measure approximately the area under this region as a indication of the average chance of parallelization. Further to make the measurement a little less fine grained, it was taken only when a new block was allocated to the to-space. This value can be considered indicative of how much parallelization is possible on average during that GC run. [At least I hope so] 
     212 
     213Here are similar plots of some programs in the nofib test suite that is available in the GHC source tree.  
     214 
     215Plots of real/fulsom (with input 8) 
     216 
     217http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g0-#-block_dist.png 
     218 
     219http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g0-#-avg_block_dist.png 
     220 
     221http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g0-#-live_objs.png 
     222 
     223http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g1-#-block_dist.png 
     224 
     225http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g1-#-avg_block_dist.png 
     226 
     227http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g1-#-live_objs.png 
     228 
     229Plots of real/pic (with input 20000) 
     230 
     231http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g0-#-block_dist.png 
     232 
     233http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g0-#-avg_block_dist.png 
     234 
     235http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g0-#-live_objs.png 
     236 
     237http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g1-#-block_dist.png 
     238 
     239http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g1-#-avg_block_dist.png 
     240 
     241http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g1-#-live_objs.png 
     242 
     243Plots of real/fem (with fem.stdin) 
     244 
     245http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fem-g0-#-block_dist.png 
     246 
     247http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fem-g0-#-avg_block_dist.png 
     248 
     249http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fem-g0-#-live_objs.png 
     250 
     251fem did not do an G1 collections. 
    147252 
    148253 
     
    179284This behavior would often end with power cycling the laptop and was rather frustrating for a while. After studying the process with procexp, filemon and some standard monitoring tools it seemed like the “Logitech LVPrcSrv module” related to my Logitech webcam seems to hog the CPU. Since I wasn’t using the webcam, I killed the process and the build went through fine. At this point I can’t guess at what the relationship is or why there should be one.  
    180285 
    181  
    182286---- 
    183287Roshan James (rpjames [at] cs [dot] indiana [dot] edu) 
    184288 
    185  
    186  
    187  
    188