Dolist inefficiency

["William D. Gooch" <ai.gooch@MCC.COM>]

    Why is dolist so inefficient? -

    > (progn (setf foo (loop for x below 1000 collect x)) nil)
    > (time (loop for x in foo do x)) ....
    > (time (dolist (x foo) x)) ....

It isn't.  You're timing macroexpansion.

1Always compile0 the things you want to meter.  See my results (for a
3630 with 8Mwords) below.

By the way, Symbolics offers an excellent course on optimization
for high performance which I recommend highly to anyone interested in
learning about accurately measuring performance and identifying where
time is being spent, as well as what to do about it. 


Command: (defun foo-loop (list) (loop for x in list doing (ignore x)))
FOO-LOOP
Command: (compile *)
FOO-LOOP

Command: (defun foo-list (list) (dolist (x list) (ignore x)))
FOO-LIST
Command: (compile *)
FOO-LIST

Command: (progn (setf foo (loop for x below 1000 collect x)) nil)
NIL

Command: (time (foo-loop foo))
Evaluation of (FOO-LOOP FOO) took 0.005557 seconds of elapsed time including:
  0.000 seconds processing sequence breaks,
  0.003 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.003 seconds processing 8 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
NIL
Command: (time (foo-list foo))
Evaluation of (FOO-LIST FOO) took 0.004957 seconds of elapsed time including:
  0.001 seconds processing sequence breaks,
  0.000 seconds in the storage system (including 0.000 seconds waiting for pages):
    0.000 seconds processing 4 page faults including 0 fetches,
    0.000 seconds in creating and destroying pages, and
    0.000 seconds in miscellaneous storage system tasks.
NIL

Looking at the disassemblies below, you can see that there is ultimately
very little difference in the potential performance of these functions.
Unfortunately, this isn't a fact that one can generalize from, even in
regard to the relative performance of dolist versus loop in general. 

Command: (disassemble 'foo-loop)
  0  ENTRY: 1 REQUIRED, 0 OPTIONAL
  1  PUSH-NIL                   ;creating X(FP|1)
  2  PUSH-LOCAL FP|0            ;LIST   creating FP|2 (unnamed)
  3  BRANCH 7
  4  BUILTIN CAR STACK FP|2
  5  POP-LOCAL FP|1             ;X
  6  BUILTIN CDR-LOCAL IGNORE FP|2
  7  PUSH-LOCAL FP|2
 10  BRANCH-TRUE 4
 11  RETURN-NIL 

#<DTP-COMPILED-FUNCTION FOO-LOOP 141540067>

Command: (disassemble 'foo-list)
  0  ENTRY: 1 REQUIRED, 0 OPTIONAL
  1  PUSH-LOCAL FP|0            ;LIST   creating FP|1 (unnamed)
  2  PUSH-NIL                   ;creating X(FP|2)
  3  BRANCH 7
  4  BUILTIN CAR STACK FP|1
  5  BUILTIN CDR-LOCAL IGNORE FP|1
  6  POP-LOCAL FP|2             ;X
  7  PUSH-LOCAL FP|1
 10  BRANCH-NOT-ENDP 4
 11  RETURN-NIL 

#<DTP-COMPILED-FUNCTION FOO-LIST 141540100>