### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: Reverse order of an array  (Read 15292 times)

#### BrunoK

• Sr. Member
• Posts: 446
• Retired programmer
##### Re: Reverse order of an array
« Reply #30 on: March 26, 2018, 12:08:36 pm »
Quote
-O1
Comparison with array length=20000, iterations=10000
RevSimple 0.41s  RevPtr 0.31s   RevPtr2 0.33s
Comparison with array length=20000, iterations=100000
RevSimple 4.08s  RevPtr 3.16s   RevPtr2 3.14s
Comparison with array length=200000, iterations=10000
RevSimple 4.11s  RevPtr 3.20s   RevPtr2 3.17s
Comparison with array length=200000, iterations=100000
RevSimple 41.32s  RevPtr 32.06s   RevPtr2 31.82s
Quote
-O1 -OoREGVAR
Comparison with array length=20000, iterations=10000
RevSimple 0.30s  RevPtr 0.19s   RevPtr2 0.19s
Comparison with array length=20000, iterations=100000
RevSimple 3.00s  RevPtr 1.86s   RevPtr2 1.86s
Comparison with array length=200000, iterations=10000
RevSimple 3.06s  RevPtr 1.91s   RevPtr2 1.92s
Comparison with array length=200000, iterations=100000
RevSimple 30.64s  RevPtr 19.16s   RevPtr2 19.24s
-----> RevSimple 37% more time than pointers
Quote
-O4 -OoREGVAR
Comparison with array length=20000, iterations=10000
RevSimple 0.22s  RevPtr 0.19s   RevPtr2 0.19s
Comparison with array length=20000, iterations=100000
RevSimple 2.20s  RevPtr 1.84s   RevPtr2 1.81s
Comparison with array length=200000, iterations=10000
RevSimple 2.25s  RevPtr 1.94s   RevPtr2 1.91s
Comparison with array length=200000, iterations=100000
RevSimple 22.17s  RevPtr 19.36s   RevPtr2 19.36s
-----> RevSimple 14% more time than pointers

Using howardpc code, I get similar timings for engkin, taazz or my submission within <2%.

I get ratio for RevSimple / RevPtr nearly the same as tazz. I dont understand how howardpc gets such different timings.

-O1 RevSimple takes > 30% time more than any of our RevPtr routines.
-O1 -OoREGVAR is roughly 30% faster than -O1 for both code.
No real change from -O1 to -O3 included.

It is only at -O4 that the ratio falls down to a bit more than 10%.

Thus for debuggable code the approach to say 60 bytes will be 30% faster than 96 bytes is a reasonable approach.

#### domasz

• Sr. Member
• Posts: 275
##### Re: Reverse order of an array
« Reply #31 on: June 09, 2023, 09:23:23 pm »
Also note that theoretically and technically you should not physically "reverse" an array: it makes no sense and is a waste of time. The language supports both top to bottom and bottom to top traversals.
(If you worked for me.. reason to get fired). But you ask good questions. Keep up the efforts.

Lets say I have rows of pixels stored as arrays. Now I want to mirror the image. So I can just do:

Quote
for y:=0 to Bmp.Height-1 do begin
Row[y] := Reverse(Row[y]);
end;

Reason to git fired?

#### jamie

• Hero Member
• Posts: 5691
##### Re: Reverse order of an array
« Reply #32 on: June 09, 2023, 10:55:39 pm »
you can use the copyRect and flip the X.Left. X.Right in either the source or destination onto itself.
The only true wisdom is knowing you know nothing

• Hero Member
• Posts: 13209
##### Re: Reverse order of an array
« Reply #33 on: June 10, 2023, 01:17:41 pm »
the idea behind my remark above is that the array is in place and in memory and does not need any intermediate copying:
1 iterator from low to high
1 iterator from high to low, you can output that to a new image if that is more convenient.
This flips the image and mirrors without extensive copying.

Maybe now you understand that such an approach makes a lot of sense.
« Last Edit: June 10, 2023, 01:22:56 pm by Thaddy »
I actually get compliments for being rude... (well, Dutch, but that is the same)

#### jamie

• Hero Member
• Posts: 5691
##### Re: Reverse order of an array
« Reply #34 on: June 11, 2023, 02:44:25 am »
reversing a list of doubles can be done with a simple ASM routine in 64 bit mode using nothing but registers once in the loop.

I suppose you could also rid the stack and use the registers that are passed, if you want to save a fraction of a nano second.

It could be done simply in 32 bit mode with register pairs, too.
The only true wisdom is knowing you know nothing

#### jamie

