Reverse order of an array

[Nitorami]

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

1. Did you know before hand?

Let's say I was fairly confident because I tried many similar cases before, on different machines, and the results were always slightly biased towards normal array indices. 

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

1. I would not discourage these tests.

No. But I would neither propose using pointer arithmetics to newbies. It is easy to get it wrong, and to bypass type checking, producing frustrating erors. In general with nowadays compiler optimisation, it is no longer necessary to use tricky pointer arithmetics for maximum efficiency.

[howardpc]

But just assume that the pointer arithmetic code were faster by some significant amount, then we know there is a possibility the compiler needs some adjustment. I would not discourage these tests.

There would be value in discussing theoretical compiler efficient-code-generation possibilities, and doing a comparison of explicit pointer vs. non-pointer implementations for that reason.
As far as ReverseInPlace() is concerned though, does anyone see a real-world need for this array reordering routine, when Pascal has built-in syntax for iterating arrays either ascending or descending?

[Martin_fr]

Afaik there is still a lack of certain optimizations. So using pointers can (read below) make a difference. And 5% can be a huge diff, as well as it can be a small diff.

Generally I do really discourage those optimizations. They can easily backfire by adding hard to find bugs, or preventing newer fpc from doing new optimizations (and then the pointers are slower)

Using pointers, is not always just about pointers, but also about the total of variables used in a procedure and in a loop.
And with that the amount of variables NOT stored in registers.

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

1.  p1 := @A[0];
2.   p2 := p1+High(A);
3.   for i := High(A) div 2 downto 0 do
4.   begin
5.     Tmp := p1^;

Now the loop has 4 variables (i, p1, p2, tmp). "High(a)" is only needed before the loop starts, and "0" is a constant

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

1.   for i := 0 to iMax div 2 do
2.   begin
3.     Tmp := A[i];

This loop only had 3 variables (i, A, tmp).

So worst case the pointer version does not have enough registers, and will be slower.

This can be improved (no need for i):

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

1.  p1 := @A[0];
2.   p2 := p1+High(A);
3.   while p2 > p1 do
4.  

But it still needs 3 registers. Same as the none pointer.

----
I am not saying that it will gain anything in this particular case... Just pointing out that doing optimizations by hand is a tricky business.

And in the end, it had to be tested for each indented platform/cpu (even different cpu of the same class, eg older pentium vs newer pentium).... And with each new fpc version again.


----
In larger code, using pointers sometime can help bringing down the amount of required registers. And if you can the tune the code, so fpc actually uses registers for all variables in a loop, then it may help.

I used this (and more) long ago, with an older fpc version
https://bugs.freepascal.org/view.php?id=10275
The speed diff was significant. The loss of read-ability for the code too.

[BrunoK]

Why do you never write a real program to test and argue about your assertions.

FPC 3.0.4 I386

The code with for ... and array indexing  takes roughly 1/2 more bytes of assembler than code with use of pointers so it is quite likely that the code with pointer is going to be faster.
Until proven false I'll take the code with pointers.

Bytes of assembler in routines
ReverseInPlace : I386 -O2 array indexing -> 96 bytes   -O3->96 bytes   -O4->96 bytes
ReverseInPlaceWithPointers : I386 -O2 pointers -> 60 bytes  -O3->59 bytes  -O4->60 bytes

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

1. program Project1;
2.  
3.   procedure ReverseInPlace(var A: array of double);
4.   var
5.     i: integer;
6.     Tmp: double;
7.     iMax: integer;
8.   begin
9.     iMax := High(A);
10.     for i := 0 to iMax div 2 do begin
11.       Tmp := A[i];
12.       A[i] := A[iMax - i];
13.       A[iMax - i] := Tmp;
14.     end;
15.   end;                          // I386 -O2 96 bytes
16.  
17.   procedure ReverseInPlaceWithPointers(var A: array of double);
18.   var
19.     Tmp: double;
20.     iMin, imax: pDouble;
21.   begin
22.     iMin := @A[0];
23.     imax := @A[High(A)];
24.     while iMin < iMax do begin
25.       Tmp := iMax^;
26.       iMax^ := iMin^;
27.       iMin^ := Tmp;
28.       Inc(iMin);
29.       Dec(iMax);
30.     end;
31.   end;                          // I386 -O2 60 bytes
32.  
33. var
34.   ArrayOfDouble: array of double;
35.   ix: integer;
36. begin
37.   SetLength(ArrayOfDouble, 10);
38.   for ix := 0 to High(ArrayOfDouble) do begin
39.     ArrayOfDouble[ix] := Random * 1000;
40.     Write(ArrayOfDouble[ix]: 6: 0);
41.   end;
42.   WriteLn;
43.   ReverseInPlace(ArrayOfDouble);
44.   for ix := 0 to High(ArrayOfDouble) do
45.     Write(ArrayOfDouble[ix]: 6: 0);
46.   WriteLn;
47.   ReverseInPlaceWithPointers(ArrayOfDouble);
48.   for ix := 0 to High(ArrayOfDouble) do
49.     Write(ArrayOfDouble[ix]: 6: 0);
50.   WriteLn;
51.   ReadLn;
52. end.
53.  

