home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compiler / 1375 < prev    next >
Encoding:
Text File  |  1992-08-15  |  4.3 KB  |  86 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!wupost!gumby!yale!mintaka.lcs.mit.edu!spdcc!iecc!compilers-sender
  3. From: boehm@parc.xerox.com (Hans Boehm)
  4. Subject: Re: Garbage Collection
  5. Reply-To: boehm@parc.xerox.com (Hans Boehm)
  6. Organization: Xerox PARC
  7. Date: Fri, 14 Aug 1992 20:37:33 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-08-074@comp.compilers>
  10. References: <92-08-015@comp.compilers> <92-08-056@comp.compilers>
  11. Keywords: storage, GC
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 71
  14.  
  15. eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig) writes:
  16. [Much text omitted]
  17. >    Sure, threads are important.  Sure, multiple threads in a single
  18. >process should share the same heap space.  All I'm saying is that there is
  19. >no need to use some external "alarm" interrupt to slavishly switch
  20. >contexts immediately upon receipt of such a signal.  We can, as I
  21. >explained earlier, switch contexts _only_ at the beginning of basic
  22. >blocks.  What's a few more instructions between context switches?
  23.  
  24. Clearly no problem, assuming you don't need to add frequently executed
  25. code to accomplish this.  I don't know how to do this without
  26. single-stepping from the signal handler, which may or may not be easy,
  27. depending on hardware and OS.
  28.  
  29. >If we decide, in an attempt to be _really_conservative_,
  30. >to assume everything is a pointer, then we pay a double penalty: since
  31. >we're wasting time moving junk around, garbage collection takes longer,
  32. >and since we're not reclaiming storage that is actually free, we collect
  33. >more often.
  34.  
  35. Note that we can't literally move things around, since relocating integers
  36. to point to tospace is a bad idea.
  37.  
  38. >    It seems clear that this naive approach won't be satisfactory ...
  39.  
  40. As David points out, it is usually satisfactory, assuming some care in the
  41. implementation of the allocator/collector.  In fact, many existing systems
  42. to precisely that, at least for stack references.  These include various
  43. versions of Cedar at PARC, Modula-2+ and Modula-3 implementations at DEC
  44. SRC, AKCL, Joel Bartlett's Scheme-to-C implementation, Sather, etc.
  45.  
  46. There's even a somewhat convincing argument that this should work.  Assume
  47. (here's the flakey part) that all values in the stack are either permanent
  48. or change fairly quickly.  Those that are valid pointers don't concern us
  49. (*).  Those that are short-lived are also OK, since they at worst postpone
  50. collection of some objects a little bit.  Empirically, this is a minor
  51. effect, and any generational collector will have the same problem,
  52. probably to a larger extent.  The permanent non-pointers are also easy to
  53. deal with; we look for them before we start (and at every later gc), and
  54. refuse to allocate at those adresses.
  55.  
  56. (There are actually two problems with this, both minor in practice.
  57. Long-lived nonpointers may be created while the program is running.
  58. More importantly, valid, but dead, pointers may not be cleared in a
  59. timely fashion.  This is somewhat orthogonal to conservative collection.
  60. In my experience, on an architecture like SPARC, this dominates,
  61. since many sections of the stack are not written frequently.
  62. Hence statement (*) isn't really correct.  The effect can be
  63. reduced by explicitly clearing dead stack frames from the allocator,
  64. on occasion.)
  65.  
  66. >    I just don't see how you're going to allow garbage collection to
  67. >occur _anywhere_ and handle any sort of tagged heap.  Are you assuming
  68. >that procedure calls and heap allocations are atomic?  What happens if I
  69. >have to garbage collect while I'm in the middle of allocating a record,
  70. >and haven't written the length of the record to the heap yet?
  71.  
  72. There are two ways of dealing with this.  With high allocation rates, you
  73. probably need to give each thread its own chunk of memory that it can
  74. allocate from without synchronization.  With lower allocation rates,
  75. allocation can acquire a lock to prevent conflicts.  The PCR allocator
  76. acquires and releases a monitor lock (perhaps with some minor shortcut)
  77. for each allocation.  This isn't free, but the only cost is during
  78. allocation.  With Cedar-like (or Modula-3 like or C-like) allocation
  79. frequencies this probably makes sense.  It's almost never a bottleneck.
  80. With SML-of-NJ like allocation rates, it's a bad idea.
  81.  
  82. Hans-J. Boehm
  83. -- 
  84. Send compilers articles to compilers@iecc.cambridge.ma.us or
  85. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  86.