Copy the contents of a 2D dynamic array to another one

[han]

I put this in the wiki just a couple months ago. However, care must be taken with multi-dimensional arrays. Copying with setLength only works well for rectangular matrices.

I think the wiki should be extended with some help for 2D and 3D arrays. The copy method (bar := copy(foo, 0, length(foo)) works fine for 1D but for 2D or 2D you still need "for next" statements. While working with graphics in 3D arrayS, I see only three ways to make a real copy of an array rather then swap pointers. See below:

Code: [Select]

var
    D, C: array of array of  array of integer;
    i,j,k,width2,height2, nrcolors  : integer;
   ....
 width2:=1920;
 height2:=1080;
 nrcolors:=3;
 setlength(C,nrcolors,width2,height2);
 setlength(D,nrcolors,width2,height2);

  {clear}
  for k:=0 to nrcolors-1 do
    for i:=0 to width2-1 do
      for j:=0 to height-1 do
        C[k,i,j]:=1;

  {copy contains method 1}
    for k:=0 to nrcolors-1 do
      for i:=0 to width2-1 do
        for j:=0 to height-1 do
          D[k,i,j]:=C[k,i,j];

 {copy contains method 2}
   for k:=0 to nrcolors-1 do
     for i:=0 to width2-1 do
        D[k,i]:=copy(C[k,i],0,height2);

  {copy contains method 3}
    D:=C;{copy pointer}
    setlength(D,nrcolors,width2,height2);{make real duplicate}


Please tell me if there are more or better ways and lets document them in the wiki.

[BobDog]

After messing around I got:

Code: Pascal  [Select][+][-]

1.    program tester;
2.  
3.  
4.  type
5.   T2D = array of array of integer;
6.  
7.   var
8.    A,B:T2D;
9.    i,j:integer;
10.    rows:integer;
11.    cols:integer;
12.  
13.  
14. procedure show(ar:T2d;r:integer;c:integer;msg:ansistring);
15.  var x,y,L:integer;
16.  sa:ansistring;
17.  pad:ansistring;
18.  begin
19.  pad:='     ';
20.  writeln(msg);
21.   for x:=0 to r-1 do
22.  begin
23.  for y:=0 to c-1 do
24.  begin
25.  str(ar[x,y],sa);
26.  L:=5-length(sa);
27.  setlength(pad,L);
28.  write(sa,pad);
29.  end;
30.  writeln;
31.  end;
32.  writeln;
33.  end;   {show}
34.  
35.   procedure transfer(src:T2D;var dest:T2D;row:integer;col:integer);
36.  begin
37.  dest:=src;
38.  setlength(dest,row,col);
39.  end;  {transfer}
40.  
41.  
42.  begin
43.  
44.  rows:=20; // change to test   at least 2 or greater
45.  cols:=10;  // change to test           ""
46.  
47.  setlength(A,rows,cols);
48.  
49.   for i:=0 to rows-1 do
50.  begin
51.  for j:=0 to cols-1 do
52.  begin
53.  A[i,j]:=i+j;  {fill up A}
54.  end;
55.  end;
56.  
57.  show(A,rows,cols,' array A ');
58.  
59.  
60.  transfer(A,B,rows,cols);
61.  
62.  show(B,rows,cols,' array B (copied)');
63.  
64.  // change a value in A
65.  writeln( 'change a value in A');
66.    A[2,2]:=-88;
67.   writeln('A[2,2] = ',A[2,2]);
68.   writeln('B[2,2] = ',B[2,2],'  (remains unchanged)');
69.    writeln;
70.   show(A,rows,cols,' A again ' );
71.    show(B,rows,cols,' B again ' );
72.    writeln('press return to end');
73.   readln
74.  end.
75.  
76.  
77.    

(Just a learner)
basically let a raw new array:= the old, then setlength(the raw array,to (in this case the old array dimensions))
Using Dev-pas ide.
tested 64 bits 3.04 version

[jamie]

No, User137 understood it correctly: a dynamic array of dynamic arrays is essentially an array of Pointers. Each of these pointers points to another dynamic array which all can have different lengths. The compiler has absolutely no knowledge about the memory layout. One of those sub elements could reside at the start of the heap, another at the end, a third somewhere in between. This is by design.
If you want a consecutive memory layout for multi dimensional arrays use a static array or write your own type that handles that based on a single junk of memory plus array properties for access.

@Pascal:

 The compiler is at fault by building the array with the structure that it has, which has been my point all along...

 All you need is the base pointer of the bulk to the array, and instead of using Pointers to the elements you use offsets to the
elements.

 The compiler needs to generate code to get the offset and add the base if one is to ask for the pointer but if one want to do a
bulk overwrite with another, then basic memory function of a MemMove will do it.

 That is my point!
   OFFSETS, not pointers..
 When I say OFFSETS, I am talking about replacing the sub pointers with OFFSETS....

[lucamar]

The problem, Jamie, is that you can do this:

Code: Pascal  [Select][+][-]

1. var
2.   MyArray: array of array of char;
3.  
4. begin
5.   SetLength(MyArray, 3);
6.   SetLength(MyArray[0], 4);
7.   SetLength(MyArray[1], 3);
8.   SetLength(MyArray[2], 7);
9.   {
10.     Do complex things with the array,
11.     and after them ...
12.   }
13.   SetLength(MyArray[1], 256);
14.   {
15.     Keep going ...
16.   }
17. end;

With the actual code line 13 needs basically to get a new block, copy the old MyArray[1] over and free the old memory. Using offsets and contiguous memory would mean moving almost the whole array and recalculating almost all offsets.

The example is trivial but imagine, say, a simple line editor with thousands of lines and megabytes of text where that operation must be repeated over and over.

[User137]

In the "Do complex things with the array, and after them ..." part you can even initialize new arrays which in the memory may be placed in the middle of MyArray.

But here's a treat, class for dealing with rectangular 2D array using only 1D one. It should be faster in most operations than array of array of SomeType. Simple Lazarus GUI application with TButton and TEdit:

Code: Pascal  [Select][+][-]

1. unit Unit1;
2.  
3. {$mode objfpc}{$H+}
4.  
5. interface
6.  
7. uses Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls, Math;
8.  
9. type
10.  
11.   { T2DIntArray }
12.  
13.   T2DIntArray = class
14.   private
15.     FArray: array of integer;
16.     FRows, FCols: integer;
17.     function GetData(row, col: integer): integer;
18.     procedure SetData(row, col: integer; value: integer);
19.   public
20.     constructor Create(_cols, _rows: integer);
21.     property Ints[col, row: integer]: integer read GetData write SetData; default;
22.     property Cols: integer read FCols;
23.     property Rows: integer read FRows;
24.     procedure Resize(newCols, newRows: integer);
25.   end;
26.  
27.   { TForm1 }
28.  
29.   TForm1 = class(TForm)
30.     btnTest: TButton;
31.     Edit1: TEdit;
32.     procedure btnTestClick(Sender: TObject);
33.   private
34.  
35.   public
36.  
37.   end;
38.  
39. var Form1: TForm1;
40.  
41. implementation
42.  
43. {$R *.lfm}
44.  
45. { TForm1 }
46.  
47. procedure TForm1.btnTestClick(Sender: TObject);
48. var a1: T2DIntArray;
49.     s: string;
50. begin
51.   a1:=T2DIntArray.Create(10, 20);
52.   // Set some values
53.   a1[2, 2]:=2;
54.   a1[3, 3]:=3;
55.   s:=format('old(%d, %d)',[a1[2, 2], a1[3, 3]]);
56.   // Rescale the array
57.   a1.Resize(14, 18);
58.   s:=s+format(' new(%d, %d)',[a1[2, 2], a1[3, 3]]);
59.   a1.Free;
60.   // Results
61.   edit1.Text:=s; // Prints out: old(2, 3) new(2, 3)
62. end;
63.  
64. { T2DIntArray }
65.  
66. constructor T2DIntArray.Create(_cols, _rows: integer);
67. begin
68.   FCols:=_cols;
69.   FRows:=_rows;
70.   setlength(FArray, FCols*FRows);
71. end;
72.  
73. function T2DIntArray.GetData(row, col: integer): integer;
74. begin
75.   result:=FArray[col+row*FCols];
76. end;
77.  
78. procedure T2DIntArray.SetData(row, col: integer; value: integer);
79. begin
80.   FArray[col+row*FCols]:=value;
81. end;
82.  
83. procedure T2DIntArray.Resize(newCols, newRows: integer);
84. var A2: array of integer;
85.     i, j, index: integer;
86. begin
87.   setlength(A2, NewCols*NewRows);
88.   for j:=0 to min(NewRows, FRows)-1 do begin
89.     index:=j*NewCols;
90.     for i:=0 to min(NewCols, FCols)-1 do begin
91.       A2[index]:=Ints[j, i];
92.       inc(index);
93.     end;
94.   end;
95.   FArray:=A2;
96.   FCols:=NewCols;
97.   FRows:=NewRows;
98. end;
99.  
100. end.

Now, you can generalize the array so it can be defined for any type if you look for clues here at least:
https://stackoverflow.com/questions/37603003/index-operator-property-on-2d-array-in-delphi
But i don't know if there might be differences in FPC and Delphi regards that so it didn't compile when i tried.

Oh, i forgot rangechecking in GetData and SetData. I didn't think they'd be necessary but for Resize() absolutely needed.

edit: Those min() from math library should be good enough to fix rangechecking for Resize, without needing to reduce performance of Get/SetData.

[PascalDragon]

No, User137 understood it correctly: a dynamic array of dynamic arrays is essentially an array of Pointers. Each of these pointers points to another dynamic array which all can have different lengths. The compiler has absolutely no knowledge about the memory layout. One of those sub elements could reside at the start of the heap, another at the end, a third somewhere in between. This is by design.
If you want a consecutive memory layout for multi dimensional arrays use a static array or write your own type that handles that based on a single junk of memory plus array properties for access.

@Pascal:

 The compiler is at fault by building the array with the structure that it has, which has been my point all along...

The compiler is not at fault, because this is by design. That's how dynamic arrays work, because dynamic arrays are not simply a flat memory space, but a pointer to a flat memory space, so a dynamic array of dynamic arrays can not be a flat memory.

[Mr.Madguy]

Simple thing. Array - is simple type. Therefore I don't think, that it's good idea to overcomplicate it by some obscure and implicit behavior. Pascal is compiler, not script language. Some thing are intentionally designed to be done manually, so programmer would have more control over them. If one needs more complex behavior, then may be it's better to use lists or other custom objects?

[han]

In my graphic program 3D arrays manipulations are everywhere. This is normally done with for-next loops since the data has to be manipulated. Just duplicating an array is rare and mainly for backup/restore of a graphic. Nevertheless speed is important and I did some speed test for a 3x1920x1080 array of single:

1000 repeats:
Method 1 (for-do): 19 seconds
Method 2 (for-do +copy): 5 seconds
Method 3 (setlength): 29 seconds
Method 4 (1D array): 8 seconds

My conclusion is that method 2 is the best method. Using setlength is a disappointing slow process. Method 1 is required for array/graphic manipulations.

For method 4 you have to add later multiplications to access the data correctly which will slow down it significantly  e.g.:

Code: [Select]

  for k:=0 to nrcolors-1 do
    for i:=0 to width2-1 do
       for j:=0 to height-1 do
          F[k+nrcolors*i+nrcolors*width2*j]:=E[k+nrcolors*i+nrcolors*width2*j];
The 4 methods:

Code: [Select]

{copy contains method 1}
    for k:=0 to nrcolors-1 do
      for i:=0 to width2-1 do
        for j:=0 to height-1 do
          D[k,i,j]:=C[k,i,j];

 {copy contains method 2}
   for k:=0 to nrcolors-1 do
     for i:=0 to width2-1 do
        D[k,i]:=copy(C[k,i],0,height2);

  {copy contains method 3}
    D:=C;{copy pointer}
    setlength(D,nrcolors,width2,height2);{make real duplicate}

  {copy contains method 4}
   for k:=0 to (nrcolors-1)*(width2-1)*(height2-1) do
     F[k]:=E[k];



[han]

Simple thing. Array - is simple type. Therefore I don't think, that it's good idea to overcomplicate it by some obscure and implicit behavior. Pascal is compiler, not script language. Some thing are intentionally designed to be done manually, so programmer would have more control over them. If one needs more complex behavior, then may be it's better to use lists or other custom objects?

Yes simplicity results often in speedy execution. For my application (stacking of astronomical images) speed is important and I have to stack hundreds of images, calculating the mean, standard deviation of the values for each calculation pixel position.  Arrays are ideal for that. Nevertheless I have now learned:

- Using copy for the 1D part of a 3D array makes it faster.
- Setlength for making an array copy is terrible slow, you better use a "for do" loop.

[User137]

Code: [Select]

  for k:=0 to nrcolors-1 do
    for i:=0 to width2-1 do
       for j:=0 to height-1 do
          F[k+nrcolors*i+nrcolors*width2*j]:=E[k+nrcolors*i+nrcolors*width2*j];


If it's about cloning the array, new size is same as old size then it can be done simpler (because that is 1 continuous "3-dimensional" memory block):

Code: [Select]

F:=copy(E[0], 0, nrcolors*width2*height); // might need the [0] index for dynamic array

[han]

Code: [Select]

  for k:=0 to nrcolors-1 do
    for i:=0 to width2-1 do
       for j:=0 to height2-1 do
          F[k+nrcolors*i+nrcolors*width2*j]:=E[k+nrcolors*i+nrcolors*width2*j];


If it's about cloning the array, new size is same as old size then it can be done simpler (because that is 1 continuous "3-dimensional" memory block):

Code: [Select]

F:=copy(E, 0, nrcolors*width2*height2);

That should be faster. My code above was an illustration how to manipulate/access the 3D data in a 1D array rather then copying. E.g multiplying the values with a factor 2.

Let's call this variation method 5. I have compared it with method 4 (for-do + 1D array)  Method 5 takes about 5 seconds if repeated 1000 times. Method 4 takes 8 seconds.

Method 4: 8 seconds
Method 5: 5 seconds

Code: [Select]

  {copy contains method 4}
   for k:=0 to (nrcolors-1)*(width2-1)*(height-1) do
     F[k]:=E[k];
 
  {copy contains method 5}
   F:=copy(E,0,(nrcolors-1)*(width2-1)*(height-1));

Still I think method 2 (for-do + copy) is the best unless you have to setlength anyhow. Then you probably would use method 3 (D:=C + setlength(D,...))

[Mr.Madguy]

Yes simplicity results often in speedy execution. For my application (stacking of astronomical images) speed is important and I have to stack hundreds of images, calculating the mean, standard deviation of the values for each calculation pixel position.  Arrays are ideal for that. Nevertheless I have now learned:

- Using copy for the 1D part of a 3D array makes it faster.
- Setlength for making an array copy is terrible slow, you better use a "for do" loop.

Essential part of programmers' philosophy is "Do it once - use it till the end of your life". If you need some special tool for your task, that would make your life easier - just make one. For example don't use dynamic arrays at all. You may construct any possible data structure by yourself with any possible functionality - via making new class. How about allocation of X*Y*Z*SizeOf(Data) 1D array and accessing it via class property?

Something like this:

Code: Pascal  [Select][+][-]

1. TData = array[0..0] of TItem;
2. PData = ^TData;
3.  
4. TMyData = class
5.   protected
6.     FData:PData;
7.     FLengthX, FLengthY, FLengthY:Integer;
8.     procedure SetData(AX, AY, AZ:Integer;AData:TItem);
9.     function GetData(AX, AY, AX:Integer):TItem;
10.   public
11.     constructor Create(ALenghtX, ALengthY, ALengthZ:Integer);
12.     destructor Destroy;override;
13.     property Data[AX, AY, AZ:Integer]:TItem read GetData write SetData;
14.     function Copy:TMyData;
15. end;
16.  
17. constructor TMyData.Create(ALenghtX, ALengthY, ALengthZ:Integer);
18. begin
19.   FLengthX := ALengthX;
20.   FLengthY := ALengthY;
21.   FLengthZ := ALengthZ;
22.   FData := GetMem(FLengthX * FLengthY * FLengthY * SizeOf(TItem));
23. end;
24.  
25. destructor TMyData.Destroy;
26. begin
27.   FreeMem(FData);
28. end;
29.  
30. procedure TMyData.SetData(AX, AY, AZ:Integer;AData:TItem);
31. begin
32.   //Check ranges here
33.   FData^[((AZ * FLengthY) + AY) * FLengthX) + AX] := AData;
34. end;
35.  
36. function TMyData.GetData(AX, AY, AZ:Integer):TItem;
37. begin
38.   //Check ranges here
39.   Result := FData^[((AZ * FLengthY) + AY) * FLengthX) + AX];
40. end;
41.  
42. function TMyData.Copy:TMyData;
43. begin
44.   Result := TMyData.Create(FLengthX, FLengthY, FLengthY);
45.   Move(FData^[0], Result.FData^[0], FLengthX * FLengthY * FLengthY * SizeOf(TItem));
46. end;
47.  

