Changes between Version 2 and Version 3 of Commentary/Rts/Storage/GC


Ignore:
Timestamp:
Dec 4, 2009 12:32:47 PM (4 years ago)
Author:
simonmar
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Rts/Storage/GC

    v2 v3  
    22 
    33= The Garbage Collector = 
     4 
     5GC concepts: 
     6 
     7 * [wiki:Commentary/Rts/Storage/GC/Aging Aging] 
     8 * [wiki:Commentary/Rts/Storage/GC/Pinneed Pinned objects] 
     9 
     10GC algorithms supported: 
    411 
    512 * [wiki:Commentary/Rts/Storage/GC/Copying Copying GC] 
     
    1320The GC is designed to be flexible, supporting lots of ways to tune its behaviour.  Here's an overview of the techniques we use: 
    1421 
    15  * Generational GC, with a runtime-selectable number of generations (`+RTS -G<n> -RTS`, where `n >= 1`) 
     22 * Generational GC, with a runtime-selectable number of generations (`+RTS -G<n> -RTS`, where `n >= 1`).  Currently it is a 
     23   traditional generational collector where each collection collects a particular generation and all younger generations. 
     24   Generalizing this such that any subset of generations can be collected is a possible future extension. 
    1625 
    1726 * The heap grows on demand.  This is straightforwardly implemented by basing the whole storage manager on a [wiki:Commentary/Rts/Storage/BlockAlloc block allocator]. 
    1827 
    19  * Aging: objects can be aged within a generation, to avoid premature promotion.  In GHC 6.12 and earlier this was implemented by having each generation consist of a runtime-tunable number of ''steps'', so objects would be moved through the list of steps before being promoted to the next highest generation.  We found that having 2 steps was almost always the best ''integral'' number of steps, but GHC 6.12 did not support a fractional number of steps.  In GHC 6.13 and later, the concept of steps was removed.  Aging is still supported, by having each block point to the generation to which objects in that block should be promoted; this lets us provide any fractional number of steps between 1 and 2, while eliminating the infrastructural overhead of steps. 
     28 * Aging: objects can be aged within a generation, to avoid premature promotion.  See [wiki:Commentary/Rts/Storage/GC/Aging].  In GHC 6.12 and earlier this was implemented by having each generation consist of a runtime-tunable number of ''steps'', so objects would be moved through the list of steps before being promoted to the next highest generation.  We found that having 2 steps was almost always the best ''integral'' number of steps, but GHC 6.12 did not support a fractional number of steps.  In GHC 6.13 and later, the concept of steps was removed.  Aging is still supported, by having each block point to the generation to which objects in that block should be promoted; this lets us provide any fractional number of steps between 1 and 2, while eliminating the infrastructural overhead of steps. 
    2029 
    2130 * The heap collection policy is runtime-tunable.  You select how large a generation gets before it is collected using the `+RTS -F<n> -RTS` option, where `<n>` is a factor of the generation's size the last time it was collected.  The default value is 2, that is a generation is allowed to double in size before being collected. 
    2231 
    2332== GC data structures == 
     33 
     34[[GhcFile(includes/rts/storage/GC.h)]] 
     35 
     36=== generation === 
     37 
     38The main data structure is `generation`, which contains: 
     39 
     40 `blocks`:: 
     41   a pointer to a list of blocks 
     42 
     43 `large_objects`:: 
     44   a pointer to a list of blocks containing large objects 
     45 
     46 `threads`:: 
     47   a list of threads in this generation 
     48 
     49 `mut_list`:: 
     50   the "remembered set", a list of blocks containing pointers to objects in ''this'' generation that point to objects in ''younger'' generations 
     51 
     52and various other administrative fields (see [[GhcFile(includes/rts/storage/GC.h)]] for the details). 
     53 
     54Generations are kept in the array `generations[]`, indexed by the generation number. 
     55 
     56=== nursery === 
     57 
     58A `nursery` is a list of blocks into which the mutator allocates new (small) objects.  For resaons of locality, we want to re-use the list of blocks for the nursery after each GC, so we keep the nursery blocks rather than freeing and re-allocating a new nursery after GC. 
     59 
     60The struct `nursery` contains only two fields 
     61 
     62 `blocks`:: 
     63   the list of blocks in this nursery 
     64 `n_blocks`:: 
     65   the number of blocks in the above list 
     66 
     67In the threaded RTS, there is one nursery per Capability, as each Capability allocates independently into its own allocation area.  Nurseries are therefore stored in an array `nurseries[]`, indexed by Capability number. 
     68 
     69The blocks of the nursery notionally logically to generation 0, although they are not kept on the list `generations[0].blocks`.  The reason is that we want to keep the actual nursery blocks separate from any blocks containing live data in generation 0.  Generation 0 may contain live data for two reasons: 
     70 
     71 * objects live in the nursery are not promoted to generation 1 immediately, instead they are [wiki:Commentary/Rts/Storage/GC/Aging aged], first being copied to generation 0, and then being promoted to generation 1 in the next GC cycle if they are still alive. 
     72 
     73 * If there is only one generation (generation 0), then live objects in generation 0 are retained in generation 0 after a GC. 
     74