From: lawrence.g.mayka
Subject: Models of iteration in ANSI Common Lisp
Date:
Message-ID: <15130@cbnewsc.ATT.COM>
I have been comparing the various iteration models available in
ANSI Common Lisp. Ideally, I will decide which ones I consider
preferable for which situations (according to various criteria
such as understandability, modifiability, and efficiency), then
modify my programming practice to conform to this decision.
Before I do this, however, I would appreciate outside input.
(Forgive me if I deeply offend a particular sect and/or start a
major war.)
Here are my categories, and some impressions and opinions on
each. I do not deny that some of my comments are subjective.
- Fairly explicit program counter movement via the new LOOP macro
as well as the older DO, DOTIMES, and DOLIST. Reliably
optimizable; almost always applicable; quite understandable,
particularly for programmers originally trained in other
languages; relatively low level of abstraction; new LOOP often not
vendor-supported.
- Functional recursion, via local functions if desirable. Often
not optimized (particularly non-tail recursion); almost always
applicable; verbose (for carrying out an iterative task) and often
difficult to follow; medium level of abstraction; always
vendor-supported.
- List-mapping functions such as MAPCAR and MAPLIST.
Well-optimized in better implementations; limited number of
applicable cases; highly understandable when naturally applicable;
fairly high level of abstraction; always vendor-supported.
- Sequence-mapping functions such as MAP and REMOVE-IF. Rarely
optimized; wide variety of applicable cases; quite understandable
when naturally applicable; high level of abstraction; always
vendor-supported.
- Dick Waters' SERIES package, described in CLtL/2e and the latest
issue of Lisp Pointers. Well optimized; extremely flexible;
fairly understandable though occasionally a bit verbose; high
level of abstraction; rarely vendor-supported.
I ran a simple test - adding 1 to every element of a list - on
each iteration model, on a Symbolics 3653 and XL400. All were
roughly equal in speed, except for sequence mapping, which was
slower. I was surprised that non-tail recursion, which was *not*
transformed into a direct loop, was nevertheless just as fast as
the other three that *were* transformed into direct loops.
My feeling at this time is to use list mapping when naturally
applicable, otherwise sequence mapping when naturally applicable
and not pressed for efficiency, otherwise series if
vendor-supported (maybe even if not?), otherwise LOOP. (Sorry,
recursion fans.) Any comments?
Lawrence G. Mayka
AT&T Bell Laboratories
···@ihlpf.att.com
Standard disclaimer.
From: Mark Johnson
Subject: Re: Models of iteration in ANSI Common Lisp
Date:
Message-ID: <36517@brunix.UUCP>
It's always surprised me that there aren't standard macros available
that "special-case" the list and sequence-mapping functions. Perhaps
this has been done - if so, I'd like to get a copy of these macros!
For example, most implementations create a closure for
the lambda expression in the following function.
(defun my-filter (n1 n2 numbers)
"Remove all numbers between n1 and n2 in numbers"
(remove-if #'(lambda (n) (< n1 n n2))
numbers))
But couldn't the remove-if expression be automatically expanded in cases
such as these into an iterative form, which would execute
faster?
(defun my-filter* (n1 n2 numbers)
"Remove all numbers between n1 and n2 in numbers"
(let* (current-cons result)
(dolist (n numbers result)
(if (not (< n1 n n2))
(if current-cons
(setf current-cons
(setf (cdr current-cons) (list n)))
(setf result
(setf current-cons (list n))))))))
When run on my Lisp (MACL), I get the following results:
? (defparameter *my-list* (make-sequence 'list 10000 :initial-element 3))
*MY-LIST*
? (time (my-filter 2 5 *my-list*))
(MY-FILTER 2 5 *MY-LIST*) took 82 ticks (1.367 seconds) to run.
NIL
? (time (my-filter* 2 5 *my-list*))
(MY-FILTER* 2 5 *MY-LIST*) took 22 ticks (0.367 seconds) to run.
NIL
Anyway, my point is that such expansions could be implemented by providing
macro definitions for mapping functions such as remove-if, reduce, etc.
Then these "optimizations" would be available on any CL implementation.
Mark Johnson
From: lawrence.g.mayka
Subject: Re: Models of iteration in ANSI Common Lisp
Date:
Message-ID: <15168@cbnewsc.ATT.COM>
In article <·····@brunix.UUCP> ··@cs.brown.edu (Mark Johnson) writes:
>It's always surprised me that there aren't standard macros available
>that "special-case" the list and sequence-mapping functions. Perhaps
>this has been done - if so, I'd like to get a copy of these macros!
Since all predefined Common Lisp functions (may) default to
INLINE, a CL compiler has the right to perform this special-casing
today; and indeed the better implementations optimize the list
mapping functions like MAPCAR. But the sequence mapping functions
are applicable to both lists and vectors (including strings and
bit-vectors), so their optimization would generally require either
a programmer-written type declaration or a run-time type test.
Perhaps someone can tell us whether any existing CL implementation
converts sequence-mapping functions into loops by such techniques.
Dr. Waters' SERIES package takes a slightly different tack.
Certain of its functions take a (sometimes optional) typename.
More specific types such as LIST and VECTOR aid in optimization;
type T is the most general and reusable but may result in less
efficient generated code.
>Anyway, my point is that such expansions could be implemented by providing
>macro definitions for mapping functions such as remove-if, reduce, etc.
>Then these "optimizations" would be available on any CL implementation.
ANSI Common Lisp supports programmer-written optimizations of this
kind. DEFINE-COMPILER-MACRO defines a macro expansion to be
performed only during compilation. The envisioned usage is to
define a function like REMOVE-IF with elegant semantics, then to
define a corresponding compiler macro with the same name that
looks at compilation context and optimizes the expression if
possible. One can even query the compilation environment for type
declarations via the VARIABLE-INFORMATION function.
Do we have an extensible language, or what?
Lawrence G. Mayka
AT&T Bell Laboratories
···@ihlpf.att.com
Standard disclaimer.
From: Bruce Krulwich
Subject: Macro versions of CL functions (was Re: Models of iteration ...)
Date:
Message-ID: <6524@accuvax.nwu.edu>
In article <·····@brunix.UUCP>, ··@cs (Mark Johnson) writes:
>It's always surprised me that there aren't standard macros available
>that "special-case" the list and sequence-mapping functions. Perhaps
>this has been done - if so, I'd like to get a copy of these macros!
I've done this for a few functions: MAPCAR, MAPC, SOME, EVERY, and
REMOVE-IF-NOT. As of now they all only work on lists and not on general
sequences, and I don't handle all of the REMOVE-IF-NOT keyword arguments.
I've named them all M-<original-name> for now, although as someone else has
mentioned I could use DEFINE-COMPILER-MACRO (or whatever it's called) to have
them automatically used for all compiled instances of the original functions.
In implementing them I found that they all had roughly the same structure,
which I think is the case for most list-traversing functions, so the same
approach could probably be used for other similar functions.
I did some rough time tests in Lucid CL on a SPARC, and found that MAPCAR and
MAPC already had compile-time expansion in Lucid CL. In fact, I disassembled
the results of my macro and the Lucid one and found line-for-line identical
assembly code! Other than that, I found that my versions of SOME and EVERY
ran 10 times as fast and REMOVE-IF-NOT ran 5 times as fast.
I would appreciate any comments/improvements.
Bruce Krulwich
Institute for the Learning Sciences
;;;;------------------------clip here--------------------------------
(in-package 'user)
;;; MACROS.LISP: a file of macro versions of basic functions.
;;; The macro versions eliminate closure CONSing in inner-loops.
;;; Bruce Krulwich
;;; Institute for the Learning Sciences
;;; ········@ils.nwu.edu
;;; --------------------------------------------------------------------------
;;; Utilities used here:
(defun make-a-call (proc-spec args)
(if (and (listp proc-spec) (eq (car proc-spec) 'function))
(cons (cadr proc-spec) args)
`(funcall ,proc-spec ,@args)))
;;; --------------------------------------------------------------------------
;;; Macro version of MAPCAR:
(defmacro m-mapcar (proc &rest lsts)
(let ((list-vars (mapcar #'(lambda (n)
(declare (ignore n)) (gentemp "LIST"))
(make-list (length lsts))))
(result-var (gentemp "RESULT-VAR"))
(result-acc-var (gentemp "RESULT-ACC"))
)
`(let ((,result-var (cons nil nil)))
(do ((,result-acc-var ,result-var (cdr ,result-acc-var))
,@(mapcar #'(lambda (v l) `(,v ,l (cdr ,v))) list-vars lsts))
((or ,@(mapcar #'(lambda (v) `(null ,v)) list-vars))
(cdr ,result-var))
(setf (cdr ,result-acc-var)
(cons ,(make-a-call proc (mapcar #'(lambda (v) `(car ,v))
list-vars))
nil))
))))
;;; PROB: hard to return first list (like LUCID MAPC) w/o double-evaling it
;;; (for now returns nil instead)
(defmacro m-mapc (proc &rest lsts)
(let ((list-vars (mapcar #'(lambda (n)
(declare (ignore n)) (gentemp "LIST"))
(make-list (length lsts))))
)
`(do ,(mapcar #'(lambda (v l) `(,v ,l (cdr ,v))) list-vars lsts)
((or ,@(mapcar #'(lambda (v) `(null ,v)) list-vars))
nil) ; Lucid MAPC returns 1st lst
,(make-a-call proc (mapcar #'(lambda (v) `(car ,v))
list-vars))
)))
;;; --------------------------------------------------------------------------
;;; macro version of SOME and EVERY: only work on lists, not other seq's
(defmacro m-some (pred &rest lsts)
(let ((list-vars (mapcar #'(lambda (n) (ignore n) (gentemp "LIST"))
(make-list (length lsts))))
(temp-var (gentemp "TEMP"))
)
`(do ,(mapcar #'(lambda (v l) `(,v ,l (cdr ,v))) list-vars lsts)
((or ,@(mapcar #'(lambda (v) `(null ,v)) list-vars))
nil)
(let ((,temp-var
,(make-a-call pred (mapcar #'(lambda (v) `(car ,v)) list-vars))))
(if ,temp-var (return ,temp-var))))))
(defmacro m-every (pred &rest lsts)
(let ((list-vars (mapcar #'(lambda (n) (ignore n) (gentemp "LIST"))
(make-list (length lsts))))
)
`(do ,(mapcar #'(lambda (v l) `(,v ,l (cdr ,v))) list-vars lsts)
((or ,@(mapcar #'(lambda (v) `(null ,v)) list-vars))
t)
(if (not ,(make-a-call pred (mapcar #'(lambda (v) `(car ,v)) list-vars)))
(return nil)))))
;;; --------------------------------------------------------------------------
;;; REMOVE-IF-NOT: only works on lists for now, not other types of SEQ's
(defmacro m-remove-if-not (test lst)
(let ((list-var (gentemp "LIST"))
(result-var (gentemp "RESULT-VAR"))
(result-acc-var (gentemp "RESULT-ACC"))
)
`(let ((,result-var (cons nil nil)))
(do ((,result-acc-var ,result-var)
(,list-var ,lst (cdr ,list-var)) )
((null ,list-var)
(cdr ,result-var))
(when ,(make-a-call test `((car ,list-var)))
(setf (cdr ,result-acc-var) (cons (car ,list-var) nil))
(setf ,result-acc-var (cdr ,result-acc-var)))))))
;;; --------------------------------------------------------------------------
From: Barry Margolin
Subject: Re: Macro versions of CL functions (was Re: Models of iteration ...)
Date:
Message-ID: <35744@think.Think.COM>
In article <····@accuvax.nwu.edu> ········@ils.nwu.edu (Bruce Krulwich) writes:
>Other than that, I found that my versions of SOME and EVERY
>ran 10 times as fast and REMOVE-IF-NOT ran 5 times as fast.
Of course, your version also is not generic to all sequences, and your
REMOVE-IF-NOT doesn't accept any of the keyword arguments.
I was somewhat surprized and disappointed to find that Lucid (we have
version 3.0.1) doesn't optimize calls to sequence functions when the
sequence argument is declared to be a list or simple-vector. They claim to
optimize array operations well if they are declared to be simple, but they
haven't done anything about optimizing sequence operations when the type of
the sequence is specified.
--
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar
From: Barry Margolin
Subject: Re: Models of iteration in ANSI Common Lisp
Date:
Message-ID: <35672@think.Think.COM>
In article <·····@cbnewsc.ATT.COM> ···@cbnewsc.ATT.COM (lawrence.g.mayka) writes:
> I was surprised that non-tail recursion, which was *not*
>transformed into a direct loop, was nevertheless just as fast as
>the other three that *were* transformed into direct loops.
Consider where the "expense" of recursion comes from:
1) Pushing arguments,
2) Function call and return
3) Creating new stack frames
In the case of (1), the iterative versions have to move the value into the
iteration variable, which is close to the same expense. (2) isn't much
more expensive than the jumps that must be done within the iterative
function. In the case of (3), the main expense of creating stack frames is
page faults, so if the new stack frame fits on the same page as the
previous one then there's very little expense; this means that your results
will depend on the size of the function, and your test sounds like it was
done with a tiny function.
--
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar