Recent

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

BrunoK

  • Sr. Member
  • ****
  • Posts: 452
  • 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: 423
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: 6091
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

Thaddy

  • Hero Member
  • *****
  • Posts: 14210
  • Probably until I exterminate Putin.
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 »
Specialize a type, not a var.

jamie

  • Hero Member
  • *****
  • Posts: 6091
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: 6091
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
  11.  Addq %RCX,%RDI;
  12. Redo:
  13.  Mov (%RSI),%RCX;
  14.  xchg (%RDI), %RCX;
  15.  Mov %RCX, (%RSI);
  16.  Addq $8, %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: 78
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).

I made vectorized versions =3.

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
  21.         add    A, 16
  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
  53.         add     A, 32
  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
  67.         add    A, 8
  68.         sub    r8, 8
  69.         cmp    A, r8
  70.         jb     @1xLoop
  71. @Done:
  72. end;

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

Weiss

  • Full Member
  • ***
  • Posts: 127
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?

 

TinyPortal © 2005-2018