Subject: [clisp-list] does LOOP cons less than MAP? [was: VECTOR-PUSH-EXTE ND]

From: "Hoehle, Joerg-Cyril" <[email-masked]>
Date: Tue Sep 10 05:20:03 2002

Randall R Schulz writes:
>A C++ programmer would call it "in-lining."
That also exists in Common Lisp: (declare (inline foo bar zot))

>[...] trade away the time cost of function invocation [...]
Randall,

you omit to mention the (to me in this case) single most important point of optimization between LOOP and MAP: the elimination of a lambda.
Given that the lambda in the given form was a closure and could not be resolved to a constant function [*], typical Lisps must allocate a closure object on the heap.

In my experience, GC/consing are sisters of time (cf. one of Paul Grahams articles). But maybe I don't have enough experience with modern generational GC.

Whereas one more indirection caused by an extra FUNCALL: I learned not to bother anymore. (Advantages outweigh non measurable performance loss).

[*] CLISP optimizes away cases where all no free variables in a lambda expression are lexically bound by an outer lexical binding. Some naive Scheme or Lisp compilers (e.g. Oaklisp) don't do this kind of useful optimization and create a new closure on each invocation [**].

E.g. with CLISP, the following two are equivalent:
(defun foo (elems list)
  (let ((helper #'(lambda (x y) (equal x (first y)))))
    (dolist (e elems nil)
      (when (funcall helper e list) (return e)))))

(let ((helper #'(lambda (x y) (equal x (first y)))))
  (defun foo2 (elems list)
    (dolist (e elems nil)
      (when (funcall helper e list) (return e)))))
I.e., the programmer can concentrate on the task at hand and need not do constant-folding him/herself, hoping for better performance.

The above functions are much more efficient than the following:
(defun bar (elems list)
  (let ((helper #'(lambda (x y) (equal x (first list)))));list comes from outer env.
    (dolist (e elems nil)
      (when (funcall helper e list) (return e)))))
which is quite similar to the original poster's (OP) MAP+lambda code.
Here a new closure object is created on every call.

One of the main differences is the following instruction:
8     (COPY-CLOSURE&PUSH 2 1)             ; #<COMPILED-CLOSURE BAR-1>
as opposed to merely referencing a constant and compiled closure/function.

Of course, compilers optimizing even further could notice that the lambda has stack semantics instead of heap semantics. It could indeed be allocated on the stack, causing no extra consing/GC. CLISP doesn't do that at all.

performance lesson: sometimes it's better to pass more parameters on to a function, so that it doesn't depend on the lexical environment.

My experience: The independent function is more general and exhibits reusable patters.

[**] creating a new closure is strictly equivalent to allocating and initializing a new object. This does not in any way require compilation. Feel free to ask for more details if this confuses you.

Regards,
	Jorg Hohle.