Changes between Initial Version and Version 1 of Commentary/Rts/Storage/Slop

Oct 20, 2006 9:07:21 AM (13 years ago)



  • Commentary/Rts/Storage/Slop

    v1 v1  
     3= Slop =
     5Slop is unused memory between objects in the heap.
     7|| Object1 || ... Slop ... || Object2 ||
     9== Why do we want to avoid slop? ==
     11Slop makes it difficult to traverse an area of memory linearly, visiting all the objects, because we can't tell where `Object2` starts in the above diagram.  We need to do linear traversals for two reasons, currently:
     13 * [wiki:Commentary/Profiling/Heap Heap profiling] needs to perform a census on the whole heap.
     14 * [wiki:Commentary/Rts/Sanity Sanity checking] needs to ensure that all the pointers in the heap
     15   point to valid objects.
     17Additionally, linear traversals are useful for the mark phase of the [wiki:Commentary/Rts/Storage compacting garbage collector], and would be useful if we were to allow objects to be pinned arbitrarily (currently pinned objects cannot contain pointers, which means they don't need to be scavenged by the GC).
     19== How does slop arise? ==
     21Slop can arise for two reasons:
     23 * The compiled code allocates too much memory, and only fills part of it with objects.  For example,
     24   when compiling code for a function like this:
     26f = \x -> case x of
     27            True  -> e1
     28            False -> e2
     30   the code generator takes the maximum of the heap requirements of e1 and e2 and aggregates it into
     31   the heap check at the beginning of the function `f` (to avoid doing too many heap checks). 
     32   Unfortunately that means either `e1` or `e2` has too much heap allocated to it, leaving some slop.
     33   We solve this problem by moving the heap pointer ''backwards'' before making a tail-call if
     34   there is any heap slop.
     36 * When an object is overwritten with a smaller object.  This happens in two ways:
     37   [wiki:Commentary/Rts/Updates Updates] and [wiki:Commentary/Rts/BlackHoles Black Holes].
     39== What do we do about it? ==
     41We avoid the problem for [wiki:Commentary/Profiling/Heap heap profiling] by arranging that we only ever do a census on a newly garbage-collected heap, which has no slop in it (the garbage collector never leaves slop between objects in the heap).
     43Slop does arise due to updates and black holes during normal execution, and GHC does not attempt to avoid it (because avoiding or filling slop during an update is costly).  However, if we're doing [wiki:Commentary/Rts/Sanity sanity checking], then we need to arrange that slop is clearly marked: so in a `DEBUG` version of the RTS (see [wiki:Commentary/Rts/Config RTS configurations])  the update code and the blackhole code both arrange to fill slop with zeros: see the `FILL_SLOP` macro in [[GhcFile(rts/Updates.h)]].  Hence sanity checking only works with a `DEBUG` version of the RTS.