hoey@nrl-aic.ARPA (Dan Hoey) (09/25/86)
In AIList Digest V4 #191, Steven J. Clark responds to the statement that ``Garbage collection is much more sophisticated on Symbolics'' with his belief that ``To my knowledge this is absolutely false. S. talks about their garbage collection more, but X's is better.'' Let me first deplore the abuse of language by which it is claimed that Xerox has a garbage collector at all. In the language of computer science, Xerox reclaims storage using a ``reference counter'' technique, rather than a ``garbage collector.'' This terminology appears in Knuth's 1973 *Art of Computer Programming* and originated in papers published in 1960. I remain undecided as to whether Xerox's misuse of the term stems from an attempt at conciseness, ignorance of standard terminology, or a conscious act of deceit. The question remains of whether Interlisp-D or Zetalisp has the more effective storage reclamation technique. I suspect the answer depends on the programmer. If we are to believe Xerox, the reference counter technique is fundamentally faster, and reclaims acceptable amounts of storage. However, it is apparent that reference counters will never reclaim circular list structure. As a frequent user of circular list structure (doubly-linked lists, anyone?), I find the lack tantamount to a failure to reclaim storage. Apparently Xerox's programmers perform their own careful deallocation of circular structures (opening the cycles before dropping the references to the structures). If I wanted to do that, I would write my programs in C. I have never understood why Xerox continues to neglect to write a garbage collector. It is not necessary to stop using reference counts, but simply to have a garbage collector available for those putatively rare occasions when they run out of memory. Dan Hoey
neves@AI.WISC.EDU (David M. Neves) (09/27/86)
When I was using MIT Lisp Machines (soon to become Symbolics) years
ago nobody used the garbage collector because it slowed down the
machine and was somewhat buggy. Instead people operated for hours/days
until they ran out of space and then rebooted the machine. The only
time I turned on the garbage collector was to compute 10000 factorial.
Do current Symbolics users use the garbage collector?
"However, it is apparent that reference counters will never
reclaim circular list structure."
This is a common complaint about reference counters. However I don't
believe there is very many circular data structures in real Lisp code.
Has anyone looked into this? Has any Xerox user run out of space
because of circular data structures in their environment?
--
David Neves, Computer Sciences Department, University of Wisconsin-Madison
Usenet: {allegra,heurikon,ihnp4,seismo}!uwvax!neves
Arpanet: neves@rsch.wisc.eduambar@EDDIE.MIT.EDU (Jean Marie Diaz) (10/06/86)
In article <8609262352.AA10266@ai.wisc.edu> neves@ai.wisc.edu (David M. Neves) writes: >Do current Symbolics users use the garbage collector? At MIT, yes. I do recall at Rutgers this summer that I was forever doing a (gc-on), because some user there was turning it off.... -- AMBAR "Timid entrant into the Rich Rosen School of Computer Learning...."
tjhorton%ai.toronto.edu@RELAY.CS.NET ("Timothy J. Horton") (10/07/86)
> When I was using MIT Lisp Machines (soon to become Symbolics) years > ago nobody used the garbage collector because it slowed down the > machine and was somewhat buggy. Instead people operated for hours/days > until they ran out of space and then rebooted the machine. The only > time I turned on the garbage collector was to compute 10000 factorial. > Do current Symbolics users use the garbage collector? > > "However, it is apparent that reference counters will never > reclaim circular list structure." > > This is a common complaint about reference counters. However I don't > believe there is very many circular data structures in real Lisp code. > Has anyone looked into this? Has any Xerox user run out of space > because of circular data structures in their environment? > > -- > David Neves, Computer Sciences Department, University of Wisconsin-Madison > Usenet: {allegra,heurikon,ihnp4,seismo}!uwvax!neves > Arpanet: neves@rsch.wisc.edu In the Xerox environment at least, the extensive use of windows is one of the most common sources of problems. Often is the case that a window must be 'related' somehow to another window i.e. you create a subsidiary window for some main window (as a scroll window is to a display window), and the two windows must 'know' about each other. The obvious thing is to put pointers on each window's property list to the other window, "et viola" a circular list. Everything on the property lists of the two windows also gets kept around, and since Xerox windows are such good places to store things the circular structure is often very large. (check out the stuff on a 'Sketch' window's property list) A careful programmer can avoid such problems. In the case of windows, one just has to be careful about how windows find out about one another (some kind of global variable scheme or a directed search of all windows). Yet accidents happen and windows can kill the environment fairly quickly. Yes, I have lost an environment to just this problem (that's why I know), and it's very hard to tell what happened after the fact.