Re: Adding rassq-delete-all to lisp/subr.el.

[David Kastrup <dak@gnu.org>]

Lute Kamstra <Lute.Kamstra.lists@xs4all.nl> writes:

> David Kastrup <dak@gnu.org> writes:
>
>> And I am not too fond of quadratic complexity algorithms.
>
> Me neither, but I was lazy and adapted assq-delete-all.
>
>> If one takes
>> (defun checkit ()
>>   (setq x nil)
>>   (dotimes (i 100001) (push (cons (- i) i) x))
>>   (float-time
>>    (time-since (prog1 (current-time)
>> 		 (dotimes (i 101)
>> 		   (setq x (rassq-delete-all (* 100 i) x)))))))
>>
>> The discrepancy seems pretty small after byte compilation, which seems
>> strange.
>
> delq in defined in C and it's only called 101 times.

Ah, right.  If we removed all elements piecemeal, this would be
different.

>> What makes a _significant_ difference is using (car (cdr...)) instead
>> of (cadr...): for some unfathomable reason, cadr introduces a
>> temporary binding to "x", and that is really expensive in the inner
>> loop.
>
> Strange, (cadr ...) is just a defsubst for (car (cdr ...)).  So
> compiled it should make no difference.

The defsubst binds and unbinds x.  I consider that a byte compiler
deficiency.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum