bug#7174: 23.2; `last' can be made faster by using `length'

bug#7174: 23.2; `last' can be made faster by using `length'

[IRIE Shinsuke]

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

bug#7174: 23.2; `last' can be made faster by using `length'

[Glenn Morris]

Thanks; applied.

bug#7174: 23.2; `last' can be made faster by using `length'

[Juanma Barranquero]

> Thanks; applied.

They are not equivalent:

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

    Juanma

bug#7174: 23.2; `last' can be made faster by using `length'

[Glenn Morris]

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

bug#7174: 23.2; `last' can be made faster by using `length'

[Juanma Barranquero]

On Thu, Oct 14, 2010 at 00:48, Glenn Morris <rgm@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

bug#7174: 23.2; `last' can be made faster by using `length'

[Glenn Morris]

Juanma Barranquero wrote:

> Fine. Are you going to install it?

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

bug#7174: 23.2; `last' can be made faster by using `length'

[IRIE Shinsuke]

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

IRIE Shinsuke

bug#7174: 23.2; `last' can be made faster by using `length'

[Juanma Barranquero]

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

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

Done.

bug#7174: 23.2; `last' can be made faster by using `length'

[Glenn Morris]

Juanma Barranquero wrote:

> Done.

Cheers.

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

bug#7174: 23.2; `last' can be made faster by using `length'

[IRIE Shinsuke]

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

Thanks.

IRIE Shinsuke

bug#7174: 23.2; `last' can be made faster by using `length'

[Glenn Morris]

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?)

bug#7174: 23.2; `last' can be made faster by using `length'

[Juanma Barranquero]

On Thu, Oct 14, 2010 at 01:29, Glenn Morris <rgm@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

bug#7174: 23.2; `last' can be made faster by using `length'

[Juanma Barranquero]

On Thu, Oct 14, 2010 at 01:30, Glenn Morris <rgm@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

bug#7174: 23.2; `last' can be made faster by using `length'

[IRIE Shinsuke]

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