GNU bug report logs - #7174
23.2; `last' can be made faster by using `length'

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 7174 in the body.
You can then email your comments to 7174 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>
To: bug-gnu-emacs <at> gnu.org
Subject: 23.2; `last' can be made faster by using `length'
Date: Fri, 08 Oct 2010 10:31:46 +0900

Recently I saw the implementation of `last' in subr.el and found that
it counts the number of list elements on its own:

(defun last (list &optional n)
  "Return the last link of LIST.  Its car is the last element.
If LIST is nil, return nil.
If N is non-nil, return the Nth-to-last link of LIST.
If N is bigger than the length of LIST, return LIST."
  (if n
      (let ((m 0) (p list))
	(while (consp p)
	  (setq m (1+ m) p (cdr p)))
	(if (<= n 0) p
	  (if (< n m) (nthcdr (- m n) list) list)))
    (while (consp (cdr list))
      (setq list (cdr list)))
    list))

So I modified the code to use `length' as follows, and confirmed
it becomes much faster:

(defun last (list &optional n)
  "Return the last link of LIST.  Its car is the last element.
If LIST is nil, return nil.
If N is non-nil, return the Nth-to-last link of LIST.
If N is bigger than the length of LIST, return LIST."
  (if n
      (and (> n 0)
	   (let ((m (length list)))
	     (if (< n m) (nthcdr (- m n) list) list)))
    (and list
	 (nthcdr (1- (length list)) list))))

Furthermore, the code can be made much simpler (but slower than
the above, in particular cases) as:

(defun last (list &optional n)
  "Return the last link of LIST.  Its car is the last element.
If LIST is nil, return nil.
If N is non-nil, return the Nth-to-last link of LIST.
If N is bigger than the length of LIST, return LIST."
  (nthcdr (- (length list) (or n 1)) list))

Thanks.

IRIE Shinsuke

Message #10 received at 7174-done <at> debbugs.gnu.org (full text, mbox):

From: Glenn Morris <rgm <at> gnu.org>
To: 7174-done <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Tue, 12 Oct 2010 23:30:29 -0400

Thanks; applied.

Message #13 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: Juanma Barranquero <lekktu <at> gmail.com>
To: 7174 <at> debbugs.gnu.org, rgm <at> gnu.org
Cc: 7174-done <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Thu, 14 Oct 2010 00:25:18 +0200

> Thanks; applied.

They are not equivalent:

