home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / lisp / 3109 < prev    next >
Encoding:
Internet Message Format  |  1992-12-18  |  2.0 KB
  1. Path: sparky!uunet!think.com!barmar
  2. From: barmar@think.com (Barry Margolin)
  3. Newsgroups: comp.lang.lisp
  4. Subject: Reference counting (was Re: Yet another Lisp Interpreter Available (RefLisp) Long)
  5. Date: 18 Dec 1992 00:19:31 GMT
  6. Organization: Thinking Machines Corporation, Cambridge MA, USA
  7. Lines: 29
  8. Message-ID: <1gr5ejINN3k5@early-bird.think.com>
  9. References: <1992Dec11.131657.19196@uk03.bull.co.uk> <1gk60iINNjg8@iraul1.ira.uka.de> <1992Dec17.200901.20942@uk03.bull.co.uk>
  10. NNTP-Posting-Host: telecaster.think.com
  11.  
  12. In article <1992Dec17.200901.20942@uk03.bull.co.uk> bbirch@hemel.bull.co.uk (Bill Birch) writes:
  13. >    - RefLisp has reference counting garbage collection, that means
  14. >      memory is reclaimed as soon as it is un-used. It is a "non-stop"
  15. >      system, in that there is never any halt for garbage collection (GC).
  16.  
  17. This is a frequent claim that is simply not true.  A reference counting
  18. system simply changes the time and distribution of the GC delays, but it
  19. doesn't eliminate it.  For instance, if you allocate a million-element
  20. list, and then lose the pointer to the first element, that operation will
  21. take a million times longer than losing a pointer to the head of a
  22. one-element list, as it has to recursively deallocate all the objects in
  23. the list (assuming there are no other pointers into the list).  No matter
  24. how fast your reference counting scheme is, I can always construct a data
  25. structure that takes a noticeable amount of time to deallocate it when the
  26. last pointer to the first element is dropped (assuming there's enough
  27. memory).
  28.  
  29. Reference counting GC's also have the misfeature that they must reference
  30. the object that a pointer points to when the pointer is reassigned.  On a
  31. system with demand-paged virtual memory, this could cause an unnecessary
  32. page fault, further slowing down the assignment.
  33.  
  34. Modern generational garbage collectors also distribute the GC delays more
  35. evenly than old stop-and-copy or mark-sweep GCs.
  36. -- 
  37. Barry Margolin
  38. System Manager, Thinking Machines Corp.
  39.  
  40. barmar@think.com          {uunet,harvard}!think!barmar
  41.