Changes between Version 13 and Version 14 of GarbageCollectorNotes

May 19, 2006 10:20:40 AM (11 years ago)



  • GarbageCollectorNotes

    v13 v14  
    5757Haskell threads are not time-sliced via a timer (potentially a time rinterrupt) the way OS threads are [cross check if there is some time sliced mechanism]. Instead they are interreupted by certain commonly occuring events. Due to the lazy nature of Haskell thunks need to be created and values need to be computed very often. Hence the execution of a thread entails lots of of memory allocation. One of the ways the execution of a thread is interrupted is when a thread has run out of space in its current block - it then returns control back to the scheduler.
     59I stand corrected about the above - ''We do have a time-slice mechanism: the timer interrupt (see Timer.c) sets the context_switch flag, which causes the running thread to return to the scheduler the next time a heap check fails (at the end of the current nursery block).
     61When a heap check fails, the thread doesn't necessarily always return to the scheduler: as long as the context_switch flag isn't set, and there is another block in the nursery, it resets Hp and HpLim to point to the new block, and continues.''
    5963A GHC block is a 4k page that is page aligned for the OS VM system. 
    137141=== Generations ===
     142The GHC GC is a generational collector. The number of generations is set to 2 by default and they are referred to as gen 0 and gen 1. gen 0 has never objects, objects that survive collections in gen 0 are promoted to gen 1. Older objects reside in gen 1.
     144==== Command Line Switches ====
     145The number of generations in an exceution of a compiled haskell program can be changed by by using the command line switch -G<n>, where n is the number of generations. This is an RTS switch and so has to be used as follows -
     148main.exe +RTS -G5 -RTS
     151Where main.exe is the compiled program and we want it to have 5 generations. More about the RTS switches can be found here
     152[ Runtime Control].
     154On the topic of command line switches, for a compiler hacker this is also interesting -
     155[ Debugging the compiler]
    139157=== Steps ===
     158GHC generations are divided into steps. The number of steps per generations is a configurable value as well. The last generation, the oldest one has only one step. By default GHC compiled programs have 2 steps per generation. Since GHC usually has only 2 generations, it has 2 steps in gen 0 and 1 step in gen 1. Steps of a generation are referred to by their index number starting from 0.
     160Garbage collection happens at the level of generations. So when you say that you are collecting gen 0, you are essentially collecting all the steps in gen 0. If you are collecting gen 4, then you are collecting all the steps in gen 0 to gen 4. Objects that survive a collection are promoted into the next higher step, or into the next higher generation if the onject is already in the highest step of its generation.
     162The reasoning behing having steps is approximately this - if there were no steps and a surviving a gen0 collection meant automativ promotion to gen1, then it means that at the time when gen0 happened several very new objects (which are potentially shortlived as well) get promoted to gen1. gen1 collections are expensive since higher generations are larger and hence these objects will reside in memory a long time before they get collected. On the other had if gen0 were divided into two steps then a gen0step0 object hops to gen0setp1 on its first survival and needs to survive yet another GC before it is promoted to gen1. [This I think is a very neat idea. My current understanding is that the .Net GC does have steps. Is this correct?]
     164That said, lets look at the data structures. This is what a generation looks like -
     166typedef struct generation_ {
     167  unsigned int   no;                    /* generation number */
     168  step *         steps;                 /* steps */
     169  unsigned int   n_steps;               /* number of steps */
     170  unsigned int   max_blocks;            /* max blocks in step 0 */
     171  bdescr        *mut_list;              /* mut objects in this gen (not G0)*/
     173  /* temporary use during GC: */
     174  bdescr        *saved_mut_list;
     176  /* stats information */
     177  unsigned int collections;
     178  unsigned int failed_promotions;
     179} generation;
     182This is what a step looks like -
     184typedef struct step_ {
     185  unsigned int         no;              /* step number */
     186  bdescr *             blocks;          /* blocks in this step */
     187  unsigned int         n_blocks;        /* number of blocks */
     188  struct step_ *       to;              /* destination step for live objects */
     189  struct generation_ * gen;             /* generation this step belongs to */
     190  unsigned int         gen_no;          /* generation number (cached) */
     191  bdescr *             large_objects;   /* large objects (doubly linked) */
     192  unsigned int         n_large_blocks;  /* no. of blocks used by large objs */
     193  int                  is_compacted;    /* compact this step? (old gen only) */
     195  /* During GC, if we are collecting this step, blocks and n_blocks
     196   * are copied into the following two fields.  After GC, these blocks
     197   * are freed. */
     198  bdescr *     old_blocks;              /* bdescr of first from-space block */
     199  unsigned int n_old_blocks;            /* number of blocks in from-space */
     201  /* temporary use during GC: */
     202  StgPtr       hp;                      /* next free locn in to-space */
     203  StgPtr       hpLim;                   /* end of current to-space block */
     204  bdescr *     hp_bd;                   /* bdescr of current to-space block */
     205  StgPtr       scavd_hp;                /* ... same as above, but already */
     206  StgPtr       scavd_hpLim;             /*     scavenged.  */
     207  bdescr *     scan_bd;                 /* block currently being scanned */
     208  StgPtr       scan;                    /* scan pointer in current block */
     209  bdescr *     new_large_objects;       /* large objects collected so far */
     210  bdescr *     scavenged_large_objects; /* live large objs after GC (d-link) */
     211  unsigned int n_scavenged_large_blocks;/* size of above */
     212  bdescr *     bitmap;                  /* bitmap for compacting collection */
     213} step;
     216These definitions maybe found in rts\storage.h.
    141220== Allocation ==