(last '(1 . 2) 0)  => 2
(last-new '(1 . 2) 0) => nil

    Juanma

Message #17 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: Glenn Morris <rgm <at> gnu.org>
To: Juanma Barranquero <lekktu <at> gmail.com>
Cc: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>, 7174 <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Wed, 13 Oct 2010 18:48:56 -0400

Juanma Barranquero wrote:

> They are not equivalent:
>
> (last '(1 . 2) 0)  => 2
> (last-new '(1 . 2) 0) => nil

See also http://debbugs.gnu.org/cgi/bugreport.cgi?bug=7206

(defun last-new2 (list &optional n)
  "Return the last link of LIST.  Its car is the last element.
If LIST is nil, return nil.
If N is non-nil, return the Nth-to-last link of LIST.
If N is bigger than the length of LIST, return LIST."
  (if n
      (and (>= n 0)
         (let ((m (safe-length list)))
              (if (< n m) (nthcdr (- m n) list) list)))
    (and list
     (nthcdr (1- (safe-length list)) list))))


(last-new2 '(1 . 2) 0) => 2

Message #20 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: Juanma Barranquero <lekktu <at> gmail.com>
To: Glenn Morris <rgm <at> gnu.org>
Cc: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>, 7174 <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Thu, 14 Oct 2010 00:52:46 +0200

On Thu, Oct 14, 2010 at 00:48, Glenn Morris <rgm <at> gnu.org> wrote:

> See also http://debbugs.gnu.org/cgi/bugreport.cgi?bug=7206

Yes, I was seeing that same error.

> (last-new2 '(1 . 2) 0) => 2

Fine. Are you going to install it?

Thanks,

    Juanma

Message #23 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: Glenn Morris <rgm <at> gnu.org>
To: Juanma Barranquero <lekktu <at> gmail.com>
Cc: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>, 7174 <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Wed, 13 Oct 2010 18:56:37 -0400

Juanma Barranquero wrote:

> Fine. Are you going to install it?

Can't for several hours, so if you want to, feel free.

Message #26 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>
To: Juanma Barranquero <lekktu <at> gmail.com>
Cc: rgm <at> gnu.org, 7174 <at> debbugs.gnu.org, 7174-done <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Thu, 14 Oct 2010 08:00:00 +0900

Oops, sorry, I should've considered more...

IRIE Shinsuke

Message #30 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: Juanma Barranquero <lekktu <at> gmail.com>
To: Glenn Morris <rgm <at> gnu.org>
Cc: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>, 7174 <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Thu, 14 Oct 2010 01:16:25 +0200

On Thu, Oct 14, 2010 at 00:56, Glenn Morris <rgm <at> gnu.org> wrote:

> Can't for several hours, so if you want to, feel free.

Done.

Message #33 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>
To: Juanma Barranquero <lekktu <at> gmail.com>
Cc: Glenn Morris <rgm <at> gnu.org>, 7174 <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Thu, 14 Oct 2010 08:29:47 +0900

At Thu, 14 Oct 2010 01:16:25 +0200,
Juanma Barranquero wrote:
 
> Done.

Thanks.

IRIE Shinsuke

Message #36 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: Glenn Morris <rgm <at> gnu.org>
To: Juanma Barranquero <lekktu <at> gmail.com>
Cc: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>, 7174 <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Wed, 13 Oct 2010 19:29:34 -0400

Juanma Barranquero wrote:

> Done.

Cheers.

My "(>= n 0)" bit, which seems to fix your particular example from
this report, is still outstanding.

Message #39 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: Glenn Morris <rgm <at> gnu.org>
To: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>
Cc: Juanma Barranquero <lekktu <at> gmail.com>, 7174 <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Wed, 13 Oct 2010 19:30:55 -0400

IRIE Shinsuke wrote:

> Oops, sorry, I should've considered more...

No worries. However long this sat uncommitted, it was inevitable
somebody would find some issue right after it was installed.

(I assume it is still faster than the original, BTW?)

Message #42 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: Juanma Barranquero <lekktu <at> gmail.com>
To: Glenn Morris <rgm <at> gnu.org>
Cc: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>, 7174 <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Thu, 14 Oct 2010 01:44:24 +0200

On Thu, Oct 14, 2010 at 01:29, Glenn Morris <rgm <at> gnu.org> wrote:

> My "(>= n 0)" bit, which seems to fix your particular example from
> this report, is still outstanding.

Yes, an oversight, sorry. Fixed now.

    Juanma

Message #45 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: Juanma Barranquero <lekktu <at> gmail.com>
To: Glenn Morris <rgm <at> gnu.org>
Cc: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>, 7174 <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Thu, 14 Oct 2010 01:45:33 +0200

On Thu, Oct 14, 2010 at 01:30, Glenn Morris <rgm <at> gnu.org> wrote:

> No worries. However long this sat uncommitted, it was inevitable
> somebody would find some issue right after it was installed.

How true. The best way to find bugs in a patch is under fire.

> (I assume it is still faster than the original, BTW?)

That's a good question.

    Juanma

Message #48 received at 7174 <at> debbugs.gnu.org (full text, mbox):

From: IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>
To: Glenn Morris <rgm <at> gnu.org>
Cc: Juanma Barranquero <lekktu <at> gmail.com>,
	IRIE Shinsuke <irieshinsuke <at> yahoo.co.jp>, 7174 <at> debbugs.gnu.org
Subject: Re: bug#7174: 23.2; `last' can be made faster by using `length'
Date: Thu, 14 Oct 2010 13:35:41 +0900

At Wed, 13 Oct 2010 19:30:55 -0400,
Glenn Morris wrote:

> (I assume it is still faster than the original, BTW?)

I examined that.

The new `last' is still faster than the original even though it uses
`safe-length', except for particular cases as follows:

  (last nil 0)   (last '(foo) 0)   (last '(foo))

Here, '(foo) is a list of one element. In these cases, it's 2-5% slower.
If LIST has 1000 elements, 4-8 times faster.

IRIE Shinsuke

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.