Archive for the ‘history’ Category

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.

With knobs on

Friday, September 28th, 2007

Reading Sutherland’s incredible 1963 Sketchpad thesis I was struck by the following passage:

We will issue specific commands with a set of push buttons, turn functions on and off with switches, indicate position information and point to existing drawing parts with the light pen, rotate and magnify picture parts by turning knobs, and observe the drawing on the display system.

Where are my knobs and buttons? Why is the great advance of recent decades in widely available physical human-computer interaction the click-wheel mouse?

Sutherland opens his thesis by observing:

Heretofore, most interaction between men and computers has been slowed down by the need to reduce all communication to written statements that can be typed; in the past, we have been writing letters to rather than conferring with our computers.

Isn’t it time the epistolary model of interaction evolved?1,2

1. Yes, I know this seems at odds with my admiration for CLIM.

2. Yes, I am being deliberately provocative – this is the web – but I can imagine zipping through a document accepting and rejecting edits with my PS2 control being a lot more productive (and fun) than the mouse+keyboard experience.