Any way the gains in speed are negligible except if you run the code millions of times.

[Nitorami]

The code with for ... and array indexing  takes roughly 1/2 more bytes of assembler than code with use of pointers so it is quite likely that the code with pointer is going to be faster.

No.

Why do you never write a real program to test and argue about your assertions.

Yep. I just said three posts above that I tested it and the native array solution is a bit faster on my machine. Just test for yourself.

[BrunoK]

@Nitorami

You didn't show anycode, just blabla..

What was your timing protocol, show code !

[Nitorami]

*Sigh*

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

1. uses sysutils;
2.  
3. {$DEFINE Pointers}
4. {$IFNDEF Pointers}
5. procedure Rev(var A: array of Double);
6. var
7.   i, j , imax: dword;
8.   Tmp: Double;
9. begin
10.   if Length(A)=0 then exit;
11.   imax := high(A);
12.   for i := imax div 2 downto 0 do
13.   begin
14.     j := imax-i;
15.     Tmp := A[i];
16.     A[i] := A[j];
17.     A[j]:= tmp;
18.   end;
19. end;
20. {$ELSE}
21. procedure Rev(var A: array of Double);
22. var
23.   i: Integer;
24.   Tmp: Double;
25.   p1: pdouble;
26.   p2: pdouble;
27. begin
28.   if Length(A)=0 then exit;
29.   p1 := @A[0];
30.   p2 := p1+High(A);
31.   for i := High(A) div 2 downto 0 do
32.   begin
33.     Tmp := p1^;
34.     p1^ := p2^;
35.     p2^ := Tmp;
36.     inc(p1);
37.     dec(p2);
38.   end;
39. end;
40. {$ENDIF}
41.  
42. var n: longint;
43.     T1: TDateTime;
44.     A: array of double;
45. begin
46.   SetLength (A,20000);
47.   for n:= 0 to high(A) do A[n] := random;
48.   T1 := now;
49.   for n:= 0 to 10000 do Rev(A);
50.   writeln ((now-T1)*24*3600:2:2);
51. end.
52.  

[BrunoK]

I will try tomorrow an post my results wathever they are.
Thanks for showing your code protocol.

[howardpc]

My testing, adapted from nitorami's code, shows that the pointer implementation is over 3 times quicker than the simpler approach on my machine.

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

1. program project1;
2.  
3. uses sysutils;
4.  
5. type
6.   TDoubleDynArray = array of Double;
7.  
8. procedure RevSimple(var A: TDoubleDynArray);
9. var
10.   i, j , imax: dword;
11.   Tmp: Double;
12. begin
13.   if Length(A)=0 then exit;
14.   imax := high(A);
15.   for i := imax div 2 downto 0 do
16.   begin
17.     j := imax-i;
18.     Tmp := A[i];
19.     A[i] := A[j];
20.     A[j]:= tmp;
21.   end;
22. end;
23.  
24. procedure RevPtr(var A: TDoubleDynArray);
25. var
26.   i: Integer;
27.   Tmp: Double;
28.   p1: pdouble;
29.   p2: pdouble;
30. begin
31.   if Length(A)=0 then exit;
32.   p1 := @A[0];
33.   p2 := p1+High(A);
34.   for i := High(A) div 2 downto 0 do
35.   begin
36.     Tmp := p1^;
37.     p1^ := p2^;
38.     p2^ := Tmp;
39.     inc(p1);
40.     dec(p2);
41.   end;
42. end;
43.  
44. procedure CompareReversing(anArrayLength, anIterations: LongWord);
45. var n: longint;
46.     T1: TDateTime;
47.     A: TDoubleDynArray;
48. begin
49.   WriteLn('Comparison with array length=',anArrayLength,', iterations=',anIterations);
50.   SetLength (A, anArrayLength);
51.   for n:= 0 to High(A) do
52.     A[n] := Random;
53.  
54.   T1 := Now;
55.   for n:= 1 to anIterations do RevSimple(A);
56.   Write('RevSimple ',(Now-T1)*SecsPerDay:2:2,'s  ');
57.  
58.   T1 := Now;
59.   for n:= 1 to anIterations do RevPtr(A);
60.   WriteLn ('RevPtr ',(Now-T1)*SecsPerDay:2:2,'s');
61. end;
62.  
63. begin
64.   CompareReversing(20000, 10000);
65.   CompareReversing(20000, 100000);
66.   CompareReversing(200000, 10000);
67.   CompareReversing(200000, 100000);
68. end.

