If I need to create a small structure, I can do it with a list, or a
vector, or defstruct. I wonder what is the most efficient of the
three in Common Lisp compilers -- especially for small structures.
Take this definition of binary tree:
(defstruct mytree
"My binary tree structure."
(left nil)
(right nil)
(value nil))
Now, I can easily create routines to store to tree elements, have a
SETF method for mytree-left, mytree-right, etc. But I could have
represented the tree like this:
(value . (left . right))
then (mytree-left X) would be written as (cadr X), mytree-right would
be CDDR and mytree-value would be CAR. I also could have represented
the tree as a three-elements vector:
#(value left right)
Then (mytree-left X) would be (aref X 0), etc.
Since I much prefer the `defstruct' version, I'd like to know if there
is any penalty with using a structure rather than a cons, or
especially a vector. The logical thing would be to implement them
internally as vector-lookalikes (that's what CL extensions in Emacs
do), but can I rely on such an assumption?
--
Hrvoje Niksic <·······@srce.hr> | Student at FER Zagreb, Croatia
--------------------------------+--------------------------------
Ask not for whom the <CONTROL-G> tolls.
Hrvoje Niksic <·······@srce.hr> writes:
> If I need to create a small structure, I can do it with a list, or a
> vector, or defstruct. I wonder what is the most efficient of the
> three in Common Lisp compilers -- especially for small structures.
>
> Take this definition of binary tree:
>
> (defstruct mytree
> "My binary tree structure."
> (left nil)
> (right nil)
> (value nil))
In Common Lisp you can use defstruct and defer the decision on the
implementation till later on in the development cycle. At that moment
just add a :type keyword argument to the defstruct with an argument of
vector, (vector element-type) or list.
Maurizio
Maurizio Vitale <······@esat.kuleuven.ac.be> writes:
> In Common Lisp you can use defstruct and defer the decision on the
> implementation till later on in the development cycle. At that
> moment just add a :type keyword argument to the defstruct with an
> argument of vector, (vector element-type) or list.
I know that, but I'd like to know what implementations use by default,
and which is more efficient of the three (the three being vector,
list, or default -- whatever it is).
--
Hrvoje Niksic <·······@srce.hr> | Student at FER Zagreb, Croatia
--------------------------------+--------------------------------
WWW: World-Wide-Waste. Waste management corporation, which
handles the billions of tons of garbage generated by just
about everybody these days.
In article <...> Hrvoje Niksic <·······@srce.hr> writes:
> I know that, but I'd like to know what implementations use by default,
> and which is more efficient of the three (the three being vector,
> list, or default -- whatever it is).
The efficiency can be measured along multiple dimensions, so there is
really an engineering trade-off involved.
Lists:
Storage cost is 2 words per stored element. That is because each cons
cell takes up to logical "words". You can save one if you don't
use a true list, but rather a dotted pair for the last element.
Extending the number of items is easy. It is also quick if they are
added at the front.
Inserting in the middle or deleting from the middle can be done efficiently.
Reference to an arbitrary element of the list is inefficient, since
lists are not random access, but linear access structures.
Vectors:
Storage cost is 1 word per stored element plus the vector overhead.
This can vary by implementation, but is at least one word to hold
the length information. It can easily be more if there is a need
to store type information and options. Simple-Vector is cheaper.
Extending, inserting in the middle and deleting elements (not changing
elements to NIL) are costly operations since they involve copying
the other elements.
Random access to arbitrary elements is quick
Defstruct
Automatically provides nice accessors and a few other features, such
as a separately named type. These are typically implmented using
vectors with one or more additional entries for holding the type
information and possibly a pointer to a print function. Otherwise they
work a lot like vectors. The defstruct accessor functions will compile
to very efficient code, essentially ending up as simple vector
references at high speed and low safety settings.
Conclusion:
Use lists for data structures that vary in size.
Use vectors for fixed size data structures where sequence is a
meaningful concept and where the elements are uniform
Use defstruct for fixed size data structures with heterogeneous data
components.
The uniform, non-uniform distinction isn't required by the Lisp
language, but it is a good programming practice. Although defstructs
are slightly less space efficient than vectors, the increment is usually
pretty small, and there is the advantage of having a more logical
interface to the different fields. The meaning of
(struct-id-number Foo)
is a lot clearer than
(aref Foo 3)
even when they are exactly the same.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
* Hrvoje Niksic wrote:
> I know that, but I'd like to know what implementations use by default,
> and which is more efficient of the three (the three being vector,
> list, or default -- whatever it is).
It depends on your lisp of course, but I'd assume that vectors &
structures are comparable and both faster, & smaller, than lists if
you have more than 2 elements in your structure. A cons should be
efficient for 2 element structures.
It's easy enough to test though, and you should really do that.
--tim
Hrvoje Niksic <·······@srce.hr> writes:
> I know that, but I'd like to know what implementations use by default,
> and which is more efficient of the three (the three being vector,
> list, or default -- whatever it is).
Well, I tried it with CMU Common Lisp...
---------------------- naive test code begins ----------------------
(defstruct (foo (:constructor make-foo (value left right)))
value
(left nil :type (or foo null))
(right nil :type (or foo null)))
(defun nothing-struct (x)
(if (foo-left (foo-left x)) (format t "ouch~%")))
(defun nothing-vector (x)
(if (aref (aref x 1) 1) (format t "ouch~%")))
(defun nothing-cons (x)
(if (cadr (cadr x)) (format t "ouch~%")))
(defun do-test ()
(gc)
(format t "Struct:~%")
(time
(dotimes (i 100000)
(nothing-struct (make-foo i (make-foo 0 nil nil) (make-foo 1 nil nil))))
)
(gc)
(format t "Vector:~%")
(time
(dotimes (i 100000)
(nothing-vector (vector i (vector 0 nil nil) (vector 0 nil nil))))
)
(gc)
(format t "Cons:~%")
(time
(dotimes (i 100000)
(nothing-cons (cons i (cons (cons 0 (cons nil nil))
(cons 1 (cons nil nil))))))
)
)
----------------------- naive test code ends -----------------------
Structures and vectors each took about 1.5 seconds and consed
about 7.7Mb; conses took about 1.1 seconds and consed about 5Mb.
So I conjecture that structs are implemented in much the same
way as vectors.
Doing it with a different list representation -- (list 0 nil nil) etc --
took about 1.4 seconds and consed almost exactly the same amount as the
structure and vector implementations.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.