home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / function / 951 < prev    next >
Encoding:
Text File  |  1992-07-23  |  2.1 KB  |  51 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!europa.asd.contel.com!darwin.sura.net!mips!pacbell.com!decwrl!parc!boehm
  3. From: boehm@parc.xerox.com (Hans Boehm)
  4. Subject: GC complexity (was algorithmic efficiency and lazy languages)
  5. Message-ID: <boehm.711925393@siria>
  6. Sender: news@parc.xerox.com
  7. Organization: Xerox PARC
  8. References: <DTARDITI.92Jul21023549@DESERT.FOX.CS.CMU.EDU> <501@owl.ukc.ac.uk> <ACHA.92Jul23145206@DRAVIDO.SOAR.CS.CMU.EDU>
  9. Distribution: comp
  10. Date: 23 Jul 92 21:03:13 GMT
  11. Lines: 38
  12.  
  13. acha@CS.CMU.EDU (Anurag Acharya) writes:
  14. >... garbage collection needs time proportional to the
  15. >amount of live data (best case -- mark and sweep needs time proportional
  16. >to the all space available to the program). 
  17.  
  18. (I hate to start this thread again, especially since it's irrelevant to
  19. the previous discussion, but ...)
  20. As far as I know, the above statement about mark-sweep collection is
  21. only meaningful and correct if:
  22.  
  23. 1. Allocation and initialization time is not considered,
  24. 2. Concurrent or incremental collection is not considered.  (Otherwise it
  25. becomes hard  and pointless to distinguish the collector and the allocator.)
  26. 3. The M/S collector is not allowed to defer sweeping to allocation
  27. time, e.g. by using a bit map representation of the free list.
  28. 4. The collector does not attempt to maintain the heap size as a fixed
  29. multiple of the amount of live data (otherwise there's no asymptotic
  30. difference between the two).
  31.  
  32. (1) seems rather arbitrary.  There are great arguments for violating (2)
  33. through (4), and I don't know of any good arguments for not implementing
  34. at least (3) (and (4) under a real OS).
  35.  
  36. Thus, I think a more informative version of the standard statement
  37. about asymptotic complexity of mark/sweep collection is:
  38.  
  39. It's possible to implement mark-sweep collection so badly that garbage
  40. collector pause time is proportional to all space available to the
  41. program.
  42.  
  43. Of course, there are other arguments why mark-sweep collection might
  44. to e.g. copying collection under the right circumstances.  But I think
  45. the asymptotic complexity argument is 95% bogus.
  46.  
  47. Hans-J. Boehm
  48. (boehm@parc.xerox.com)
  49. Standard disclaimer ...
  50.  
  51.