Copying a multidimensional array

Discussion of Common Lisp
Harleqin
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Copying a multidimensional array

Post by Harleqin » Tue Jun 16, 2009 10:22 am

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?
"Just throw more hardware at it" is the root of all evil.
Svante

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Copying a multidimensional array

Post by gugamilare » Tue Jun 16, 2009 10:50 am

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.

simon
Posts: 16
Joined: Wed May 13, 2009 9:12 am

Re: Copying a multidimensional array

Post by simon » Tue Jun 16, 2009 11:45 am

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.]
Last edited by simon on Tue Jun 16, 2009 1:25 pm, edited 1 time in total.

Harleqin
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Copying a multidimensional array

Post by Harleqin » Tue Jun 16, 2009 12:19 pm

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.
"Just throw more hardware at it" is the root of all evil.
Svante

simon
Posts: 16
Joined: Wed May 13, 2009 9:12 am

Re: Copying a multidimensional array

Post by simon » Tue Jun 16, 2009 1:02 pm

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.

Harleqin
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Copying a multidimensional array

Post by Harleqin » Tue Jun 16, 2009 1:16 pm

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)))
"Just throw more hardware at it" is the root of all evil.
Svante

Harleqin
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Copying a multidimensional array

Post by Harleqin » Tue Jun 16, 2009 2:07 pm

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))
"Just throw more hardware at it" is the root of all evil.
Svante

Harleqin
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Copying a multidimensional array

Post by Harleqin » Tue Jun 16, 2009 3:14 pm

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.
"Just throw more hardware at it" is the root of all evil.
Svante

Harleqin
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Copying a multidimensional array

Post by Harleqin » Tue Jun 16, 2009 3:39 pm

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?
"Just throw more hardware at it" is the root of all evil.
Svante

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: Copying a multidimensional array

Post by findinglisp » Wed Jun 17, 2009 9:06 am

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.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

Post Reply