all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
* Recent changes to add-to-list
@ 2006-10-29  9:38 David Kastrup
  2006-10-30  1:05 ` Stefan Monnier
  2006-10-30 13:33 ` Richard Stallman
  0 siblings, 2 replies; 8+ messages in thread
From: David Kastrup @ 2006-10-29  9:38 UTC (permalink / raw)



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

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Recent changes to add-to-list
  2006-10-29  9:38 Recent changes to add-to-list David Kastrup
@ 2006-10-30  1:05 ` Stefan Monnier
  2006-10-30 13:33 ` Richard Stallman
  1 sibling, 0 replies; 8+ messages in thread
From: Stefan Monnier @ 2006-10-30  1:05 UTC (permalink / raw)
  Cc: emacs-devel

> 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

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Recent changes to add-to-list
  2006-10-29  9:38 Recent changes to add-to-list David Kastrup
  2006-10-30  1:05 ` Stefan Monnier
@ 2006-10-30 13:33 ` Richard Stallman
  2006-10-30 22:48   ` David Kastrup
  1 sibling, 1 reply; 8+ messages in thread
From: Richard Stallman @ 2006-10-30 13:33 UTC (permalink / raw)
  Cc: emacs-devel

    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?

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Recent changes to add-to-list
  2006-10-30 13:33 ` Richard Stallman
@ 2006-10-30 22:48   ` David Kastrup
  2006-10-30 23:05     ` Nick Roberts
  0 siblings, 1 reply; 8+ messages in thread
From: David Kastrup @ 2006-10-30 22:48 UTC (permalink / raw)
  Cc: emacs-devel

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

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Recent changes to add-to-list
  2006-10-30 22:48   ` David Kastrup
@ 2006-10-30 23:05     ` Nick Roberts
  2006-11-01  2:13       ` Richard Stallman
  0 siblings, 1 reply; 8+ messages in thread
From: Nick Roberts @ 2006-10-30 23:05 UTC (permalink / raw)
  Cc: rms, emacs-devel

 > 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

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Recent changes to add-to-list
  2006-10-30 23:05     ` Nick Roberts
@ 2006-11-01  2:13       ` Richard Stallman
  2006-11-01 16:39         ` Stefan Monnier
  0 siblings, 1 reply; 8+ messages in thread
From: Richard Stallman @ 2006-11-01  2:13 UTC (permalink / raw)
  Cc: emacs-devel

    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.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Recent changes to add-to-list
  2006-11-01  2:13       ` Richard Stallman
@ 2006-11-01 16:39         ` Stefan Monnier
  2006-11-02  4:43           ` Richard Stallman
  0 siblings, 1 reply; 8+ messages in thread
From: Stefan Monnier @ 2006-11-01 16:39 UTC (permalink / raw)
  Cc: Nick Roberts, emacs-devel

>     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

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Recent changes to add-to-list
  2006-11-01 16:39         ` Stefan Monnier
@ 2006-11-02  4:43           ` Richard Stallman
  0 siblings, 0 replies; 8+ messages in thread
From: Richard Stallman @ 2006-11-02  4:43 UTC (permalink / raw)
  Cc: nickrob, emacs-devel

    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.

^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2006-11-02  4:43 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2006-10-29  9:38 Recent changes to add-to-list David Kastrup
2006-10-30  1:05 ` Stefan Monnier
2006-10-30 13:33 ` Richard Stallman
2006-10-30 22:48   ` David Kastrup
2006-10-30 23:05     ` Nick Roberts
2006-11-01  2:13       ` Richard Stallman
2006-11-01 16:39         ` Stefan Monnier
2006-11-02  4:43           ` Richard Stallman

Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.