From: Peter Norvig
Subject: Can there be an efficient SWITCH form in CL?
Date:
Message-ID: <32711@ucbvax.BERKELEY.EDU>
Many languages support a syntactic construct that compiles into a
dispatch table. For example, in C, the statement:
switch(opcode) {
case 0: /* noop */ break;
case 1: acc+=arg; break;
case 2: acc-=arg; break;
...
}
can (at the compiler's discretion) dispatch directly to the right code
fragment, rather than comparing the key (opcode) against each case. In
Common Lisp, one could use CASE and hope that the compiler optimizes
into a dispatch table when appropriate, but in my experience compilers
do not make this optimization. I tried to write a macro to do this, but
it proved difficult. For simplicity, let's ignore the key processing of
SWITCH; and try to implement a zero-based computed-goto. Thus, the
fragment above would be:
(computed-goto opcode
() ; noop
(incf acc arg)
(decf acc arg)
...
)
And my first attempt at the macro is:
(defmacro computed-goto (key &rest clauses)
`(funcall
(aref (vector ,@(loop for c in clauses collect `#'(lambda () ,c)))
,key)))
This works, but it conses the vector and possibly some closures
on each application, so it is very inefficient. We need to create
the vector at compile time. Consider:
(defmacro computed-goto (key &rest clauses)
`(funcall
(aref ',(apply #'vector (loop for c in clauses collect `#'(lambda () ,c)))
,key)))
This produces a constant vector, but the vector holds s-expressions, not
closures, so local variables like acc and arg are not accessible. We
could try evaluating the `#'(lambda () ,c) expressions, but they have to
be evaluated in the calling environment, not the compiler's environment,
and the calling environment can change each time. Thus, I conclude that
an efficient computed-goto cannot be written in Common Lisp.
Does anybody have another approach? Or should we just insist that
compiler writers produce better code for (CASE n ...), and for
(aref (vector ...) n)?
- Peter Norvig ······@cogsci.Berkeley.EDU
From: Barry Margolin
Subject: Re: Can there be an efficient SWITCH form in CL?
Date:
Message-ID: <31749@news.Think.COM>
In article <·····@ucbvax.BERKELEY.EDU> ······@cogsci.berkeley.edu (Peter Norvig) writes:
> Or should we just insist that
>compiler writers produce better code for (CASE n ...), and for
>(aref (vector ...) n)?
After racking our brains a couple of years ago over this one, we complained
to Symbolics. As a result, the compiler in Genera 7.2 optimizes CASE
macros when all the keys are non-negative fixnums and the space of keys
isn't too sparse (if memory serves, "too sparse" is when fewer than half of
the keys between 0 and the largest key are used). Earlier this year I sent
them the minor modifications necessary to remove the reference to 0.
By the way, depending on the memory architecture of the machine, converting
a series of tests into a jump through a dispatch table might *not* be an
optimization. Some systems simultaneously prefetch both branches of a
conditional jump, but this can't be done easily with a dispatch. You can
often get better overall performance by putting the most common cases
first. This is why such optimization should be left to the compiler
(although it's still a hard problem, since different models of Symbolics
36xx's have different prefetch and caching characteristics, yet there is
only one compiler for the whole family).
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar