home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compiler / 1418 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  3.7 KB
  1. Path: sparky!uunet!stanford.edu!rutgers!faatcrl!iecc!compilers-sender
  2. From: pardo@cs.washington.edu (David Keppel)
  3. Newsgroups: comp.compilers
  4. Subject: Large-space GC
  5. Keywords: GC, storage, design
  6. Message-ID: <92-08-117@comp.compilers>
  7. Date: 20 Aug 92 02:23:17 GMT
  8. Sender: compilers-sender@iecc.cambridge.ma.us
  9. Reply-To: pardo@cs.washington.edu (David Keppel)
  10. Organization: Computer Science & Engineering, U. of Washington, Seattle
  11. Lines: 67
  12. Approved: compilers@iecc.cambridge.ma.us
  13.  
  14. As long as we're discussing GC: has anybody studied garbage collection in
  15. wide-address/persistant store machines?  Consider, for example, that you
  16. have a machine with a 64-bit address space and a distributed single-level
  17. store.  In such a system it is likely that pointers in the active process
  18. will point to memory on disk, across the network, etc.  Today's GC's
  19. already can take a long time because the GC space may be hundreds of
  20. megabytes and because parts of that space are out of main memory.  In
  21. ``large-space'' machines it is likely a space will be many gigabytes of
  22. fragmented memory, distributed across even devices slower than disks.
  23.  
  24. Note that `conventional' distributed GC algorithms don't really solve the
  25. problem because they still are designed for spaces on the order of
  26. hundreds of megabytes.  In short, they assume the the entire pointer space
  27. can be traced to do one round of GC.
  28.  
  29. I am imagining situations where a process can map in large databases that
  30. are used only sparsely, or where a process contains a pointer to a data
  31. structure that contains pointers in to other processes, each happily
  32. generating (and reclaiming) garbage.  Even a simple dictionary could cover
  33. gigabytes of data structures describing text, tables, static pictures,
  34. animations, and so on.  The time to trace the dictionary is probably on
  35. the order of days.
  36.  
  37. The general problem is that in a large address space there isn't enough
  38. time to trace *all* pointers to live objects.  The GC really needs to
  39. restrict the search to reasonable-size subspaces.
  40.  
  41. I imagine several possible solutions, but I'm sure there must be
  42. others besides:
  43.  
  44.  - Reference counting.  Tends to have a large compute overhead and
  45.    fails when there are cycles, but has excellent locality and can
  46.    reallocate freed storage immediately.
  47.  
  48.  - Mark segments of the memory space as non-GC'd.  Variations are
  49.    possible: the collector gets to avoid performing a collection in the
  50.    segment, it gets to assume that the segment is never GC'd, thus
  51.    never moves, contains no roots, ...
  52.  
  53.  - Mark segments as externally GC'd.
  54.  
  55.  - Keep summary info for a segment, where the summary info says what
  56.    other segments have pointers in to the segment and what other
  57.    segments are pointed to by the segment.  The summary info might be
  58.    similar to inter-generation info in generational collectors, or to
  59.    distributed collector references.
  60.  
  61.  - Make all references in to a segment equivalent.  The segment is
  62.    deallocated all at once, and only when the last pointer in to the
  63.    segement disappears.
  64.  
  65.  - Qualify objects and types as reference-contributing or not,
  66.    exportable (to another segment) or not, ...
  67.  
  68. There are additional problems to be solved.  For example, for security and
  69. protection reasons, my user-level process really shouldn't be allowed to
  70. set mark bits in something owned by another ``administrative entity.''
  71. Yet halting tracing at read-only boundaries doesn't work, because the
  72. read-only object may have a reference back in to the local (writable)
  73. segment that the collector is trying to GC.
  74.  
  75. I will summarize e-mail.
  76.  
  77.     ;-D oN  ( GC for the 90's: Reduce, Reuse, Recycle! )  Pardo
  78. -- 
  79. Send compilers articles to compilers@iecc.cambridge.ma.us or
  80. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  81.