union, intersection etc. cons too much with &key arguments

[hoehle@zeus.gmd.de (Jorg-Cyril Hohle)]

Hello,

I just found out that CLISP conses a lot when &REST and &KEY are used
together in a lambda list and APPLY is used on the rest list.  This
affects UNION, INTERSECTION, SUBSETP and all other set functions
defined in DEFS1.LSP when one of the :TEST, :TEST-NOT or :KEY
arguments is used and may affect user code as well.

(defun union (list1 list2 &rest rest &key test test-not key)
  (declare (ignore test test-not key))
...
         (apply #'union (cdr list1) list2 rest))


I verified that CLISP avoids consing when only &REST or &KEY are used
in a lambda list or when the rest argument is empty (nothing to cons).

> (time (intersection '(1 2 3 4 5 6 7 8 9) '(a b c d e f g h i j k l)))

Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 0 Bytes
NIL
> (time (intersection '(1 2 3 4 5 6 7 8 9) '(a b c d e f g h i j k l) :test #'eql :key #'identity))

Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 608 Bytes
NIL

The reason is that EVAL.D:apply_closure():apply_cclosure_key_withlist_:
doesn't treat the case where all &REST arguments are already in the
last argument to APPLY like it does in apply_cclosure_rest_nokey: for
functions with &REST but without &KEY or for functions with &KEY but
without &REST.

Instead of
              if (flags & bit(0)) { NEXT(ptr1) = unbound; } # Rest-Parameter
there could be a loop similar to apply_cclosure_rest_nokey: where only
<args_on_stack> values need be pushed onto <args>, constructing the &REST
list in apply_closure() and not in match_cclosure_key().

I don't know how much user code would benefit from such a change but I
know that we're using set functions with :KEY and/or :TEST a lot --
and I thought I'd optimize by using (union x y :test #'eq) instead of
just (union x y) :-(

Regards,
	Jo"rg Ho"hle.
Joerg.Hoehle@gmd.de		http://zeus.gmd.de/~hoehle/amiga-clisp.html

PS: speed doesn't seem to be affected (except for GC of course).

PPS: I wonder if there's any situation where match_cclosure_key() is
called without rest_arg set to #<unbound>?