Copying a multidimensional array

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:

(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?

Doing this:

: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

:initial-contents (make-array ...)

instead, or to iteratively copy the new elements using

(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.

Something like this:

(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.]

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.

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:

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.

Thanks for the pointer to alexandria. Alexandria uses an effect of ADJUST-ARRAY when applied to displaced arrays:

(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)))

simon wrote: At any rate, besides being non-idiomatic,

I find my code always very idiomatic.

here is another problem with your approach:

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:

(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))

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.

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?

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.

findinglisp wrote: It won't make a transient copy of the actual data, but it will create a small "displaced array object" ...

This was my initial thought as well, but without consulting the spec I didn't want to commit to "never copying". On reflection, I can't see a way this could run into trouble but I didn't stop to think about it in original comment.

In any case, using a scheme like his you can't avoid the overhead of the transient displaced array, and if you are dealing with very small simple-arrays this may be of similar size to the data, which probably isn't what you want.

This is only one reason why the repeated copying of 4x4 arrays benchmark above is a bit limited and you don't want to take much away from those results. One thing about using a standard function like adjust-array or copy-seq is that if you at least allow for the possibility of an implementation being smart about handling special cases quickly. Typically the overhead for this sort of thing is too high to be of much advantage if you are dealing with tiny matrices or whatever, but it might be a big win on some cases.

This latter is also why in practice if you actually need fast code generation with 4x4 simple-arrays or something of the like, your best bet is usually going to be to expose the copying process, then even a not-to-bright compiler should be able to optimize the array accesses.