[han]

I have attached a speed test program for all 5 methods. Results:

1000 repeats:
Method 1 (for-do 3D array): 19 seconds
Method 2 (for-do 2D array+copy 1D array): 5 seconds
Method 3 (B:=A; setlength 3D array): 29 seconds
Method 4 (for-do 1D array): 9 seconds
Method 5 (copy 1D array): 5 seconds

So method 2  (for-do 2D array+copy 1D array) is for me the winner. Speed is more or less equal to method 5  (copy 1D array) since most data is copied using system.copy and it allows working with an 3D array. I will update test times in my previous posts.

If you have to define the array size anyhow, you could use method 3, B:=A; setlength(B,...);

Code: [Select]

{copy contains method 2}
   for k:=0 to nrcolors-1 do
     for i:=0 to width2-1 do
        D[k,i]:=copy(C[k,i],0,height2);


Update
The test program is updated. See:
https://forum.lazarus.freepascal.org/index.php/topic,39739.msg491301.html#msg491301

[han]

Essential part of programmers' philosophy is "Do it once - use it till the end of your life". If you need some special tool for your task, that would make your life easier - just make one. For example don't use dynamic arrays at all. You may construct any possible data structure by yourself with any possible functionality - via making new class. How about allocation of X*Y*Z*SizeOf(Data) 1D array and accessing it via class property?

