union performance bug in symbolics CL

[tk@AI.research.att.com (Thomas Kirk)]

the implementation of union in symbolics CL has a nasty performance bug.
i haven't analyzed the algorithm, but it appears that the number of 
pairwise comparisons done in this implementation of union is quadratic 
in terms of the lengths of the arguments; the length of the second argument 
is in the square term. 

ouch. this can be done with N * M comparisons.

the following demonstrates the badness:

    (defun union-lossage (n m)
      (let ((nn 0)
	    (x1 (loop for i below n collect i))
	    (x2 (loop for i from n below (+ n m) collect i)))
	(flet ((nneq (a b) (incf nn) (eq a b)))
	  (union x1 x2 :test #'nneq)
	  nn)))
    
    (union-lossage 1 1000) ==> 500500
    
    (union-lossage 1000 1) ==> 1000