doc/internals-notes/non-moving-gc

   1 Non-moving GC
   2 =============
   3 For a few types of objects, evidence suggests that
   4 either they are almost immediately known to be long-lived (a PACKAGE, e.g.),
   5 of very fleeting in lifetime (gensyms during compilation, e.g).
   6 At least four types of objects share this aspect:
   7 - LAYOUT
   8 - FDEFN
   9 - PACKAGE
  10 - SYMBOL, but only certain symbols, those which appear
  11   (by their name) to be special variables
  12
  13 In addition, these objects seem to have in common the property that speed
  14 of allocation is relatively unimportant, and which therefore are indifferent
  15 to an allocator which is somewhat more expensive than a "pointer bump".
  16
  17 Taking each in turn:
  18 A LAYOUT is created when augmenting the type system (via DEFSTRUCT,DEFCLASS)
  19 which has so much overhead in and of itself, that speed of creation of
  20 the LAYOUT is insignificant.  We also expect changes to the type system
  21 to be few and far between (in comparison to operations on the objects of that
  22 type) such that reclamation of the metadata by GC is nearly irrelevant as
  23 to whether or when it happens.
  24
  25 An FDEFN is created for function linkage, which entails compilation,
  26 which entails tons of overhead. (While it's certainly possible to create
  27 FDEFNs outside of the compiler/loader, it would be unusual)
  28 Morever, it was not even possible to delete FDEFN objects prior to the
  29 rewrite of globaldb, which is to say, FDEFNs were *actually* immortal.
  30
  31 A PACKAGE is generally expected to be long-lived, and again speed of
  32 allocation is irrelevant.
  33
  34 And finally, interned symbol usually live as long as their package does.
  35
  36 For most of those objects, immobile placement does not seem to lead
  37 to too much heap fragmentation in the immobile space.
  38
  39 Prior to dumping a core image, we could allow motion on the otherwise
  40 non-moving heap to squash the waste out. But this renders infeasible
  41 the possibility of wiring in 32-bit immediate operands in assembly code
  42 unless all code-components store their fixups for later use.
  43 And indeed, assembly code makes frequent reference to SYMBOLs, FDEFNs,
  44 and LAYOUTs, so there is something to be said for wiring them in.
  45
  46 Card marking
  47 ============
  48 For FDEFNs and SYMBOLs, we can avoid OS-based write-protection while
  49 incurring less of a penalty than was suggested by Paul Khuong's sw-write-barrier
  50 branch. If symbols that "look like" special variables are immobile,
  51 then a card-marking scheme can be used with a cost of only 1 instruction
  52 for known symbols.
  53    LOCK BTS [someplace], N ; set the "card dirty" bit
  54    MOV [addr], val         ; write it
  55 Some fairly intricate cooperation with the fasloader will be required to
  56 compute the absolute address of the mark bit, but not much more tricky
  57 than the logic to assign symbol TLS indices at load time.
  58 [And this doesn't help any with (SET SYM VAL) or with (PROGV)]
  59
  60 We need two bits per card: one bit for whether the card is dirty,
  61 and one bit for whether the card was ever the target of a preserve_pointer()
  62 or the target of the effective address of a MOV instruction if that is
  63 where the stop-for-gc signal occurred.
  64 [This is the downside of not loading the symbol into a register]
  65 In the latter case we can't clear the dirty bit even if the card seems clean,
  66 because in the instruction sequence above, the second operation writes
  67 the card in a way that would be accidentally invisible to GC if the dirty
  68 bit were cleared after the first instruction.
  69
  70
  71 Additional tweaks
  72 =================
  73
  74 1. If PACKAGEs and FDEFNs are both in low space (using the non-moving GC),
  75 one 8-byte pointer slot in a SYMBOL can be made into 2 4-byte pointers
  76 so that SYMBOL-FDEFN becomes a mere slot reference.
  77 This is an utterly trivial change to the vops, and to the GC scavenge
  78 function for a symbol.
  79
  80 2. Non-moving GC could be used for non-toplevel CODE objects.
  81 This might allow all functions within the same file to use the
  82 ordinary x86 CALL instruction, under control of an optimize policy
  83 (because it would be difficult to trace/redefine/encapsulate)
  84
  85 3. If a closure header needs only 2 bytes for the length (probably true),
  86 there is 1 byte available for a generation# and there are 4 bytes for the
  87 layout of FUNCTION. The same is true for funcallable-instance and FUNCTION.
  88 Note that the generation# for a SIMPLE-FUN will be stored in
  89 the CODE-COMPONENT object, not the SIMPLE-FUN.
  90
  91 [unrelated]
  92 4. A build-time selection that limits array-total-size to 2^31 on 64-bit
  93 would allow a vector length to be stuffed into the vector header,
  94 which saves space for small vectors. A vector of length 3 would shrink
  95 from 6 physical words to 4 words - a 33% savings.