Constructing a dedicated data structure is an option. But that will result in a large change in code. I have to test if it will result in an increased execution speed. Maybe it has also an effect on debugging and range and overflow checking.

[Mr.Madguy]

Constructing a dedicated data structure is an option. But that will result in a large change in code. I have to test if it will result in an increased execution speed. Maybe it has also an effect on debugging and range and overflow checking.

You can also use interface instead of class so it would be reference counted. Interfaces support properties too (at least in Delphi). And I've forgotten about marking Data property as default:

Code: Pascal  [Select][+][-]

1.     property Data[AX, AY, AZ:Integer]:TItem read GetData write SetData;default;
2.  

In this case object behaves exactly like array, i.e. no code changes are needed.

For example:

Code: Pascal  [Select][+][-]

1. X, Y:T3DDynArray;
2.  
3. SetLength(X, 10, 10, 10);
4.  
5. X[0, 0, 0] := 0.1;
6.  
7. Y := X;
8.  
9. SetLength(Y, 10, 10, 10);
10.  

changes into:

Code: Pascal  [Select][+][-]

1. X, Y:I3DArray;
2.  
3. X := T3DArray.Create(10, 10, 10);
4.  
5. X[0, 0, 0] := 0.1;
6.  
7. Y := X.Copy;
8.  

P.S. Dunno about FPC, but Delphi doesn't support := operator overloading, like C++ does. And no overloading for classes is supported - you're expected to use class methods instead. In case of C++ you would be able to overload := and turn Y := X.Copy into Y := X.