From: Bruce L. Lambert, Ph.D.
Subject: How do I avoid consing?
Date:
Message-ID: <3468E1BB.A8232119@uic.edu>
Hi everyone,
I tend to write code that conses a lot, and it's a habit I'm trying to
break. I have Norvig's book and Graham's book and I try to take their
advice. But I had an additional question.
Is it generally bad form to allocate local variables (using let or let*)
within loops that iterate a lot? That is, is it better to create the
local variables at the top level and then setf them to the appropriate
values within the loop than it is to repeatedly allocate them (using let
statements within a do, dotimes, dolist, or loop)? Stylistically, it
often seems clearer to me to allocate the variables within the loops,
since they are automatically created (fresh, with correct default
values) at the start of each loop. The other option, while it seems
like it would cons less, leaves one with a lot of variables allocated in
a long let statement at the top of each function.
Thanks for your input.
--
Bruce L. Lambert
Department of Pharmacy Administration
University of Illinois at Chicago
Phone: (312) 996-2411
Fax: (312) 996-3272
email: ········@uic.edu
* Bruce L Lambert, Ph D wrote:
> Is it generally bad form to allocate local variables (using let or let*)
> within loops that iterate a lot? That is, is it better to create the
> local variables at the top level and then setf them to the appropriate
> values within the loop than it is to repeatedly allocate them (using let
> statements within a do, dotimes, dolist, or loop)? Stylistically, it
> often seems clearer to me to allocate the variables within the loops,
> since they are automatically created (fresh, with correct default
> values) at the start of each loop. The other option, while it seems
> like it would cons less, leaves one with a lot of variables allocated in
> a long let statement at the top of each function.
Depends a lot on the compiler. Note that `allocating' a local
variable is not allocating memory in the sense of consing. It may be
allocating stack space, or a register, or in fact nothing at all,
depending on how hairy the compiler's optimizer is. So the difference
between:
(let ((x ...))
(loop
...
(setf x (cons ...))
...))
and
(loop
...
(let ((x (cons ...)))
...))
isn't going to be how much gets consed except in very odd cases.
I think that this is a classic case where you need to measure things:
run the program in both variants , with real optimisation settings,
for real data and see where the time goes.
This is also a case where I'd guiltily resort to disassembling the
loop to see what the compiler did, if I knew it was really used a lot.
The LET-around-the-smallest-chunk-of-code solution is much nicer
though, I think.
--tim
>>>>> "Tim" == Tim Bradshaw <···@aiai.ed.ac.uk> writes:
Tim> Depends a lot on the compiler. Note that `allocating' a local
Tim> variable is not allocating memory in the sense of consing. It may be
Tim> allocating stack space, or a register, or in fact nothing at all,
Tim> depending on how hairy the compiler's optimizer is. So the difference
Tim> between:
Tim> (let ((x ...))
Tim> (loop
Tim> ...
Tim> (setf x (cons ...))
Tim> ...))
Tim> and
Tim> (loop
Tim> ...
Tim> (let ((x (cons ...)))
Tim> ...))
Tim> isn't going to be how much gets consed except in very odd cases.
One other comment: for CMUCL the latter code can produce much better
results because the compiler can more easily derive the type of X. It
is a fault of the compiler that if you setf a variable, the compiler
usually cannot derive the type of X and reverts usually to type NUMBER
or T.
Ray
Tim Bradshaw <···@aiai.ed.ac.uk> wrote something that led me to say:
Incidentally, this is a place that the language and present
implementations tend to deviate a lot. I hope one day compilers
will aspire to use all the power of the CL declaration system,
and particularly the DYNAMIC-EXTENT declaration.
People are probably familiar with these idioms which are
recognized and used by many CL implementations:
;;; Example 1.
;;; Permits such tricks as stack-allocated rest list.
(defun f (&rest x)
(declare (dynamic-extent x))
...)
;;; Example 2.
;;; Permits a "downward funarg" to be stack-allocated.
(defmacro with-foo (&body forms)
(let ((fn (gensym "THUNK")))
`(flet ((,fn () ,@forms))
(declare (dynamic-extent #',fn))
(call-with-foo #',fn))))
But there are other kinds of uses to which DYNAMIC-EXTENT
declarations can be made that are presently not used but that
you could legitimately ask for support. Such as:
;;; Example 3.
;;; Permits locally created objects like lists, arrays, and
;;; structures to be stack-allocated.
(defmacro stack-let (bindings &body forms)
`(let ,bindings
(declare (dynamic-extent ,@(mapcar #'car bindings)))
,@forms))
I'm also convinced that there are situations involving unboxed float
and double-float arithmetic which should be improved by declaring
intermediate quantities to be DYNAMIC-EXTENT, although there are some
issues to be worked out because sometimes a mathematical result might
be EQ to one of the inputs, and there needs to be an
assure-this-is-not-stack-allocated operator ... except it doesn't
have to be quite so strong.
(Note that DYNAMIC-EXTENT does not MEAN "stack-allocatable" in that
no Lisp is required to have a stack; the term is more general than
needed to just apply to stacks. But in practice, most people use
stacks, so I find the stack metaphors useful. We spent a lot of time
at X3J13 uselessly quibbling over this matter of whether the term
stack allocation was going to inhibit developers, and I have no
interest in re-opening that issue. So if you're a stack-hater,
read all of my above remarks with appriately generalized meaning.)
Tim> This is also a case where I'd guiltily resort to disassembling
Tim> the loop to see what the compiler did, if I knew it was really
Tim> used a lot.
Once in a while I agree this is needed. But it should never be done
until first determining that the code in question is a serious
performance bottleneck... the naive tendancy is to spend ages
optimizing silliness like this without examining how often it's
called, only later realizing it's made 1/1000th of the program's
typical execution time 3 times as fast (usually after hours of
work)... often a very poor investment.
Focus on abstract algorithmic speed of your program. Send vendors bug
reports about constant factors, but resist where possible the
temptation to tune code according to the incidental matter of one
compiler on one particular machine. If your code is worth doing,
you'd better hope it will outlast both that compiler and maybe even
that machine, and the last thing you need to be doing is spending your
precious lifetime microtuning it on future compilers and hardware.
I hope you don't want your tombstone to read
"He kept who-cares::something-unimportant 20% faster
for as long as he could... now he can finally rest."
* Kent M Pitman wrote:
> (defmacro with-foo (&body forms)
> (let ((fn (gensym "THUNK")))
> `(flet ((,fn () ,@forms))
> (declare (dynamic-extent #',fn))
> (call-with-foo #',fn))))
I actually wish that there was some way making a declaration like
Genera's DOWNWARD-FUNCTION -- I often use idioms like this (with
macrosity around them) to do the same sort of thing that
CALL-NEXT-METHOD does, and it's a real pain to have to bind the thing
to a variable all the time.
Tim> This is also a case where I'd guiltily resort to disassembling
Tim> the loop to see what the compiler did, if I knew it was really
Tim> used a lot.
> Once in a while I agree this is needed. But it should never be done
> until first determining that the code in question is a serious
> performance bottleneck... the naive tendancy is to spend ages
> optimizing silliness like this without examining how often it's
> called, only later realizing it's made 1/1000th of the program's
> typical execution time 3 times as fast (usually after hours of
> work)... often a very poor investment.
I did say `if I knew it was really used a lot'!
--tim
In article <·················@uic.edu>,
Bruce L. Lambert, Ph.D. <········@uic.edu> wrote:
>Is it generally bad form to allocate local variables (using let or let*)
>within loops that iterate a lot? That is, is it better to create the
>local variables at the top level and then setf them to the appropriate
>values within the loop than it is to repeatedly allocate them (using let
>statements within a do, dotimes, dolist, or loop)? Stylistically, it
>often seems clearer to me to allocate the variables within the loops,
>since they are automatically created (fresh, with correct default
>values) at the start of each loop. The other option, while it seems
>like it would cons less, leaves one with a lot of variables allocated in
>a long let statement at the top of each function.
Establishing local bindings doesn't cause any consing. Consing occurs when
you call functions that create new data structures. Local variables are
implemented in the compiler (since you're concerned about performance, I
assume you're compiling your program) simply by pushing the values onto the
stack.
Stylistically, you should arrange for the lifetimes of your variables to be
as small as possible. This can also improve performance, since the data
becomes garbage as soon as the variable's lifetime ends.
On the other hand, code can be tough to read it you have lots of nested
LETs, e.g.
(let ((var1 ...))
do stuff
(let ((var2 ...)
(var3 ...))
do more stuff
(let ((var4 ...))
...)))
looks more complex than:
(let ((var1 ...)
var2 var3 var4)
do stuff
(setq var2 ...
var3 ...)
do more stuff
(setq var4 ...)
...)
so it can be more convenient to create all the local variables at the
top level; this was the reason for &AUX variables in the lambda list.
One way to get the benefit of minimal lifetimes and still be readable is to
break your code into smaller functions rather than lots of nested
bindings. But if the inner scope needs to access and update the variables
established in the outer scope this can be difficult.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Please don't send technical questions directly to me, post them to newsgroups.