Is there a 'tuple' equivalent thing in common-lisp?

Question

In my project I have a lot of coordinates to process, and in 2D situation I found that the construction of (cons x y) is faster than (list x y) and (vector x y).

However, I have no idea how to extend cons to 3D or further because I found no things like cons3. Is there any solution for a fast tuple in common-lisp?

For illustration, I made the following tests:

* (time (loop repeat 10000 do (loop repeat 10000 collect (cons (random 10) (random 10)))))

Evaluation took:
  7.729 seconds of real time
  7.576000 seconds of total run time (7.564000 user, 0.012000 system)
  [ Run times consist of 0.068 seconds GC time, and 7.508 seconds non-GC time. ]
  98.02% CPU
  22,671,859,477 processor cycles
  3,200,156,768 bytes consed

NIL
* (time (loop repeat 10000 do (loop repeat 10000 collect (list (random 10) (random 10)))))

Evaluation took:
  8.308 seconds of real time
  8.096000 seconds of total run time (8.048000 user, 0.048000 system)
  [ Run times consist of 0.212 seconds GC time, and 7.884 seconds non-GC time. ]
  97.45% CPU
  24,372,206,280 processor cycles
  4,800,161,712 bytes consed

NIL
* (time (loop repeat 10000 do (loop repeat 10000 collect (vector (random 10) (random 10)))))

Evaluation took:
  8.460 seconds of real time
  8.172000 seconds of total run time (8.096000 user, 0.076000 system)
  [ Run times consist of 0.260 seconds GC time, and 7.912 seconds non-GC time. ]
  96.60% CPU
  24,815,721,033 processor cycles
  4,800,156,944 bytes consed

NIL

Answer 1

The general way to go about such data structures is to use defstruct. This is how you create data structures in Common Lisp. So, if you wanted to have a point in three-dimensional space, this is more or less what you would do:

(defstruct point-3d x y z)

Why is this better then array:

1. It names things properly.

2. It creates a bunch of useful stuff you'd be creating anyway, such as accessors, a function to test for whether some data is of this type, a function to construct objects of this type and some other goodies.

3. Typing is more elaborate then in arrays: you can specify the type for each slot separately.

4. Specialized printing function that can print your data nicely.

Why is this better then lists:

1. You can always ask a struct to behave as a list by doing something like:

---

(defstruct (point-3d (:type list)) x y z)

• All the same stuff as arrays.

---

Optimization issues:

You should probably try to explore other alternatives. The difference between creating an array or a cons cell of equivalent memory imprint is not worth optimizing it. If you are facing a problem w/r to this particular operation, you should consider the task in general unmanageable. But really I think that techniques like object pooling, memoization and general caching should be tried first.

Another bullet point: you didn't tell the compiler to try to generate efficient code. You can tell the compiler to optimize for size, speed or debugging. You should really measure the performance after you specify what kind of optimization you are trying to pull out.

---

I've written a quick test to see what's the difference:

(defstruct point-3d
  (x 0 :type fixnum)
  (y 0 :type fixnum)
  (z 0 :type fixnum))

(defun test-struct ()
  (declare (optimize speed))
  (loop :repeat 1000000 :do
     (make-point-3d :x (random 10) :y (random 10) :y (random 10))))

(time (test-struct))

;; Evaluation took:
;;   0.061 seconds of real time
;;   0.060000 seconds of total run time (0.060000 user, 0.000000 system)
;;   98.36% CPU
;;   133,042,429 processor cycles
;;   47,988,448 bytes consed

(defun test-array ()
  (declare (optimize speed))
  (loop :repeat 1000000
     :for point :of-type (simple-array fixnum (3)) :=
     (make-array 3 :element-type 'fixnum) :do
     (setf (aref point 0) (random 10)
           (aref point 1) (random 10)
           (aref point 2) (random 10))))

(time (test-array))

;; Evaluation took:
;;   0.048 seconds of real time
;;   0.047000 seconds of total run time (0.046000 user, 0.001000 system)
;;   97.92% CPU
;;   104,386,166 processor cycles
;;   48,018,992 bytes consed

First version of my test came up biased because I forgot to run GC before the first test, so it got disadvantaged by having to reclaim memory left after the previous test. Now the numbers are more precise, and also show that there is practically no difference between using structs and arrays.

So, again, as per my previous suggestion: use object pooling, memoization, whatever other optimization technique you may think of. Optimizing here is a dead end.