remove

[haltraet@monsun.si.no (Hallvard Tr{tteberg)]

Hi, I'm profiling some code and found out that it's consing much more
than it should. I found that the following is true of MCL 2.0:

(let ((a '(1 2 3))) (eq    a (remove 0 a))) => nil, while of course
(let ((a '(1 2 3))) (equal a (remove 0 a))) => t

Remove conses up a new list even though it doesn't remove anything!
It shouldn't be difficult to write one that kept the biggest unchanged
tail of the original list, returning the whole unmodified list if it
didn't contain the first argument. It only requires an eq-test on the
result from a recursive call:

(defun faster-remove (elt list)
  (if (atom list)
    (values list)
    (let* ((cons (cdr list))
           (cons-result (faster-remove elt (cdr list))))
      (if (eq (car list) elt)
        (values cons-result)
        (if (eq cons cons-result)
          (values list)
          (cons (car list) cons-result))))))

Time-ing shows a big difference:

(DOTIMES (A 1000) (DOTIMES (B 8) (FASTER-REMOVE B '(1 2 3 4 5 1 2 3 4
5)))) took 2421 milliseconds (2.421 seconds) to run.
Of that, 117 milliseconds (0.117 seconds) were spent in The
Cooperative Multitasking Experience.
 240000 bytes of memory allocated.
NIL
? 
(DOTIMES (A 1000) (DOTIMES (B 8) (REMOVE B '(1 2 3 4 5 1 2 3 4 5))))
took 6966 milliseconds (6.966 seconds) to run.
Of that, 376 milliseconds (0.376 seconds) were spent in The
Cooperative Multitasking Experience.
 640000 bytes of memory allocated.
NIL

I know my function isn't as general as remove since it only works on
lists and doesn't take all those arguments. But I feel remove should
be optimized for the simplest cases and also should try to cons as
little as possible. As the results show, faster-remove (or should it
be called low-consing-remove) is far better when it comes to consing.

--
Hallvard Traetteberg
Dept. of Knowledge Based Systems
Center for Industrial Research
Box 124 Blindern, 0314 Oslo 3
NORWAY

Tlf: +47 2 45 29 83 or  +47 2 45 20 10
Fax: +47 2 45 20 40
Email: Hallvard.Tretteberg@si.no