Page 1 of 2

Copying a multidimensional array

PostPosted: Tue Jun 16, 2009 10:22 am
by Harleqin
As far as I have found, copying multidimensional arrays is not directly supported by the CL standard. It can be accomplished by a sort of "dimension casting" and COPY-SEQ:

Code: Select all
(defun copy-array (array)
  (make-array (array-dimensions array)
              :element-type (array-element-type array)
              :displaced-to (copy-seq (make-array (reduce #'* (array-dimensions array))
                                                  :element-type (array-element-type array)
                                                  :displaced-to array))))


Is there a better or more efficient way?

Re: Copying a multidimensional array

PostPosted: Tue Jun 16, 2009 10:50 am
by gugamilare
Doing this:

Code: Select all
:displaced-to (copy-seq (make-array ...))


Will make there to be 2 arrays in memory, the copied sequence and the array itself. I think it is better to use

Code: Select all
:initial-contents (make-array ...)


instead, or to iteratively copy the new elements using

Code: Select all
(dotimes (i (array-total-size old-array))
  (setf (row-major-aref new-array i) (row-major-aref old-array i)))


The libraries metatilities and alexandria already have this function, you can take a look at their implementation of copy-array.

Re: Copying a multidimensional array

PostPosted: Tue Jun 16, 2009 11:45 am
by simon
Something like this:
Code: Select all
(defun copy-array (a)
  (do ((b (make-array (array-dimensions a)  :element-type (array-element-type a)))
       (n 0 (1+ n)))
      ((>= n (array-total-size a)) b)
    (setf (row-major-aref b n) (row-major-aref a n))))

Avoids the double copy you are making. Also note the existence of #'array-total-size.

The reason it isnt' a built in is that there are too many possible cases (fill pointers, displaced arrays, different element types, etc.) you might want to deal with. Doing it bespoke gets that part right....


[update: in case it's not clear, I'm not suggesting the above implementation of copy-array, quite the contrary. What I'm saying is that in practice I haven't found such a function to actually be useful. There are many implementations floating around that try and do a bit better job than the above, but at the end of the day it seems to me be clearer just to write the explicit copy out, and let the compiler take advantage of what it knows.]

Re: Copying a multidimensional array

PostPosted: Tue Jun 16, 2009 12:19 pm
by Harleqin
I am not making a double copy. As far as I understood, :displaced-to makes the new array a kind of alias for the original array (or possibly a sub-array thereof). The array data are thus only copied once, through the COPY-SEQ.

Re: Copying a multidimensional array

PostPosted: Tue Jun 16, 2009 1:02 pm
by simon
Harleqin wrote:I am not making a double copy. As far as I understood, :displaced-to makes the new array a kind of alias for the original array (or possibly a sub-array thereof). The array data are thus only copied once, through the COPY-SEQ.


Sorry, I think I conflated a statement in your original and gugamilare's comment.

I'm not certain that your method will never make a transient copy, but I'd have to think about it.

At any rate, besides being non-idiomatic, here is another problem with your approach:
Code: Select all
CL-USER> (setf *print-array* nil a (make-array (list 1024 1024) :element-type '(unsigned-byte 8)))
#<(SIMPLE-ARRAY (UNSIGNED-BYTE 8) (1024 1024)) {BABE997}>
CL-USER> (copy-array a)
#<(ARRAY (UNSIGNED-BYTE 8) (1024 1024)) {A8EF037}>

Which probably really isn't really what you want...

As noted, there are lots of these floating around, but precise requirements for a given situation vary enough that you're often best off just making the three lines or so of code explicit. Particularly if you're looking to let the compiler optimize array accesses.

Re: Copying a multidimensional array

PostPosted: Tue Jun 16, 2009 1:16 pm
by Harleqin
Thanks for the pointer to alexandria. Alexandria uses an effect of ADJUST-ARRAY when applied to displaced arrays:

Code: Select all
(defun copy-array (array &key
                   (element-type (array-element-type array))
                   (fill-pointer (and (array-has-fill-pointer-p array)
                                      (fill-pointer array)))
                   (adjustable (adjustable-array-p array)))
  "Returns an undisplaced copy of ARRAY, with same fill-pointer
and adjustability (if any) as the original, unless overridden by
the keyword arguments."
  (let ((dims (array-dimensions array)))
    ;; Dictionary entry for ADJUST-ARRAY requires adjusting a
    ;; displaced array to a non-displaced one to make a copy.
    (adjust-array
     (make-array dims
                 :element-type element-type :fill-pointer fill-pointer
                 :adjustable adjustable :displaced-to array)
     dims)))

Re: Copying a multidimensional array

PostPosted: Tue Jun 16, 2009 2:07 pm
by Harleqin
simon wrote:At any rate, besides being non-idiomatic,


I find my code always very idiomatic.

here is another problem with your approach:
Code: Select all
CL-USER> (setf *print-array* nil a (make-array (list 1024 1024) :element-type '(unsigned-byte 8)))
#<(SIMPLE-ARRAY (UNSIGNED-BYTE 8) (1024 1024)) {BABE997}>
CL-USER> (copy-array a)
#<(ARRAY (UNSIGNED-BYTE 8) (1024 1024)) {A8EF037}>

Which probably really isn't really what you want...


Good observation. The new array not being a simple-array anymore can cause problems, e.g. for optimization. By the way, you can just use TYPE-OF for getting the type. The alexandria version has the same problem, though.

I also did a little benchmark (copying and timing 100000 copies of a 4x4 array), and my version seems to use 3% more space but 42% less time than the alexandria version. However, simon's version uses 40% less space AND 42% less time than mine (68% less than alexandria), so I guess that's a patch suggestion for alexandria.

I synthesized the alexandria functionality with simon's and gugamilare's suggestions:

Code: Select all
(defun copy-array (array &key
                   (element-type (array-element-type array))
                   (fill-pointer (and (array-has-fill-pointer-p array)
                                      (fill-pointer array)))
                   (adjustable (adjustable-array-p array)))
  "Returns an undisplaced copy of ARRAY, with same fill-pointer
and adjustability (if any) as the original, unless overridden by
the keyword arguments."
  (let ((copy (make-array (array-dimensions array)
                          :element-type element-type
                          :fill-pointer fill-pointer
                          :adjustable adjustable)))
    (dotimes (i (array-total-size array))
      (setf (row-major-aref copy i) (row-major-aref array i)))
    copy))

Re: Copying a multidimensional array

PostPosted: Tue Jun 16, 2009 3:14 pm
by Harleqin
Now the only thing left that is bugging me is that I don't like to loop when what I really do is map. I'd like something like MAP-INTO, just for multidimensional arrays.

Re: Copying a multidimensional array

PostPosted: Tue Jun 16, 2009 3:39 pm
by Harleqin
OK, now the metatilities version: it also uses displacement, and it also doesn't produce a simple-array. It is a bit faster than my original attempt, but much slower than my result two posts ago.

This (at least the speed and memory footprint) could be a problem with the displacement implementation. I am using SBCL 1.0.28. Can anyone do some benchmarking on other systems?

Re: Copying a multidimensional array

PostPosted: Wed Jun 17, 2009 9:06 am
by findinglisp
simon wrote:
Harleqin wrote:I am not making a double copy. As far as I understood, :displaced-to makes the new array a kind of alias for the original array (or possibly a sub-array thereof). The array data are thus only copied once, through the COPY-SEQ.


Sorry, I think I conflated a statement in your original and gugamilare's comment.

I'm not certain that your method will never make a transient copy, but I'd have to think about it.


It won't make a transient copy of the actual data, but it will create a small "displaced array object" that contains information about the displaced array and then points to the actual data in the original array. In other words, it will create a small amount of transient garbage every time the copy function is invoked, but that garbage should be small and fixed size, irrespective of the size of the array being copied.

That said, I don't typically expect copy functions to create transient garbage; I only expect the allocation of the new array. Whether that transient garbage is a problem or not depends entirely on the rate of copying. If you only call the function every now and then, it's probably not a problem. If you call it in a tight loop, you might be surprised how much you are consing. But then, you're already consing the new copy of the array, so it might not be a big deal in comparison to that. In any case, I typically try to write my code with the "principle of least surprise" in mind. IMO, copying functions should not cons. If they do, you should at least document that fact in your code so you aren't tracking it down later when it's doing something you don't expect.