Subject: Re: Vector help
From: Erik Naggum <>
Date: 1998/02/19
Newsgroups: comp.lang.lisp
Message-ID: <>

* 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
  instead of flying by the seat of your pants.  that said, we've had a few
  very interesting exchanges in this newsgroup in the past that highlighted
  the vastly different approaches to speeding up Lisp code, so don't assume
  that there's a "last word" on this.

  hope this helps.

  God grant me serenity to accept the code I cannot change,
  courage to change the code I can, and wisdom to know the difference.