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

[Thaddy]

Bart, posts crossed, have a look at my last example. (arrayfun3) and a dynamic array is always a managed type....

[Bart]

The datatype of the array is guaranteed to be NOT managed.

A dynamic array is by definition a managed type ,Bart. What do you mean?

I mean that in "array of array of TSomething", TSomething is not, nor does it contain, a managed type.
In fact, it will contain a boolean, or possibly a static array of boolean.

So, I would think that for each row move(A[r],B[r], SizeOf(TSomething)) should work, and I suspect it is faster than B[r] := Copy(A[r], Length(A[r])), because the latter will (possibly) re-allocate B[r].

Mind you, the dimension of the array wil most probaly never be greater than the dimension (in pixels) of the screen, so the difference between move() and copy() may not be of great concern to me, since the most time will be spent in the "calculate the new value of A" anyway, since this will require access to 9 "cells" in the copy I just made.

You also suggest making the array bitpacked.
I can imagine this will lower the memory footprint, but I also cam imaging this will in some degree lower the access speed to indivdual "cells"?

Bart

[Thaddy]

Bart in any case the memory representation is flat (albeit maybe pointers to strings, classes or something) whether it is a dynamic or a static array. As I explained.
The book keeping is done at negative offset, so the content is flat in all dimensions. If it s not a managed type, like a simple record, it is even fully sequential in content too. Think of it as a flat file database with fixed length records and different indices. It works like I explained..

And no: boolean operations are fast and mostly if not all CPU instructions. No speed loss there.

[Bart]

@Thaddy: I understand your explanation.

@all: My question was: "is there a more efficient way to copy than to use a nested loop and assign each cell".

This has been aswered.

Initially I hope a simple single move or copymemory would suffice, but as all of you explained, this will not do because of the nature of dynamic arrays (it would suffice fo a static one in my use case).

Thanks to all.

I have enough to get me going (testing and playing around).

@Thaddy: care to elaborate on my question about bitpacked and speed?

Bart

[howardpc]

howardpc: Copying dynamic arrays using copy() does not require separate memory allocation, neither manual calculation of element size. I don't think that would work.

Try this example of Copy on a T2DArr if you need convincing:

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

1. program CopyArray;
2.  
3. type
4.   T2DArr = array of array of Boolean;
5.  
6.   procedure ShowArray(anArray: T2DArr);
7.   var
8.     r, c: Integer;
9.   begin
10.     for r := Low(anArray) to High(anArray) do begin
11.       WriteLn;
12.       for c := Low(anArray[0]) to High(anArray[0]) do
13.         Write('(', r, ',', c, ')', anArray[r,c], ';  ');
14.     end;
15.     WriteLn;
16.   end;
17.  
18. var
19.   A, B: T2DArr;
20.   r, c: Integer;
21. const
22.   dimR = 20;
23.   dimC = 10;
24. begin
25.   SetLength(A, dimR, dimC);
26.   for r := Low(A) to High(A) do
27.     for c := Low(A[0]) to High(A[0]) do
28.       A[r, c] := Odd(r) or Odd(c);
29.   WriteLn('------------- A -------------');
30.   ShowArray(A);
31.   WriteLn;
32.  
33.   WriteLn('------------- B -------------');
34.   SetLength(B, dimR, dimC);
35.   B:=Copy(A, 0, dimR*dimC*Sizeof(Boolean));
36.   ShowArray(B);
37. end.

[jamie]

I just did a Assembler dump on how it calculates the matrix of the array..

The compiler is creating a flat memory layout however, it is creating a jump table within the
block to locate the final element. This is ok but it does make the array larger internally but that isn't
the only problem. The biggest issue is that this table is absolute which it should relative!

  You can completely move the block of memory to another one with no issues however! The jump
table now points to incorrect memory!

   Maybe there should be a compiler switch to generate the type of multi-D as you would like..

   1 . As it is now;
   2 . Using Relative jump table (movable this way)
   3 . Don't use a jump table and have the compiler generate the X,Y,Z pointer to math to go directly to it.

Oh well.

 I think maybe this would be the time for you to make a standard raw single 1D array that has no table in it and
simply make it the size you need 100x100 for example.
 Then write a function to Get or Set it.

 For what you are doing, you can use a Bitmap and use the standard Canvas.Pixel function to do the same.
 have you thought about that one ? 

[Thaddy]

Bart, any bit in a byte can be addressed with a single instruction on most CPU's. So in the case of a bitpacked array, it is not only smaller but probably faster too.
Jamie, what O level did you test? And for which platform? ARM32/64 and X86_32/64 are fully flat continuous representations on O2+ within their memory limitations.

[Nitorami]

@howardpc:

I did not know as yet that copy also works on two-dimensional arrays  .

Still, it should not be required to SetLength (B) before copying, neither multiplication by sizeof(Boolean). Copy takes the number of elements, not the number of bytes. In this example, sizeof(Boolean)= 1 and does not matter; but even if we say B := copy (A,0,10000000), it would work, because no more elements than contained in A will be copied anyway. This is different to system.move.
Altogether, a simple B := copy(A) does the trick even for multidimensional arrays. Except for Bart's case because he does not want to reallocate B.

