[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Adding rassq-delete-all to lisp/subr.el.
From: |
David Kastrup |
Subject: |
Re: Adding rassq-delete-all to lisp/subr.el. |
Date: |
Tue, 19 Apr 2005 18:39:06 +0200 |
User-agent: |
Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux) |
Lute Kamstra <address@hidden> writes:
> David Kastrup <address@hidden> 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