nancy@GRASP.CIS.UPENN.EDU (Nancy Orlando) (07/17/87)
Are there any "accepted" methods of writing code that minimize a LISP's tendancy to garbage-collect? I don't mean a switch to turn it off; just a means of minimizing the need for it. I'm dealing particularly with DEC VAX lisp. I have assumed that iteration as opposed to recursion was one way; is this correct? Are there other techniques? Nancy Sliwa nancy@grasp.cis.upenn.edu or nesliwa%telemail@orion.arpa
Chester@UDEL.EDU (07/21/87)
The direct way to avoid garbage collection in lisp is to define your own `cons' function that prefers to get cell pairs from an `available list', calling the regular `cons' only when the `available list' is empty. A `reclaim' function that puts cell pairs on the `available list' (using `rplacd') will be needed also. See any book on data structures. The technique can be used for cell pairs and gensym atoms, if needed, but in my experience, not with strings or numbers. String manipulations can usually be avoided, but a program that crunches a lot of numbers cannot avoid consuming memory and eventually triggering garbage collection (at least in VAX lisp). I wish there were some way for a user to reclaim numbers so that they could be reused as cell pairs can. If so, I could write all my lisp programs so that they don't need to garbage collect. It would also be nice to have a built-in `reclaim' function that would work in conjunction with the built-in `cons'; it would be dangerous for novices, but handy for the experienced. By the way, recursion in itself doesn't cause garbage collection; VAX lisp is smart enough to reclaim the memory used for the function stack automatically. Daniel Chester chester@dewey.udel.edu
biep@cs.vu.nl ("J. A. "Biep" Durieux") (07/22/87)
In article <8707202143.aa23792@Dewey.UDEL.EDU> Chester@UDEL.EDU writes: >The direct way to avoid garbage collection in lisp is to define your own `cons' >function that prefers to get cell pairs from an `available list' (...). Also handy in many cases (small functions like append, alist-functions, subst) is icons: (defun icons (a d cell) (cond ((and (eq (car cell) a) (eq (cdr cell) d)) cell) (t (cons a d)))) In this way whenever it turns out the new cells weren't really needed, the old ones are used again (as in (append x nil)). Be aware, however, that your copy-function may not work any more if it's defined as (subst nil nil x)! -- Biep. (biep@cs.vu.nl via mcvax) Never confound beauty with truth!
nesliwa%telemail@AMES.ARPA (NANCY E. SLIWA) (07/29/87)
My thanks to all the respondants to my question about garbage
collection suppression. As several people asked for the results, I'm
posting it for all:
Date: Friday, 17 July 1987 07:32-CDT
From: nancy at grasp.cis.upenn.edu (Nancy Orlando)
Are there any "accepted" methods of writing code that minimize a LISP's
tendancy to garbage-collect? I don't mean a switch to turn it off;
just a means of minimizing the need for it. I'm dealing particularly with
DEC VAX lisp. I have assumed that iteration as opposed to recursion was
one way; is this correct?
From: Chester@UDEL.EDU
Subject: Re: Garbage Collection Suppression
The direct way to avoid garbage collection in lisp is to define your own `cons
function that prefers to get cell pairs from an `available list', calling the
regular `cons' only when the `available list' is empty. A `reclaim' function
that puts cell pairs on the `available list' (using `rplacd') will be needed
also. See any book on data structures. The technique can be used for cell
pairs and gensym atoms, if needed, but in my experience, not with strings or
numbers. String manipulations can usually be avoided, but a program that
crunches a lot of numbers cannot avoid consuming memory and eventually
triggering garbage collection (at least in VAX lisp). I wish there were some
way for a user to reclaim numbers so that they could be reused as cell pairs
can. If so, I could write all my lisp programs so that they don't need to
garbage collect. It would also be nice to have a built-in `reclaim' function
that would work in conjunction with the built-in `cons'; it would be dangerous
for novices, but handy for the experienced.
By the way, recursion in itself doesn't cause garbage collection; VAX lisp is
smart enough to reclaim the memory used for the function stack automatically.
Daniel Chester
chester@dewey.udel.edu
Date: Mon, 20 Jul 87 01:36:44 PDT
From: woutput@ji.Berkeley.EDU (Andrew Purshottam)
Subject: Re: Garbage Collection Suppression
Forgive me if my response is too trivial, but you ommited
the most important technqiue for reducing gc use, limiting the use,
implict and explict, of cons. Particularly nasty is the use of
append or append1 (not sure what that is called in CL) to build up a list
by adding elements to its end. This method uses O(n^2) cons cells,
where n is the length of list built. Standard solutions include the use
of "accumulators", arguments which hold a partial result which
is modified in inner recursions and finally returned as
value when the function returns; building the list backword
and maybe reversing it at end; nconc, which uses O(n^2) time but
only O(n) space; or tconc structures, which keep a pointer to
the end of the list. (In prolog we have a cute method avail,
putting an uninstantiated element at the end of the list, effectively
a "hole" that can be filled by an element and another hole).
Not also that some popular functional programming techniques,
particularly those involving streams and higher order procedures
are quite greedy in cons cells, as they build intermediate lists,
most of whose elements are thrown away. The apply-append-mapcar
trick, the set functions like (filter 'pred 'list), union, and intersect
all do this if implemented in the obvious way, with the sets represented
and fully computed lists. The Black Book (Charniak/McDerrmot, AI Programming)
discusses more eff. ways to deal with this using generators, where
no more elements are computed than needed. (See also Abelson/Sussman
for a very readable (we inflict it on freshman!) discussion of delay
and force).
Again, excuse if this is too simple, no offense intended.
Andy
--
Cheers, Andy (...!ucbvax!woutput woutput@ji.berkeley.edu)
(cond ((lovep you (quote LISP)) (honk)) (t (return ())))
Date: Mon, 20 Jul 1987 05:32 CDT
From: AI.DUFFY@R20.UTEXAS.EDU
Subject: Garbage Collection Suppression
No. You make garbage when you create data structures. Recursion v.
iteration has nothing to do with it, unless VAXlisp is more
brain-damaged than I already know it to be.
Are there other techniques?
Use destructive list operations (e.g., NCONC instead of APPEND) when
you can. If you have any arrays, structures, etc., that you are using
temporarily, you can resource them (make a bunch of them and push them
onto a list, pop one off when you want to use it, and when you are
finished with it, nullify its slots and push it back onto the list).
Your best bet, of course, is to get more memory.
Date: 20 Jul 87 09:32:01 edt
From: Walter Hamscher <hamscher@ht.ai.mit.edu>
Subject: Garbage Collection Suppression
Iteration vs. Recursion is orthogonal. By using recursion where you
could have used iteration, you may be using _stack_ space, but that's
trivially `garbage collected' every time you return from a function
(this is non-tail recursion I'm talking about). The only surefire way
to reduce garbage collection is to call CONS and and MAKE-ARRAY (and
things that call them) less often. There are a number of implications
of that for coding style (e.g. pass functions down instead of passing
consed structures up), but using iteration is not one of them.
Date: Mon, 20 Jul 1987 10:12 EDT
From: "Scott E. Fahlman" <Fahlman@C.CS.CMU.EDU>
Subject: Consing
Nancy,
In order to avoid GC's, you have to write your code in a way that avoids
consing up data structures, especially in inner loops. In the Vax
Common Lisp, I think that recursion is faster than the equivalent
iteration, but consing is not the reason; what you're seeing is the
difference between access to just a few variables (in registers or in
the cache) versus spreading out copies of those registers on the stack,
with all the associated memory references for pushing and popping.
How to avoid consing in any given Comon Lisp is a complex topic.
Perhaps the DEC people have some training materials on how to do this in
their Lisp. But there are a few things to watch for:
Make sure all your code is compiled. A lot of Lisps cons furiously in
the interpreter while consing very much less in compiled code.
If you are consing up vectors and strings in some inner loop solely for
communication with other routines, consider passing the info in a single
pre-allocated vector instead.
Some Lisps cons when passing &rest args and &keyword args. Check this.
Often a bit of Consing can make code clearer and easier to maintain.
Find who is doing the consing that is bothering you and squeeze that
part of the code for maximum efficiency; don't just squeeze everything,
because maintainability will be harmed.
-- Scott Fahlman
Date: Mon, 20 Jul 87 10:15:53 EDT
From: Mario O. Bourgoin <mob@MEDIA-LAB.MEDIA.MIT.EDU>
Subject: Re: Garbage Collection Suppression
Hello,
What you want to do is avoid storage allocation operations.
Most of the methods for doing this are implementation dependant. For
example, in Scheme iteration constructs expand to tail-recursive calls
so there's no point in trying to change function calls to do-loops.
Furthermore, good Lisp implementations optimize function calls since
they are the most used operation; they are usually cheaper than the
looping alternatives.
Lisp compilers can usually do excellent optimizations if you
use the implemetation's features. For example, ZetaLisp offers a LOOP
iteration macro which allows the programmer to communicate to the
compiler the necessary information for the latter to produce the most
efficient code possible.
What you can do reliably is to avoid using operations that
cons a lot such as `append' and use their structure modifying
alternatives such as `nconc'. You should be careful to write your
programs with the modifying operations from the beginning to avoid
encountering problems with them if you change over from the consing
operations.
Remember that operations such as the arithmetic functions must
allocate storage for their result. It might be worth your while to
code basic operations and inner loops in another language such as `C'
to avoid allocation.
--Mario O. Bourgoin
(This next was is response to a follow-up request of mine, asking if call-outs
to non-lisp external routines helped decrease garbage collection.)
Date: Thu, 23 Jul 87 9:11:18 EDT
From: Chester@UDEL.EDU
Subject: Re: garbagecollection
We have no experience with calling out to another language just to do
number crunching. My guess is that the overhead of switching languages
and of communicating between them and lisp would be too much, but that is
just a guess. If you find out differently, let me know.
Date: 22 Jul 87 14:28:51 GMT
From: "J. A. \"Biep\" Durieux" <mcvax!cs.vu.nl!biep@seismo.CSS.GOV>
Subject: Re: Garbage Collection Suppression
In article <8707202143.aa23792@Dewey.UDEL.EDU> Chester@UDEL.EDU writes:
>The direct way to avoid garbage collection in lisp is to define your own `con
>function that prefers to get cell pairs from an `available list' (...).
Also handy in many cases (small functions like append, alist-functions, subst)
is icons: (defun icons (a d cell)
(cond ((and (eq (car cell) a) (eq (cdr cell) d)) cell)
(t (cons a d))))
In this way whenever it turns out the new cells weren't really needed, the
old ones are used again (as in (append x nil)). Be aware, however, that your
copy-function may not work any more if it's defined as (subst nil nil x)!
--
Biep. (biep@cs.vu.nl via mcvax)
*****************************************************************************
I also noticed that the current (Aug.-Sept. 87) issue of LISP Pointers
has two good articles about garbage collection: "Overview of Garbage
Collection in Symbolic Computing," by Timothy J. McEntree (TI) and
"Address/Memory Management For A Gigantic LISP Environment or, GC
Considered Harmful," by Jon L. White (MIT). LISP Pointers subscriptions
are available from:
LISP Pointers
Mary S. Van Deusen, Editor
IBM Watson Research
PO Box 704
Yorktown Heights, NY 10598