[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Dolist inefficiency

    Date: Mon, 13 Feb 89 14:08:25 -0500
    From: andrew@unagi.cis.upenn.edu

    Why is dolist so inefficient? -

It's only inefficient in interpreted code.  The expansion of DOLIST
includes a use of the POP macro inside the loop, and this gets
macro-expanded each time through the loop.  This macroexpansion conses
quite a bit (it gensyms temporary variables to hold the value of the
form in case it has side effects).

> (macroexpand '(dolist (x foo) (progn x)))
  (LET ((#:G11138 FOO)
        (X NIL))
      (GO #:G11137)
   #:G11136 (SETQ X (POP #:G11138))
      (PROGN X)
   #:G11137 (UNLESS (ENDP #:G11138)
	      (GO #:G11136))
      (RETURN NIL))))

> (macroexpand '(loop for x in foo do (progn x)))
      (#:G8526 FOO))
        (GO SI:NEXT-LOOP)
     SI:LOOP-BODY (SETQ X (CAR #:G8526))
        (SETQ #:G8526 (CDR #:G8526))
     SI:NEXT-LOOP (OR (NULL #:G8526)
		      (GO SI:LOOP-BODY))
     SI:END-LOOP ))

When they are compiled, DOLIST and DO-FOR-IN are nearly identical (the
only difference is that DOLIST uses ENDP and DO-FOR-IN uses NULL, but
there's no noticeable performance difference, because these are both
just microcoded type dispatches).