Changes between Version 8 and Version 9 of GarbageCollectorNotes


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

--

Legend:

Unmodified
Added
Removed
Modified
  • GarbageCollectorNotes

    v8 v9  
    144144== Copy == 
    145145 
    146 = Motivation for Parallelization =  
    147  
    148 The essential idea is best described here: 
    149 [refer to the flood paper] 
    150  
    151 It 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  
    153 For 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  
    155 == Measurement of Block Distance while Scavenging == 
    156  
    157 Here 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  
    159 The 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  
    161 The 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 {{{ 
    164 import System 
    165  
    166 treeDepth = 17 
    167 nTrees = 40 
    168  
    169 makeList 0 d = [] 
    170 makeList n d = d : (makeList (n-1) d) 
    171  
    172 main :: IO () 
    173 main = if (recVal (makeList nTrees treeDepth)) < 10 
    174        then print "###" 
    175        else print "##" 
    176  
    177  
    178 data Tree a = L a 
    179             | B (Tree a) (Tree a) 
    180  
    181 makeTree 0 = L 1 
    182 makeTree n = B (makeTree (n-1)) (makeTree (n-1)) 
    183  
    184 sumTree (L x) = x 
    185 sumTree (B t1 t2) = 1 + (sumTree t1) + (sumTree t2) 
    186  
    187 treeVal n rest = let tr1 = makeTree n in 
    188                      sumTree(tr1) + sumTree(makeTree n) + (recVal rest) + sumTree(tr1) 
    189  
    190 recVal [] = 0 
    191 recVal (x:xs) = treeVal x xs 
    192 }}} 
    193  
    194 Here are some plots: 
    195  
    196 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g0-time-block_dist.png 
    197  
    198 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g0-time-avg_block_dist.png 
    199  
    200 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g0-time-live_objs.png 
    201  
    202 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g1-time-block_dist.png 
    203  
    204 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g1-time-avg_block_dist.png 
    205  
    206 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-memtest-g1-time-live_objs.png 
    207  
    208  
    209 Here 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  
    211 The 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  
    213 Here are similar plots of some programs in the nofib test suite that is available in the GHC source tree.  
    214  
    215 Plots of real/fulsom (with input 8) 
    216  
    217 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g0-time-block_dist.png 
    218  
    219 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g0-time-avg_block_dist.png 
    220  
    221 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g0-time-live_objs.png 
    222  
    223 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g1-time-block_dist.png 
    224  
    225 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g1-time-avg_block_dist.png 
    226  
    227 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fulsom-g1-time-live_objs.png 
    228  
    229 Plots of real/pic (with input 20000) 
    230  
    231 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g0-time-block_dist.png 
    232  
    233 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g0-time-avg_block_dist.png 
    234  
    235 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g0-time-live_objs.png 
    236  
    237 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g1-time-block_dist.png 
    238  
    239 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g1-time-avg_block_dist.png 
    240  
    241 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-pic-g1-time-live_objs.png 
    242  
    243 Plots of real/fem (with fem.stdin) 
    244  
    245 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fem-g0-time-block_dist.png 
    246  
    247 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fem-g0-time-avg_block_dist.png 
    248  
    249 http://www.cs.indiana.edu/~rpjames/HaskellGC/plot-fem-g0-time-live_objs.png 
    250  
    251 fem did not do any G1 collections. 
     146= MotivationForParallelization =  
    252147 
    253148