home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / lisp / 3128 < prev    next >
Encoding:
Internet Message Format  |  1992-12-22  |  2.2 KB
  1. Path: sparky!uunet!pipex!bnr.co.uk!uknet!mcsun!sunic!sics.se!eua.ericsson.se!erix.ericsson.se!rv
  2. From: rv@erix.ericsson.se (Robert Virding)
  3. Newsgroups: comp.lang.lisp
  4. Subject: Re: Reference counting (was Re: Yet another Lisp Interpreter Available (RefLisp) Long)
  5. Message-ID: <1992Dec22.141011.8019@eua.ericsson.se>
  6. Date: 22 Dec 92 14:10:11 GMT
  7. References: <1992Dec11.131657.19196@uk03.bull.co.uk> <1gk60iINNjg8@iraul1.ira.uka.de> <1992Dec17.200901.20942@uk03.bull.co.uk> <1gr5ejINN3k5@early-bird.think.com>
  8. Sender: news@eua.ericsson.se
  9. Organization: Ellemtel Telecom Systems Labs, Stockholm, Sweden
  10. Lines: 28
  11. Nntp-Posting-Host: renat.eua.ericsson.se
  12. Nntp-Posting-User: rv
  13.  
  14. In article <1gr5ejINN3k5@early-bird.think.com>, barmar@think.com (Barry Margolin) writes:
  15. >In article <1992Dec17.200901.20942@uk03.bull.co.uk> bbirch@hemel.bull.co.uk (Bill Birch) writes:
  16. >>    - RefLisp has reference counting garbage collection, that means
  17. >>      memory is reclaimed as soon as it is un-used. It is a "non-stop"
  18. >>      system, in that there is never any halt for garbage collection (GC).
  19. >
  20. >This is a frequent claim that is simply not true.  A reference counting
  21. >system simply changes the time and distribution of the GC delays, but it
  22. >doesn't eliminate it.  For instance, if you allocate a million-element
  23. >list, and then lose the pointer to the first element, that operation will
  24. >take a million times longer than losing a pointer to the head of a
  25. >one-element list, as it has to recursively deallocate all the objects in
  26. >the list (assuming there are no other pointers into the list).  No matter
  27. >how fast your reference counting scheme is, I can always construct a data
  28. >structure that takes a noticeable amount of time to deallocate it when the
  29. >last pointer to the first element is dropped (assuming there's enough
  30. >memory).
  31.  
  32. There are reference counting schemes in which the GC delays can be
  33. made arbitarily small, even real-time. It is not my scheme but I know
  34. because I have made a real-time implementation using it. See
  35.  
  36. Glaser, H.W., and Thompson, P., "Lazy Garbage Collection". Software -
  37. Practice and Experience, 17(1), 1-4, January 1987.
  38.  
  39.  
  40.         Robert Virding  @ Ellemtel Utvecklings AB, Stockholm
  41.         EMAIL: rv@erix.ericsson.se
  42.