Recent changes to add-to-list

Recent changes to add-to-list

[David Kastrup]

Hi,

recently add-to-list got an optional comparison function argument, and
Kim optimized a few general cases.

The main problem I have with this is that it incurs additional runtime
overhead even for the default case, and even though the comparison
function will be function almost always.  So I would think it more
reasonable to add separate functions, add-to-listq, add-to-listql and
add-to-list-whatever.  That is verbose on obarray, but does not impact
the general use case.

Alternatively, the optimization could be done at compile time using
macros.  But I don't know whether there might be cases where
add-to-list is required to be a function, and it seems like a bad idea
to change such a frequently used function to a macro, in particular
at the present point of time.

Then I have qualms about the implementation:

(defun add-to-list (list-var element &optional append compare-fn)
[...]
  (if (cond
       ((null compare-fn)
	(member element (symbol-value list-var)))
       ((eq compare-fn 'eq)
	(memq element (symbol-value list-var)))
       ((eq compare-fn 'eql)
	(memql element (symbol-value list-var)))
       (t
	(let (present)
	  (dolist (elt (symbol-value list-var))
	    (if (funcall compare-fn element elt)
		(setq present t)))
	  present)))

Note that this walks through the entire list even if the first
comparison already establishes the presence of a list element.  That
is very bad, since that is likely the most common use case.

It would make much more sense to do something like

     (t
       (let ((lst (symbol-value list-var)))
         (while (and lst
                     (null (funcall compare-fn element (car lst))))
             (setq lst (cdr lst)))
          lst)))

instead.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Recent changes to add-to-list

[Stefan Monnier]

> recently add-to-list got an optional comparison function argument, and
> Kim optimized a few general cases.

Wasn't this added in the time during which it was thought to be needed for
pushnew to avoid using CL at runtime?  If so, maybe it can simply be
reverted since we switched to a better implementation in the mean time, thus
removing the need for this,


        Stefan

Re: Recent changes to add-to-list

[Richard Stallman]

    The main problem I have with this is that it incurs additional runtime
    overhead even for the default case, and even though the comparison
    function will be function almost always.

It is not in a loop, so it won't take a lot of time.
I think it is insignificant.

					      So I would think it more
    reasonable to add separate functions, add-to-listq, add-to-listql and
    add-to-list-whatever.  That is verbose on obarray, but does not impact
    the general use case.

That would be really ugly.  Do you have a case where the slowdown
is really a problem?

    Note that this walks through the entire list even if the first
    comparison already establishes the presence of a list element.  That
    is very bad, since that is likely the most common use case.

That is a real slowdown.  Since you've written a fix,
would you please install it?

Re: Recent changes to add-to-list

[David Kastrup]

Richard Stallman <rms@gnu.org> writes:

>     Note that this walks through the entire list even if the first
>     comparison already establishes the presence of a list element.  That
>     is very bad, since that is likely the most common use case.
>
> That is a real slowdown.  Since you've written a fix,
> would you please install it?

I am installing it, but I would ask people who actually use the third
argument to `add-to-list' with a generic function to check this out,
as I don't have a test case.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Recent changes to add-to-list

[Nick Roberts]

 > I am installing it, but I would ask people who actually use the third
 > argument to `add-to-list' with a generic function to check this out,
 > as I don't have a test case.

I don't know if it's the third or fourth argument but COMPARE-FN isn't
described in the manual. 

-- 
Nick                                           http://www.inet.net.nz/~nickrob

Re: Recent changes to add-to-list

[Richard Stallman]

    I don't know if it's the third or fourth argument but COMPARE-FN isn't
    described in the manual. 

I will document it.

Re: Recent changes to add-to-list

[Stefan Monnier]

>     I don't know if it's the third or fourth argument but COMPARE-FN isn't
>     described in the manual. 

> I will document it.

Nobody's answered my other question, it seems: is this COMPARE-FN actually
used anywhere?
I have the impression that it was added while trying to fix the fact that
`pushnew' caused CL to be loaded at runtime.  Since then we've found another
fix (by adding memql), which should make the COMPARE-FN arg of add-to-list
unnecessary, so we should just remove it.


        Stefan

Re: Recent changes to add-to-list

[Richard Stallman]

    I have the impression that it was added while trying to fix the fact that
    `pushnew' caused CL to be loaded at runtime.  Since then we've found another
    fix (by adding memql), which should make the COMPARE-FN arg of add-to-list
    unnecessary, so we should just remove it.

Since it was implemented some time ago, there is no reason to remove it.
The feature could be useful for other cases.