macros, boxing, closures
Gary Livingston
I really appreciate these discussions on optimization. After following the
threads on Larry Hunter's optimization problem, I have several questions:
1. What is 'boxing?' Is it when a variable is copied to prevent a body of
code from possibly changing the original value of a variable? Is this
copying done as part of a function call, inside the function, or both,
depending on decisions made by the compiler.
2. What are closures? I feel these are related to function calls, but
I think they are more. Do function calls create closures?
3. Do inlines and macros produce essentially the same code? This one I will
attempt to answer myself by writing two versions of the same function, one
using inline and the other using macros and comparing them. This trick of
looking at the dissassembled code is a new trick for me.
Thanks,
Gary
Barry Margolin
In article <5uc7lm$l...@usenet.srv.cis.pitt.edu>,
Gary Livingston <ga...@cs.pitt.edu> wrote:
>1. What is 'boxing?' Is it when a variable is copied to prevent a body of
>code from possibly changing the original value of a variable? Is this
>copying done as part of a function call, inside the function, or both,
>depending on decisions made by the compiler.
Boxing is when a value is wrapped up in a data structure in memory. For
instance, CPU's can operate on integers and floating point numbers
directly, but the same machine word could be used to represent either a
integer or floating point value. If the language supports runtime type
dispatching, it has to be able to tell the type of a value in memory, and
this is done by making it part of a larger data structure, where another
word contains the type information.
Boxing also refers to (implicitly) accessing a data object indirectly via a
pointer. The type information referred to above would be stored with the
pointer (sometimes this is implicit, using the BIBOP mechanism, where all
the objects in the same area of memory have a particular type).
Boxing creates inefficiencies, because the boxed objects take up more
memory and require extra effort to access.
>2. What are closures? I feel these are related to function calls, but
>I think they are more. Do function calls create closures?
A closure is a combination of a function and an environment. The
environment contains the bindings of some (or all variables), so a closure
allows a function to retain some memory of the variable bindings that were
in effect at the time it was created.
>3. Do inlines and macros produce essentially the same code? This one I will
>attempt to answer myself by writing two versions of the same function, one
>using inline and the other using macros and comparing them. This trick of
>looking at the dissassembled code is a new trick for me.
In Lisp, macros allow a program to write another program. They're
generally used for the types of things that functions can't do
conveniently, such as creating new syntactic forms (e.g. DO).
If you write a macro that has the semantics of a function, you'll generally
get similar code to what you would have gotten with an inline function.
Note that it can be difficult to get all the semantics right when
implementing a macro -- you might inadvertently change the order of
evaluation of subexpressions, or you might introduce new variables that
could shadow variables that the expressions reference. If what you want to
do can be done with either an inline function or a macro, inline is
preferred. On the other hand, inline expansion is optional on the part of
the compiler, and not all compilers do it, so if you *really* can't abide
the overhead of a function call, a macro is necessary. But make sure that
you've profiled things and determined that this function call is the true
bottleneck.
--
Barry Margolin, bar...@bbnplanet.com
BBN Corporation, 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.
Erik Naggum
* Gary Livingston
| 1. What is 'boxing?'
the allocation of a new object that holds a value that cannot be held in a
machine word due to the information required by Lisp to represent the type
of the object. the term "boxed" itself comes from the way one would store
such a value when pointers themselves could not hold type information.
e.g., suppose you have a value V that you wished to return with type
information. V itself could be just about any bit pattern and could not
tell anyone what it was. you would then create a new object that held type
information about V, and then (a copy of) V, and return that object. since
pointers can often contain type information, you may not need to waste
memory on type information, but you still need to point to the newly
created "box" that holds the value.
| 2. What are closures?
a function is said to be closed over bindings (variables) that are part of
the lexical scope in which the function is defined. e.g., in
(let ((counter 0))
(defun counter ()
(incf counter))
(defun (setf counter) (new-counter)
(setq counter new-counter)))
the functions `counter' and `setf counter' are closures that have access to
the lexical variable "counter".
however, the important purpose of closures is passing them around:
(defun foo (x)
(mapcar (lambda (y) (+ x y)) *some-global*))
we note that the anonymous function uses the variable `x' from its
lexically scope, but is passed to `mapcar' and is expected to work.
likewise, in this series of trivial examples, the function `add' returns a
function that takes one argument and returns the sum of that argument and
the argument to `add':
(defun add (x)
(lambda (y) (+ x y)))
such that you can say
(mapcar (add 5) '(10 20 30))
as Henry Baker once pointed out to me, closures can be used to create a
"structure" concept.
| 3. Do inlines and macros produce essentially the same code?
no. macros are functions that are called by the compiler to expand the
macro call form to another form, which is then compiled in its place.
function calls that are inlined cause the function body itself to produce
compiled code in situ.
macros should _never_ be used for optimization. it's simply the wrong
solution. if special considerations for inlining or speed is required, a
_compiler-macro_ should be employed in addition to the actual function.
you can cause a macro and an inlined function call to produce the same
code, but they would look very different.
an example would be too elaborate, but see the Common Lisp HyperSpec at
http://www.harlequin.com/books/HyperSpec/Body/mac_define-compiler-macro.html
for some excellent examples.
| This one I will attempt to answer myself by writing two versions of the
| same function, one using inline and the other using macros and comparing
| them. This trick of looking at the dissassembled code is a new trick for
| me.
my favorite AI Koan from the Jargon File (noting that Tom Knight was one of
the principle designers of the Lisp Machine):
A novice was trying to fix a broken Lisp machine by turning the power
off and on.
Knight, seeing what the student was doing, spoke sternly: "You cannot
fix a machine by just power-cycling it with no understanding of what is
going wrong."
Knight turned the machine off and on.
The machine worked.
many things "work", most by accident, a few by design. the task of the
conscientious student is to separate the two from each other, and then only
use those that work by design, unless the design is broken, which it takes
an even more conscientious student to figure out. so, don't be satisfied
when you find something that works, go on to figure out why and whether it
was by design or accident.
hope this helps.
#\Erik
--
404 You're better off without that file. Trust me.
Gary Livingston
O.K. Now about boxing...
People have been very good about defining boxing. The next question is how
to avoid it. The following solutions are ideas that I have that sound like
they might help avoid boxing. However I am not 100% sure. Also, how can one
tell that something is boxed by looking at the assembler code?
Possible solutions for avoiding boxing:
Inlined function. Avoids function calls which it sounds like caused
Larry Hunter's code to box floats.
Strong typing. I have time trials, and using (the float ...)
specifications in my numerical functions but I don't seem to
get any speed-up.
By the way, I am using Lucid Common Lisp, Version 4.0, 1990.
THanks,
Gary Livingston
Henry Baker
> * Gary Livingston
> | 1. What is 'boxing?'
Something mysterious that Brits do the day after Christmas, when Americans
are throwing the boxes away....