Archive for October, 2007

NREVERSE vs. pointer manipulation revisted

Wednesday, October 10th, 2007

In “To NReverse When Consing a List or By Pointer Manipulation, To Avoid It; That Is the Question” (in Some Useful Lisp Algorithms: Part 2, MERL TR93-17, August, 1993), Richard C. Waters discusses whether it’s better, when consing up “a list of elements where the order of the elements in the list is the same as the order that they are created in time”, to push and nreverse or “maintain a pointer to the end of the list and use rplacd to put each element directly into its proper place in the list.” Waters’ conclusion is that nreverse is (was) often faster, but that in any case the speed difference is not enough to avoid the simpler nreverse approach.

To examine the differences Waters used two simple functions, maplist-nreverse:

(defun maplist-nreverse (f list)
  (do ((sub list (cdr sub))
       (r nil (cons (funcall f sub) r)))
      ((null sub) (nreverse r))))

and maplist-rplacd:

(defun maplist-rplacd (f list)
  (let ((r (cons nil nil)))
    (do ((sub list (cdr sub))
	 (end r (let ((x (cons (funcall f sub) nil)))
		  (rplacd end x)
	((null sub) (cdr r)))))

Timing the functions using #'identity as the map function he got the following results (Lucid Common Lisp on an HP-730):

input list length
1 10 102 103 104 105
nreverse 8.3 3.1 2.6 2.6 2.9 6.2
rplacd 8.5 3.3 2.8 2.8 3.1 6.4

(where the numbers represent computation time in microseconds per cons created).

For no real reason I replicated this on an Intel Core2 T7200 2.0GHz running Win32 and sbcl 1.0.6:

input list length
1 10 102 103 104
nreverse 0.1562 0.0469 0.0297 0.0250 0.0252
rplacd 0.1563 0.0469 0.0234 0.0227 0.0228

(where the numbers represent computation time in microseconds per element of the input list).

Although the trend seems to be for the rplacd version to be slightly faster, the differences seem minor, and we might as well adopt Waters’ recommendations:

In closing I would like to note that the very best thing to do is to avoid writing code that conses lists altogether. Whenever possible, you should use standard parts of Common Lisp that do the consing for you. In particular, you should use functions like replace, map, reduce, remove, union, etc. whenever they are appropriate. Beyond this, you should take advantage of looping macro packages such as loop and Series.