```Subject: Re: Vector help
From: Erik Naggum <clerik@naggum.no>
Date: 1998/02/19
Newsgroups: comp.lang.lisp
Message-ID: <3096859997279323@naggum.no>

* Kevin Goodier
| I have a list of length 32, and I'm going to be altering a couple of
| elements in it multiple times (meaning I'll be making many many copies of
| it).  I'm thinking that a simple vector would be the most efficient (i'm
| looking for FASTEST) way to go, but I can't for the life of me find a
| built-in function to convert a list to a vector.  Is there an easy and
| efficient way to do this??

I think

(make-array 32 :initial-contents <list>)

is the fastest and easiest way to convert a list of known length to a
vector of known size.  I also have reason to expect

(make-array (length <list>) :initial-contents <list>)

to be faster than the other suggestions in the unknown length case.

| The list is being given to me, so I can't just create a vector instead
| (unfortunately).  Is a simple vector going to be significantly faster?

well, there's faster and there's faster.  accessing element n in a list
is an O(n) operation in the general case, whereas accessing element n in
a vector is an O(1) operation.  the special case of accessing element n+1
when you last accessed element n is O(1) in both cases if you code well.

however, there are a few minor issues that affect the constants of these
upper limits to execution time.  stepping over a list with DOLIST will
need to keep track of two values, your variable and an (opaque) variable
that holds the tail, and you will need to make two memory references, but
all the parameters of these operations are known, so you will not make
any function calls to obtain the CAR and CDR of the successive CONS cells
-- these accessors will be open-coded, the test for NIL is trivial, and
the two values typically go in registers.  stepping over a vector of
unknown size with DOTIMES will need to keep track of the index into the
vector, test it against the size (with a function call), and will have to
do generic (as opposed to type-specialized) addition every time the index
is incremented, which is likely a function call.  on top of this, you are
likely to force a function call to AREF to access the element, which will
make another test for the size of the array, forcing several more memory
references in this "faster" case.  it may turn out that you could have
accesses two or three successive elements in a list by the time you have
accessed the first slot in a vector, at least as far as the traversal
skeleton is concerned.

if you want the most out of a vector traversal, you need to declare the
index to be a fixnum, declare the type and your best effort at the
dimension of the vector, and use the more specialized SVREF instead of
the more generic AREF if you can.  then you need to compile the code with
a high SPEED and probably a low SAFETY setting to force open-coding of
all of these functions.  in this case it will be as fast as the hardware
can bear, possibly even taking advantage of instructions that decrement a
counter register and branch on zero instead of incrementing, comparing,
and branch on equal.  trust me, all of this stuff adds up real quick.

e.g., Allegro CL 4.3.1 expand (dotimes (i 100) (aref <vector> i)) into

(do ((i 0 (1+ i)))
((>= i 100))
(declare (type (integer 0 100) i))
(aref <vector> i))

but (dotimes (i (length <vector>)) (aref <vector> i)) is expanded into

(do ((#:g140 (length <vector>))
(i 0 (1+ i)))
((>= i #:g140))
(aref <vector> i))

so you would need to add your declaration to get equal code.

speed in Lisp is a difficult issue.  it's hard to predict when the
compiler knows or doesn't know enough to generation the fastest available
code.  sometimes, what works in the default cause is very fast, such as
in DOLIST, which knows all it needs to know, and sometimes it is not at
all fast, such as in the DOTIMES/AREF case, where the compiler needs to
know far more about your intentions than it is possible to communicate
with these simple forms.

however, if you're lucky, LOOP is heavily optimized in your compiler and
may do the right thing in both cases.  LOOP/IN traverses a list and
LOOP/ACROSS traverses a vector.  however, I don't know of a way to make
LOOP/ACROSS use SVREF instead of AREF when I know that the vector is
simple.  any takers?

anyway, if you are concerned with speed, you have to consider your
hardware and your compiler, which to some people seem "un-Lispy", but
that is only because it is more natural to write correct code first than
to optimize the living daylight out of incorrect code.  the compiler
cannot know your intentions unless you tell it, but it is free to assume
a lot worse than you might expect.  (and strong typing is _not_ the
answer -- it's much worse to pretend to illuminate the compiler when
you're still in the dark yourself than to keep the compiler in the dark
with you.)  most Lisp compilers come with profilers, call counters, and
other tools to help you decide when, where, and how to optimize.  this
way you can make an informed estimate of the expected performance gains