[Bart]

The approach using system.copy on each row, seems to be as fast as system.move.
I guess no re-allocation takes place because the demension already is correct in the target?

Both methods are appr. 20 times faster than the "lazy" method with nested loops.

@Thaddy: I'll do some test on a bitpacked variant to see if access speed differs much.

Bart

[Nitorami]

The approach using system.copy on each row, seems to be as fast as system.move.

That should be expected. Only for very small data size, the management overhead may become noticeable.

I guess no re-allocation takes place because the demension already is correct in the target?

Not sure. Try writeln (ptrint(B)) before and after the copy to see whether the address has changed.

Bitpacking will reduce data size by factor 8, hence the copying will be faster. On the other hand, accessing bit packed data is a bit slower because it requires a masking and shifting operation.

[Bart]

Bitpacking is not supported for dynamic arrays 

Bart

[Nitorami]

Bitpacking is not supported for dynamic arrays

Aha. Presumably for a good reason.

On the copying: As howardpc said, copy also works for multidimensional arrays so you can use

B := copy (A);

I have tried it, and it allocates new memory, even if we SetLength(B) before. I guess we should not rely on the address of managed types.

[Thaddy]

Why the hell copy? Just Assign B:= A... unlike stated above there are no side effects, not in 3.0.4, not in trunk. The copy operation on assignment is implicit and complete.

If you *think* you need to use copy, provide an example...

[edit]
Sorry, misunderstood: yes, this is a pointer copy.

[Nitorami]

?
B := A only copies the pointer, not the content.

[howardpc]

Bitpacking is not supported for dynamic arrays 

It is not directly supported in syntax terms, but you can fake it. Whether it makes the slightest difference in performance terms I doubt.
Something like this:

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

1. program CopyArray;
2.  
3. {$ModeSwitch advancedrecords}
4.  
5. type
6.   TOneBit = 0..1;
7.  
8.   { TPackedBoolRec }
9.  
10.   TPackedBoolRec = bitpacked record
11.     b0, b1, b2, b3, b4, b5, b6, b7: TOneBit;
12.     procedure Init(a0, a1, a2, a3, a4, a5, a6, a7: Boolean);
13.     procedure Report;
14.   end;
15.  
16.   T2DArr = array of array of TPackedBoolRec;
17.  
18.   procedure ShowArray(anArray: T2DArr);
19.   var
20.     r, c: Integer;
21.   begin
22.     for r := Low(anArray) to High(anArray) do
23.     begin
24.       for c := Low(anArray[0]) to High(anArray[0]) do begin
25.         Write('(', r, ',', c, ')');
26.         anArray[r,c].Report;
27.       end;
28.     end;
29.   end;
30.  
31. var
32.   A, B: T2DArr;
33.   r, c, i: Integer;
34. const
35.   dimR = 10;
36.   dimC = 2;
37.  
38. { TPackedBoolRec }
39.  
40. procedure TPackedBoolRec.Init(a0, a1, a2, a3, a4, a5, a6, a7: Boolean);
41. begin
42.   b0:=Byte(a0); b1:=Byte(a1); b2:=Byte(a2); b3:=Byte(a3);
43.   b4:=Byte(a4); b5:=Byte(a5); b6:=Byte(a6); b7:=Byte(a7);
44. end;
45.  
46. procedure TPackedBoolRec.Report;
47. begin
48.   Write('b0 ',Boolean(b0),', b1 ',Boolean(b1),', b2 ',Boolean(b2),', b3 ',Boolean(b3),
49.         ', b4 ',Boolean(b4),', b5 ',Boolean(b5),', b6 ',Boolean(b6));
50.   WriteLn(', b7 ',Boolean(b7));
51. end;
52.  
53. begin
54.   SetLength(A, dimR, dimC);
55.   for r := Low(A) to High(A) do
56.     for c := Low(A[0]) to High(A[0]) do begin
57.       for i:=0 to 7 do
58.         case i of
59.           0: A[r, c].b0 := Byte(Odd(r) or Odd(c) and Odd(i));
60.           1: A[r, c].b1 := Byte(Odd(r) or Odd(c) or Odd(i));
61.           2: A[r, c].b2 := Byte(Odd(r) or Odd(c) and Odd(i));
62.           3: A[r, c].b3 := Byte(Odd(r) or Odd(c) or Odd(i));
63.           4: A[r, c].b4 := Byte(Odd(r) or Odd(c) and Odd(i));
64.           5: A[r, c].b5 := Byte(Odd(r) or Odd(c) or Odd(i));
65.           6: A[r, c].b6 := Byte(Odd(r) or Odd(c) and Odd(i));
66.           7: A[r, c].b7 := Byte(Odd(r) or Odd(c) or Odd(i));
67.         end;
68.     end;
69.   WriteLn('------------- A -------------');
70.   ShowArray(A);
71.   WriteLn;
72.  
73.   WriteLn('------------- B -------------');
74.   SetLength(B, dimR, dimC);
75.   B:=Copy(A); // or B:=A; if you prefer
76.   ShowArray(B);
77. end.