Typical output:

Comparison with array length=20000, iterations=10000
RevSimple 0.92s  RevPtr 0.24s
Comparison with array length=20000, iterations=100000
RevSimple 9.27s  RevPtr 2.44s
Comparison with array length=200000, iterations=10000
RevSimple 9.71s  RevPtr 2.54s
Comparison with array length=200000, iterations=100000
RevSimple 93.24s  RevPtr 24.79s     

[Nitorami]

Here is my result (reduced the lengths by factor ten because I did not want to wait for ages)
Optimisation Level2

Comparison with array length=2000, iterations=10000
RevSimple 0.37s  RevPtr 0.39s
Comparison with array length=2000, iterations=100000
RevSimple 3.68s  RevPtr 3.89s
Comparison with array length=20000, iterations=10000
RevSimple 3.67s  RevPtr 3.88s
Comparison with array length=20000, iterations=100000
RevSimple 36.62s  RevPtr 38.86s

[Martin_fr]

Comparing with -O1 or -O- they are equally fast/slow.

Comparing with -O4 I get the pointer faster, but only about 30%.

[Martin_fr]

Optimisation Level2

Does that include "use registers" -Or ?

If not try adding -Or

Also depending on cpu, and how many registers there are: Try the "while p2>p1" that I posted above

[taazz]

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

1. procedure RevPtr2(var A: TDoubleDynArray);
2. var
3.   Tmp: Double;
4.   p1: pdouble;
5.   p2: pdouble;
6. begin
7.   if Length(A)=0 then exit;
8.   p1 := @A[0];
9.   p2 := p1+High(A);
10.   while p1<p2 do
11.   begin
12.     Tmp := p1^;
13.     p1^ := p2^;
14.     p2^ := Tmp;
15.     inc(p1);
16.     dec(p2);
17.   end;
18. end;        
19.  

default settings -O1

Code: [Select]

Comparison with array length=20000, iterations=10000
RevSimple 0.47s  RevPtr 0.32s RevPtr2 0.34s
Comparison with array length=20000, iterations=100000
RevSimple 4.37s  RevPtr 3.27s RevPtr2 3.35s
Comparison with array length=200000, iterations=10000
RevSimple 4.38s  RevPtr 3.29s RevPtr2 3.35s
Comparison with array length=200000, iterations=100000
RevSimple 43.84s  RevPtr 32.93s RevPtr2 33.63s
release mode -O3 optimizations.

Code: [Select]

Comparison with array length=20000, iterations=10000
RevSimple 0.29s  RevPtr 0.18s RevPtr2 0.19s
Comparison with array length=20000, iterations=100000
RevSimple 2.90s  RevPtr 1.80s RevPtr2 1.79s
Comparison with array length=200000, iterations=10000
RevSimple 2.89s  RevPtr 1.87s RevPtr2 1.87s
Comparison with array length=200000, iterations=100000
RevSimple 28.88s  RevPtr 18.64s RevPtr2 18.66s


[Nitorami]

Yes, I used register variables.
The while loop "while p2>p1" is rather a tiny bit slower, as expected. For loops are normally the fastest option.

[Martin_fr]

Yes, I used register variables.
The while loop "while p2>p1" is rather a tiny bit slower, as expected. For loops are normally the fastest option.

And there you see how much all depends on the environment (eg exact cpu)

For me the "while was just a tick (0.5%) faster. (yes that is close, but it happened consistently)
Intel(R) Pentium(R) CPU 2020M @ 2.40GHz
fpc from svn 2018/01/08

Anyway, the "while" would be interesting if the logic in the loop required more variables. It frees the loop counter, and makes one register more available.