My algorithm uses lots of (never modified) 3 element lists of small (<
2^8) pos. integers.
Originally, I implemented these as lists. I switched to defstruct to
improve speed. Looking at the dissasembly, I see that access is quick
as can be, but that creating them still involves some expensive calls
to the generic structure creation routines.
I'd like to try implementing them as short arrays. However,
(vector 3 4 2)
creates arrays of simple-vector, which performs _much_ slower - I
assume since it doesn't know that the elements are integers.
I've tried:
(make-array 3 :element-type '(unsigned-byte 8) (vector a b c))
but that doesn't seem to work right either.
What's the right way to create these structures efficiently?
Let's simplify the question:
Is there anyway to make-array and specify all of the initial values
without having to make any intermediate data structures like lists?
On Mar 1, 1:14 pm, "S. Robert James" <············@gmail.com> wrote:
> My algorithm uses lots of (never modified) 3 element lists of small (<
> 2^8) pos. integers.
>
> Originally, I implemented these as lists. I switched to defstruct to
> improve speed. Looking at the dissasembly, I see that access is quick
> as can be, but that creating them still involves some expensive calls
> to the generic structure creation routines.
>
> I'd like to try implementing them as short arrays. However,
> (vector 3 4 2)
> creates arrays of simple-vector, which performs _much_ slower - I
> assume since it doesn't know that the elements are integers.
>
> I've tried:
> (make-array 3 :element-type '(unsigned-byte 8) (vector a b c))
> but that doesn't seem to work right either.
>
> What's the right way to create these structures efficiently?
"S. Robert James" <············@gmail.com> writes:
> Let's simplify the question:
> Is there anyway to make-array and specify all of the initial values
> without having to make any intermediate data structures like lists?
If the initial values are homogenous, you can use
:INITIAL-ELEMENT. Otherwise, no, not in the MAKE-ARRAY call. However,
(as mentioned) you could initialize it via SETF afterwards:
(defun make-triplet (a b c)
(let ((vector (make-array 3 :element-type '(unsigned-byte 8))))
(setf (aref vector 0) a
(aref vector 1) b
(aref vector 2) c)
vector))
Zach
On Mar 1, 11:52 am, Zach Beane <····@xach.com> wrote:
> "S. Robert James" <············@gmail.com> writes:
>
> > Let's simplify the question:
> > Is there anyway to make-array and specify all of the initial values
> > without having to make any intermediate data structures like lists?
>
> If the initial values are homogenous, you can use
> :INITIAL-ELEMENT. Otherwise, no, not in the MAKE-ARRAY call. However,
> (as mentioned) you could initialize it via SETF afterwards:
>
> (defun make-triplet (a b c)
> (let ((vector (make-array 3 :element-type '(unsigned-byte 8))))
> (setf (aref vector 0) a
> (aref vector 1) b
> (aref vector 2) c)
> vector))
>
> Zach
And you could create a macro for this for your own code, to clean up
your code.
(defmacro make-initialized-array (&body values)
"Make an array to hold the values specified."
(let ((num (length values))
(var (gensym)))
`(let ((,var (make-array ,num)))
(setf ,@(loop for v in values
for i from 0
append (list `(aref ,var ,i) v)))
,var)))
CL-USER> (macroexpand-1 '(make-initialized-array (:element-type
'(unsigned-byte 8)) 1 2 3))
(LET ((#:G2248 (MAKE-ARRAY 3 :ELEMENT-TYPE '(UNSIGNED-BYTE 8))))
(SETF (AREF #:G2248 0) 1 (AREF #:G2248 1) 2 (AREF #:G2248 2) 3)
#:G2248)
T
CL-USER> (make-initialized-array (:element-type '(unsigned-byte 8)) 1
2 3)
#(1 2 3)
-Harold
Oops, forgot to post my updated macro code, sorry:
(defmacro make-initialized-array (specifications &rest values)
"Make an array to hold the values specified."
(let ((num (length values))
(var (gensym)))
`(let ((,var (make-array ,num ,@specifications)))
(setf ,@(loop for v in values
for i from 0
append (list `(aref ,var ,i) v)))
,var)))
On 1 Mar 2007 14:59:21 -0800, "Harold Lee" <·······@gmail.com> said:
| Oops, forgot to post my updated macro code, sorry:
| (defmacro make-initialized-array (specifications &rest values)
| "Make an array to hold the values specified."
| (let ((num (length values))
| (var (gensym)))
| `(let ((,var (make-array ,num ,@specifications)))
| (setf ,@(loop for v in values
| for i from 0
| append (list `(aref ,var ,i) v)))
| ,var)))
Why a macro?
---Vassil.
--
mind mate, n.
One of two persons mentally compatible with each other (cf. soul mate).
On 2 Mrz., 04:58, Vassil Nikolov <···············@pobox.com> wrote:
> On 1 Mar 2007 14:59:21 -0800, "Harold Lee" <·······@gmail.com> said:
>
> | Oops, forgot to post my updated macro code, sorry:
> | (defmacro make-initialized-array (specifications &rest values)
> | "Make an array to hold the values specified."
> | (let ((num (length values))
> | (var (gensym)))
> | `(let ((,var (make-array ,num ,@specifications)))
> | (setf ,@(loop for v in values
> | for i from 0
> | append (list `(aref ,var ,i) v)))
> | ,var)))
>
> Why a macro?
If he would use a function, he would have to hold the initial values
again in some datastructure (e.g. the &rest list) at runtime. This
might be not a big problem on cl implementations which support dynamic-
extent &rest lists; it would still waste stack-space though.
ciao,
Jochen
On 2 Mar 2007 03:13:45 -0800, ···@codeartist.org" <··@codeartist.org> said:
| On 2 Mrz., 04:58, Vassil Nikolov <···············@pobox.com> wrote:
|| On 1 Mar 2007 14:59:21 -0800, "Harold Lee" <·······@gmail.com> said:
||
|| | Oops, forgot to post my updated macro code, sorry:
|| | (defmacro make-initialized-array (specifications &rest values)
|| | "Make an array to hold the values specified."
|| | (let ((num (length values))
|| | (var (gensym)))
|| | `(let ((,var (make-array ,num ,@specifications)))
|| | (setf ,@(loop for v in values
|| | for i from 0
|| | append (list `(aref ,var ,i) v)))
|| | ,var)))
||
|| Why a macro?
| If he would use a function, he would have to hold the initial values
| again in some datastructure (e.g. the &rest list) at runtime. This
| might be not a big problem on cl implementations which support dynamic-
| extent &rest lists; it would still waste stack-space though.
But with the macro, the code gets bigger (and it is less likely to
get garbage-collected).
Besides, a good compiler does not necessarily have to generate code
that conses up a list for
(make-array ... :initial-contents (list <value0> <value1> ...))
as it can open-code both MAKE-ARRAY and LIST.
---Vassil.
--
mind mate, n.
One of two persons mentally compatible with each other (cf. soul mate).
On 3 Mrz., 10:24, Vassil Nikolov <···············@pobox.com> wrote:
> But with the macro, the code gets bigger (and it is less likely to
> get garbage-collected).
>
> Besides, a good compiler does not necessarily have to generate code
> that conses up a list for
>
> (make-array ... :initial-contents (list <value0> <value1> ...))
>
> as it can open-code both MAKE-ARRAY and LIST.
If you open-code it, the code will get bigger too - there is not much
of a difference to the macro then. Another problem is, that such code
has then portability issues - on one compiler this may work efficient
on another it will be heavily consing. This may not be much of a
problem if portability between different CL compilers is not an issue
by itself. The only reason I see against using an ordinary macro is,
that one wouldn't be able to funcall it as easily as an ordinary
function. So one would actually better use a compiler macro.
ciao,
Jochen
On 3 Mar 2007 06:17:30 -0800, ···@codeartist.org" <··@codeartist.org> said:
| On 3 Mrz., 10:24, Vassil Nikolov <···············@pobox.com> wrote:
|| But with the macro, the code gets bigger (and it is less likely to
|| get garbage-collected).
||
|| Besides, a good compiler does not necessarily have to generate code
|| that conses up a list for
||
|| (make-array ... :initial-contents (list <value0> <value1> ...))
||
|| as it can open-code both MAKE-ARRAY and LIST.
| If you open-code it, the code will get bigger too - there is not much
| of a difference to the macro then.
I believe that, too, depends on the compiler, but I can see that my
point is too weak to pursue.
| Another problem is, that such code
| has then portability issues - on one compiler this may work efficient
| on another it will be heavily consing. This may not be much of a
| problem if portability between different CL compilers is not an issue
| by itself.
(And if it is, we probably want something more involved than a single
implementation of the macro...)
| The only reason I see against using an ordinary macro is,
| that one wouldn't be able to funcall it as easily as an ordinary
| function. So one would actually better use a compiler macro.
Quite, that is the right final answer.
---Vassil.
--
Is your code free of side defects?
S. Robert James wrote:
> My algorithm uses lots of (never modified) 3 element lists of small (<
> 2^8) pos. integers.
>
> Originally, I implemented these as lists. I switched to defstruct to
> improve speed. Looking at the dissasembly, I see that access is quick
> as can be, but that creating them still involves some expensive calls
> to the generic structure creation routines.
>
> I'd like to try implementing them as short arrays. However,
> (vector 3 4 2)
> creates arrays of simple-vector, which performs _much_ slower - I
> assume since it doesn't know that the elements are integers.
Why do you need a structure? Are you persisting these thee element
lists in a hash table or something? Is it possible to pass these three
values themselves around with VALUES, MULTIPLE-VALUE-BIND, and
MULTIPLE-VALUE-CALL?
Nick
"S. Robert James" <············@gmail.com> writes:
> I'd like to try implementing them as short arrays. However,
> (vector 3 4 2)
> creates arrays of simple-vector, which performs _much_ slower - I
> assume since it doesn't know that the elements are integers.
>
> I've tried:
> (make-array 3 :element-type '(unsigned-byte 8) (vector a b c))
> but that doesn't seem to work right either.
You have the syntax wrong; see
http://www.lispworks.com/documentation/HyperSpec/Body/f_mk_ar.htm
It should be something like:
(make-array 3 :element-type '(unsigned-byte 8)
:initial-contents (list a b c))
Or you could create the vector without :initial-contents and use SETF
to initialize it.
> What's the right way to create these structures efficiently?
From the "don't do it unless you /really/ have to" file, you could
pack them into an (unsigned-byte 24) with:
(logior (ash a 0) (ash b 8) (ash c 16))
From there you'd pull out the right bits with ldb or similar.
Zach
On Mar 1, 1:29 pm, Zach Beane <····@xach.com> wrote:
> It should be something like:
>
> (make-array 3 :element-type '(unsigned-byte 8)
> :initial-contents (list a b c))
>
Won't that incur a penalty in creating the list only to use it as an
argument to create an array?
"S. Robert James" <············@gmail.com> writes:
> On Mar 1, 1:29 pm, Zach Beane <····@xach.com> wrote:
> > It should be something like:
> >
> > (make-array 3 :element-type '(unsigned-byte 8)
> > :initial-contents (list a b c))
> >
> Won't that incur a penalty in creating the list only to use it as an
> argument to create an array?
Yep. It's meant more as an example of the correct syntax of make-array
than a solution to your efficiency problem.
Zach
"S. Robert James" <············@gmail.com> writes:
> On Mar 1, 1:29 pm, Zach Beane <····@xach.com> wrote:
>> It should be something like:
>>
>> (make-array 3 :element-type '(unsigned-byte 8)
>> :initial-contents (list a b c))
>>
> Won't that incur a penalty in creating the list only to use it as an
> argument to create an array?
Indeed, but you could write a reader macro, or a function to avoid the
(explicit) creation of the list.
(defun v3bytes (&rest contents)
(make-array 3 :element-type '(unsigned-byte 8)
:initial-contents contents))
(v3bytes a b c) ; instead of (vector a b c)
So here, you don't build a list explicitely, but of course, the
implementation does, for the &rest arguments.
(defparameter *rt* (copy-readtable nil))
(set-dispatch-macro-character #\# #\{
(lambda (stream subchar arg)
(declare (ignore subchar arg))
(let ((v (make-array 3 :element-type '(unsigned-byte 8)
:initial-element 0)))
(when (char= #\} (peek-char nil stream t nil t))
(error "Missing a byte"))
(setf (aref v 0) (read stream t nil t))
(when (char= #\} (peek-char nil stream t nil t))
(error "Missing a byte"))
(setf (aref v 1) (read stream t nil t))
(when (char= #\} (peek-char nil stream t nil t))
(error "Missing a byte"))
(setf (aref v 2) (read stream t nil t))
(when (char/= #\} (peek-char nil stream t nil t))
(error "Too many bytes"))
v))
*rt*)
(set-syntax-from-char #\} #\) *rt*)
(let ((*readtable* *rt*))
(read-from-string " #{1 2 3} "))
So there, when you read the vector, you store directly the bytes in
it, without building any list. But of course, make-array will first
initialize the slots to 0, so you still write twice in RAM. Only with
:initial-contents can the implementation avoid the double store.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Un chat errant
se soulage
dans le jardin d'hiver
Shiki
On 2007-03-01 18:14:45 +0000, "S. Robert James" <············@gmail.com> said:
> My algorithm uses lots of (never modified) 3 element lists of small (<
> 2^8) pos. integers.
If your fixnum size is at least 24 bits (chances are it is, but it
doesn't have to be) you can encode these in a single fixnum. Even if
your fixnums are very small (do any extant implementations still have
16-bit fixnums?) you may do well with small bignums.
--tim
In article <························@s48g2000cws.googlegroups.com>,
"S. Robert James" <············@gmail.com> wrote:
> My algorithm uses lots of (never modified) 3 element lists of small (<
> 2^8) pos. integers.
>
> Originally, I implemented these as lists. I switched to defstruct to
> improve speed. Looking at the dissasembly, I see that access is quick
> as can be, but that creating them still involves some expensive calls
> to the generic structure creation routines.
>
> I'd like to try implementing them as short arrays. However,
> (vector 3 4 2)
> creates arrays of simple-vector, which performs _much_ slower - I
> assume since it doesn't know that the elements are integers.
>
> I've tried:
> (make-array 3 :element-type '(unsigned-byte 8) (vector a b c))
> but that doesn't seem to work right either.
>
> What's the right way to create these structures efficiently?
You might also want to try the :TYPE option to DEFSTRUCT.
? (defstruct (foo (:type (vector fixnum)))
(a 0 :type fixnum)
(b 0 :type fixnum)
(c 0 :type fixnum))
FOO
? (make-foo :a 1 :b 2 :c 3)
#(1 2 3)
? (foo-b *)
2
The benefit is that DEFSTRUCT creates the accessors and you
can later simply change the underlying implementation if you need.
On Mar 1, 1:14 pm, "S. Robert James" <············@gmail.com> wrote:
> I'd like to try implementing them as short arrays. However,
> (vector 3 4 2)
> creates arrays of simple-vector, which performs _much_ slower - I
> assume since it doesn't know that the elements are integers.
If you want speed from a simple-vector, here are two (separate) things
to try.
(1) Use svref instead of aref. The "simple" in simple-vector means
that svref might be faster than aref.
(2) In make-array, try not declaring the numbers to be (unsigned-byte
8) or fixnum or anything else. The reading routine may well be faster
if it isn't checking the bit-length of each item.
And of course, (declaim (optimize speed)) at the top of the file.