• Hero Member
• Posts: 5691
##### Re: Reverse order of an array
« Reply #35 on: June 11, 2023, 09:43:32 pm »
Here is something that I just put together as a concept of using a register code loop only to reverse the doubles.
Code: Pascal  [Select][+][-]
1. Procedure ReverseDoubleArray(P:Pointer; aCount:Integer);
2. Label Redo,Done;
3. Begin
4. ASm
5.  Mov aCount, %RCX;
6.  Subq \$1, %RCX;
7.  Jc  Done;
8.  ROL \$3, %RCX;
9.  Mov P, %RSI;
10.  Mov %RSI,%RDI
12. Redo:
13.  Mov (%RSI),%RCX;
14.  xchg (%RDI), %RCX;
15.  Mov %RCX, (%RSI);
17.  Subq \$8, %RDI;
18.  Cmp %RSI, %RDI;
19.  JA Redo;
20. Done:
21. End ['RSI','RDI','RCX'];
22. end;
23.
24. procedure TForm1.Button1Click(Sender: TObject);
25. Var
26.   F:Array[0..4] of Double=(1,2,3,4,5);
27. begin
28.   ReverseDoubleArray(@F,5);
29.   Caption := F[0].Tostring+F[1].Tostring+F[2].Tostring+F[3].Tostring+F[4].Tostring;
30. end;
31.
32.

I am sure there are better ASM instructions to use but this was the simplest for me atm using 64 bit.
The only true wisdom is knowing you know nothing

#### runewalsh

• Jr. Member
• Posts: 53
##### Re: Reverse order of an array
« Reply #36 on: June 11, 2023, 11:24:45 pm »
Man, XCHG mem, reg is a terrible idea, this instruction is implicitly atomic with a memory operand (unlike exchanging two registers).

Code: Pascal  [Select][+][-]
1. {\$asmmode intel}
2. procedure RevSSE2(var A: TDoubleDynArray); assembler; nostackframe;
3. const
4.         Shufpd_ReverseDoublesInXMM = %01;
5. asm
6.         mov    A, qword ptr [A]
7.         test   A, A // A = nil?
8.         jz     @Done
9.         mov    r8, qword ptr [A - 8] // r8 = High(A)
10.         lea    r8, [A + 8 * r8 - 8] // r8 = A + length(A) - 2 doubles = right ptr
11.
12.         cmp    A, r8
13.         ja     @LastItem // no full vectors
14. @2xLoop:
15.         movupd xmm0, [A]
16.         shufpd xmm0, xmm0, Shufpd_ReverseDoublesInXMM
17.         movupd xmm1, [r8]
18.         shufpd xmm1, xmm1, Shufpd_ReverseDoublesInXMM
19.         movupd [A], xmm1
20.         movupd [r8], xmm0
22.         sub    r8, 16
23.         cmp    A, r8
24.         jbe    @2xLoop
25. @LastItem:
26.         add    r8, 8 // was −2 doubles, change to −1 double
27.         cmp    A, r8
28.         jae    @Done
29.         mov    rax, qword ptr [A]
30.         mov    rdx, qword ptr [r8]
31.         mov    qword ptr [A], rdx
32.         mov    qword ptr [r8], rax
33. @Done:
34. end;
35.
36. procedure RevAVX2(var A: TDoubleDynArray); assembler; nostackframe;
37. const
38.         Vpermpd_ReverseDoublesInYMM = %00011011;
39. asm
40.         mov    A, qword ptr [A]
41.         test   A, A // A = nil?
42.         jz     @Done
43.         mov    r8, qword ptr [A - 8] // r8 = High(A)
44.         lea    r8, [A + 8 * r8 - 24] // r8 = A + length(A) - 4 doubles = right ptr
45.
46.         cmp    A, r8
47.         ja     @Prepare1x // no full vectors
48. @4xLoop:
49.         vpermpd ymm0, [A], Vpermpd_ReverseDoublesInYMM
50.         vpermpd ymm1, [r8], Vpermpd_ReverseDoublesInYMM
51.         vmovupd [A], ymm1
52.         vmovupd [r8], ymm0
54.         sub     r8, 32
55.         cmp     A, r8
56.         jbe     @4xLoop
57.         vzeroupper
58. @Prepare1x:
59.         add    r8, 24 // was −4 doubles, change to −1 double
60.         cmp    A, r8
61.         jae    @Done
62. @1xLoop:
63.         mov    rax, qword ptr [A]
64.         mov    rdx, qword ptr [r8]
65.         mov    qword ptr [A], rdx
66.         mov    qword ptr [r8], rax
68.         sub    r8, 8
69.         cmp    A, r8
70.         jb     @1xLoop
71. @Done:
72. end;

Code: [Select]
`Comparison with array length=20000, iterations=100000RevSimple 1.51s   RevPtr2 0.56s  RevSSE2 0.33s  RevAVX2 0.26sComparison with array length=200000, iterations=100000RevSimple 15.00s  RevPtr2 6.61s  RevSSE2 4.21s  RevAVX2 3.55s`

#### Weiss

• Full Member
• Posts: 107
##### Re: Reverse order of an array
« Reply #37 on: July 04, 2023, 09:59:36 am »
the idea behind my remark above is that the array is in place and in memory and does not need any intermediate copying:
1 iterator from low to high
1 iterator from high to low, you can output that to a new image if that is more convenient.
This flips the image and mirrors without extensive copying.

Maybe now you understand that such an approach makes a lot of sense.

I am thinking, wouldn't you want to re-use a well written function, and feed it an array in a certain order? Or you would re-write the function, because somehow you happen to have an array in reverse order of members?

Also, wouldn't it speed things up, say, if you plot something, to have prepared array, scaled and reversed, and integer-ized? Instead of performing all this math at plotting? Sure, you would have to manipulate data between arrays, but this would be happening outside of time-critical block of code. Right?