Re: lists.texi

[Luc Teirlinck]

Thien-Thi Nguyen wrote:

   an index of -1 returns the "oldest" element.
   so you could just `(ring-ref ring -1)' until the
   ring is exhausted, obviating both `nreverse' and
   `var' reference, while keeping the abstraction.

ring-ref does not rotate the ring, nor does it "exhaust" it.  Maybe
you mean `ring-remove', but that would force me to copy the ring first.

The abstraction involves overhead, slowing the function down by a
factor of slightly more than 2.2.  Apparently the abstraction does
more to confuse people (making them believe the algorithm is
quadratic) than to enlighten them.  The aref makes it clear that the 
algorithm is linear.

I still propose to install the function I proposed in my last message.

Here are timings for different versions, running ring-elements ten
thousand times on a ring of length 1000 on a 1.7 GHZ dual Intel Xeon:

Original "abstract" nreverse version:

(defun old-ring-elements (ring)
  "Return a list of the elements of RING in order, newest first."
  (let (lst)
    (dotimes (var (ring-length ring))
      (push (ring-ref ring var) lst))
    (nreverse lst)))

50 secomds

Avoiding nreverse, keeping "abstraction":

(defun my-ring-elements (ring)
  "Return a list of the elements of RING in order, newest first."
  (let (lst)
    (dotimes (var (ring-length ring) lst)
      (push (ring-ref ring (- -1 var)) lst))))

51 seconds.  nreverse is a primitive running a very efficient
algorithm, it makes no sense to avoid it just for efficiency reasons.

This is the function I still propose to install:

(defun ring-elements (ring)
  "Return a list of the elements of RING, in order, newest first."
  (let ((start (car ring))
        (size (ring-size ring))
        (vect (cddr ring))
        lst)
    (dotimes (var (cadr ring) lst)
      (push (aref vect (mod (+ start var) size)) lst))))

23 seconds, better by a factor of 2.2.

The following does still _slightly_ better for this test case, but at
a real price in transparency.  I believe that it performs a lot more
operations than the function I propose to install, but it runs
slightly faster, because more operations are performed inside primitives.

(defun new-ring-elements (ring)
  "Return a list of the elements of RING in order, newest first."
  (let ((lst (mapcar #'identity (cddr ring)))
        (tot (+ (car ring) (cadr ring)))
        (size (ring-size ring)))
    (if (>= size tot)
        (nreverse (nbutlast (nthcdr (car ring) lst) (- size tot)))
      (nconc (nreverse (butlast lst (- (* 2 size) tot)))
             (nreverse (nthcdr (car ring) lst))))))

20 seconds.

If one _really_ cares about efficiency, the thing to do would be to
take the function I propose to install and write it in C, but given
the fact that `ring-elements' is not even used anywhere in the Emacs
sources, this would not seem warranted.

Sincerely,

Luc.