Author Topic: Reverse a string - timings please  (Read 1881 times)

jj2007

  • Member
  • *****
  • Posts: 10557
  • Assembler is fun ;-)
    • MasmBasic
Reverse a string - timings please
« on: December 11, 2018, 10:00:33 AM »
Just playing around with a new Rev$() macro - can I have some timings please?
Code: [Select]
Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz

?yaw retsaf a ereht sI .elddim eht ot gnitareti elihw sretcarahc eht paws ylpmis ot esohc I ,emit CISABkciuQ ym gniruD ?ypoc a gniod tuohtiw gnirts eht esrever ot elbissop ti si tuB .redro esrever ni ypoc
 a etaerc dna ,gnirts eht hguorht etareti ot eb dluow yaw tselpmis eht ,gnirts )iicsa( a gnisrever ot semoc ti nehW .sucof niam a neeb sah noitalupinam gnirts tsaf CISABkciuQ fo syad dlo eht ecniS

186 ms for reversing a 4000-byte string 100000 times with Rev$() A
183 ms for reversing a 4000-byte string 100000 times with Rev$() A
181 ms for reversing a 4000-byte string 100000 times with Rev$() A
179 ms for reversing a 4000-byte string 100000 times with Rev$() A
183 ms for reversing a 4000-byte string 100000 times with Rev$() A

191 ms for reversing a 4000-byte string 100000 times with Rev$() B
188 ms for reversing a 4000-byte string 100000 times with Rev$() B
185 ms for reversing a 4000-byte string 100000 times with Rev$() B
184 ms for reversing a 4000-byte string 100000 times with Rev$() B
186 ms for reversing a 4000-byte string 100000 times with Rev$() B

463 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
464 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
469 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
463 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
464 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()

87 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
87 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
86 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
88 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
86 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
29      bytes for Rev$_A
28      bytes for Rev$_B

TimoVJL

  • Member
  • ****
  • Posts: 556
Re: Reverse a string - timings please
« Reply #1 on: December 11, 2018, 10:18:00 AM »
Code: [Select]
AMD Athlon(tm) II X2 220 Processor

302 ms for reversing a 4000-byte string 100000 times with Rev$() A
286 ms for reversing a 4000-byte string 100000 times with Rev$() A
283 ms for reversing a 4000-byte string 100000 times with Rev$() A
282 ms for reversing a 4000-byte string 100000 times with Rev$() A
289 ms for reversing a 4000-byte string 100000 times with Rev$() A

319 ms for reversing a 4000-byte string 100000 times with Rev$() B
319 ms for reversing a 4000-byte string 100000 times with Rev$() B
319 ms for reversing a 4000-byte string 100000 times with Rev$() B
323 ms for reversing a 4000-byte string 100000 times with Rev$() B
319 ms for reversing a 4000-byte string 100000 times with Rev$() B

599 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
621 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
616 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
599 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
601 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()

127 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
127 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
127 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
128 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
128 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()

29      bytes for Rev$_A
28      bytes for Rev$_B
May the source be with you

sinsi

  • Guest
Re: Reverse a string - timings please
« Reply #2 on: December 11, 2018, 12:14:58 PM »
Code: [Select]
Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz

112 ms for reversing a 4000-byte string 100000 times with Rev$() A
110 ms for reversing a 4000-byte string 100000 times with Rev$() A
110 ms for reversing a 4000-byte string 100000 times with Rev$() A
110 ms for reversing a 4000-byte string 100000 times with Rev$() A
110 ms for reversing a 4000-byte string 100000 times with Rev$() A

131 ms for reversing a 4000-byte string 100000 times with Rev$() B
131 ms for reversing a 4000-byte string 100000 times with Rev$() B
131 ms for reversing a 4000-byte string 100000 times with Rev$() B
131 ms for reversing a 4000-byte string 100000 times with Rev$() B
132 ms for reversing a 4000-byte string 100000 times with Rev$() B

270 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
271 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
272 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
271 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
275 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()

53 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
53 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
53 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
53 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
53 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()

29      bytes for Rev$_A
28      bytes for Rev$_B

hutch--

  • Administrator
  • Member
  • ******
  • Posts: 7553
  • Mnemonic Driven API Grinder
    • The MASM32 SDK
Re: Reverse a string - timings please
« Reply #3 on: December 11, 2018, 04:23:01 PM »
Here is an in place string reverse that should have reasonable legs.

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

    include \masm32\include\masm32rt.inc
    .686p
    .mmx
    .xmm

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

comment * -----------------------------------------------------
                        Build this  template with
                       "CONSOLE ASSEMBLE AND LINK"
        ----------------------------------------------------- *

    rvstr MACRO src
      mov eax, src
      call rvst
    ENDM

    .data
      text db "abcdefghijklmnopqrstuvwxyz",0

    .code

start:
   
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

    call main
    inkey
    exit

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

main proc

    LOCAL ptxt  :DWORD
    LOCAL ltxt  :DWORD

    lea eax, text
    mov ptxt, eax

    print ptxt,13,10

  ; ******************************************

    rvstr ptxt      ; in place string reverse

  ; ******************************************

    print ptxt,13,10

    ret

main endp

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

 OPTION PROLOGUE:NONE
 OPTION EPILOGUE:NONE

 rvst proc
  ; ------------------
  ; src address in eax
  ; ------------------
    movd mm0, esi
    movd mm1, edi

    mov esi, eax        ; source in eax
    mov edi, esi

    push eax
    call StrLen
    mov edx, eax

    add edi, edx
    sub edi, 1
    shr edx, 1

  lbl:
    movzx eax, BYTE PTR [esi]
    movzx ecx, BYTE PTR [edi]
    mov BYTE PTR [edi], al
    mov BYTE PTR [esi], cl
    add esi, 1
    sub edi, 1
    sub edx, 1
    jnz lbl

    movd esi, mm0
    movd edi, mm1

    ret

 rvst endp

 OPTION PROLOGUE:PrologueDef
 OPTION EPILOGUE:EpilogueDef

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

end start
hutch at movsd dot com
http://www.masm32.com    :biggrin:  :skrewy:

Biterider

  • Member
  • ****
  • Posts: 542
  • ObjAsm Developer
    • ObjAsm
Re: Reverse a string - timings please
« Reply #4 on: December 11, 2018, 05:23:55 PM »
Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz

?yaw retsaf a ereht sI .elddim eht ot gnitareti elihw sretcarahc eht paws ylpmis ot esohc I ,emit CISABkciuQ ym gniruD ?ypoc a gniod tuohtiw gnirts eht esrever ot elbissop ti si tuB .redro esrever ni ypoc a etaerc dna ,gnirts eht hguorht etareti ot eb dluow yaw tselpmis eht ,gnirts )iicsa( a gnisrever ot semoc ti nehW .sucof niam a neeb sah noitalupinam gnirts tsaf CISABkciuQ fo syad dlo eht ecniS

122 ms for reversing a 4000-byte string 100000 times with Rev$() A
119 ms for reversing a 4000-byte string 100000 times with Rev$() A
120 ms for reversing a 4000-byte string 100000 times with Rev$() A
120 ms for reversing a 4000-byte string 100000 times with Rev$() A
120 ms for reversing a 4000-byte string 100000 times with Rev$() A

143 ms for reversing a 4000-byte string 100000 times with Rev$() B
142 ms for reversing a 4000-byte string 100000 times with Rev$() B
142 ms for reversing a 4000-byte string 100000 times with Rev$() B
142 ms for reversing a 4000-byte string 100000 times with Rev$() B
143 ms for reversing a 4000-byte string 100000 times with Rev$() B

323 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
297 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
297 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
296 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
294 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()

56 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
56 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
56 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
56 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
57 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()

29      bytes for Rev$_A
28      bytes for Rev$_B

Biterider

jj2007

  • Member
  • *****
  • Posts: 10557
  • Assembler is fun ;-)
    • MasmBasic
Re: Reverse a string - timings please
« Reply #5 on: December 11, 2018, 07:41:44 PM »
Thanks, Timo, Sinsi & BiteRider :icon14:

Here is an in place string reverse that should have reasonable legs.

Thanks, Hutch. It's pretty fast, actually, I thought the mm0 movs would slow it down but it doesn't:
Code: [Select]
Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz

---- long string ----
79 ms for reversing a 4000-byte string 50000 times with Rev$() A
82 ms for reversing a 4000-byte string 50000 times with Rev$() A
78 ms for reversing a 4000-byte string 50000 times with Rev$() A

233 ms for reversing a 4000-byte string 50000 times with Masm32 rev$()
238 ms for reversing a 4000-byte string 50000 times with Masm32 rev$()
250 ms for reversing a 4000-byte string 50000 times with Masm32 rev$()

50 ms for reversing a 4000-byte string 50000 times with MasmBasic Mirror$()
44 ms for reversing a 4000-byte string 50000 times with MasmBasic Mirror$()
44 ms for reversing a 4000-byte string 50000 times with MasmBasic Mirror$()

106 ms for reversing a 4000-byte string 50000 times with revstr (Hutch)
109 ms for reversing a 4000-byte string 50000 times with revstr (Hutch)
108 ms for reversing a 4000-byte string 50000 times with revstr (Hutch)

---- short string ----
1608 µs for reversing a 50-byte string 50000 times with Rev$() A
1605 µs for reversing a 50-byte string 50000 times with Rev$() A
1578 µs for reversing a 50-byte string 50000 times with Rev$() A

4407 µs for reversing a 50-byte string 50000 times with Masm32 rev$()
3842 µs for reversing a 50-byte string 50000 times with Masm32 rev$()
3832 µs for reversing a 50-byte string 50000 times with Masm32 rev$()

2106 µs for reversing a 50-byte string 50000 times with MasmBasic Mirror$()
2116 µs for reversing a 50-byte string 50000 times with MasmBasic Mirror$()
2114 µs for reversing a 50-byte string 50000 times with MasmBasic Mirror$()

1906 µs for reversing a 50-byte string 50000 times with revstr (Hutch)
1852 µs for reversing a 50-byte string 50000 times with revstr (Hutch)
1904 µs for reversing a 50-byte string 50000 times with revstr (Hutch)

29      bytes for Rev$_A
53      bytes for rvst

Siekmanski

  • Member
  • *****
  • Posts: 2331
Re: Reverse a string - timings please
« Reply #6 on: December 11, 2018, 09:48:46 PM »
Code: [Select]
Intel(R) Core(TM) i7-4930K CPU @ 3.40GHz

?yaw retsaf a ereht sI .elddim eht ot gnitareti elihw sretcarahc eht paws ylpmis
 ot esohc I ,emit CISABkciuQ ym gniruD ?ypoc a gniod tuohtiw gnirts eht esrever
ot elbissop ti si tuB .redro esrever ni ypoc a etaerc dna ,gnirts eht hguorht et
areti ot eb dluow yaw tselpmis eht ,gnirts )iicsa( a gnisrever ot semoc ti nehW
.sucof niam a neeb sah noitalupinam gnirts tsaf CISABkciuQ fo syad dlo eht ecniS


176 ms for reversing a 4000-byte string 100000 times with Rev$() A
171 ms for reversing a 4000-byte string 100000 times with Rev$() A
193 ms for reversing a 4000-byte string 100000 times with Rev$() A
163 ms for reversing a 4000-byte string 100000 times with Rev$() A
187 ms for reversing a 4000-byte string 100000 times with Rev$() A

183 ms for reversing a 4000-byte string 100000 times with Rev$() B
206 ms for reversing a 4000-byte string 100000 times with Rev$() B
170 ms for reversing a 4000-byte string 100000 times with Rev$() B
184 ms for reversing a 4000-byte string 100000 times with Rev$() B
175 ms for reversing a 4000-byte string 100000 times with Rev$() B

442 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
482 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
441 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
454 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
451 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()

86 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
98 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
85 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
83 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
75 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()

29      bytes for Rev$_A
28      bytes for Rev$_B
Creative coders use backward thinking techniques as a strategy.

AW

  • Member
  • *****
  • Posts: 2583
  • Let's Make ASM Great Again!
Re: Reverse a string - timings please
« Reply #7 on: December 12, 2018, 07:04:59 AM »
For large strings this should be faster because reverts 16 bytes at a time whenever possible:

Code: [Select]
    include \masm32\include\masm32rt.inc
.xmm

.data

crapBasicMsg db "Since the old days of QuickBASIC fast string manipulation has been a main focus. When it comes to " 
db "reversing a (ascii) string, the simplest way would be to iterate through the string, and create a copy in "
db "reverse order. But is it possible to reverse the string without doing a copy? During my QuickBASIC time, I chose to simply swap the characters while iterating to the middle. Is there a faster way?",0

msgLen dd ?
remaining dd ?
itCounter dd ?

align 16
result db 1024 dup (0)

align 16
shflmask dd 0C0D0E0Fh,08090A0Bh, 04050607h,00010203h

.code

main proc
invoke crt_strlen, addr crapBasicMsg
mov msgLen, eax
xor edx, edx
mov ecx, 16
div ecx
mov remaining, edx
mov itCounter, eax
lea esi, crapBasicMsg
add esi, msgLen

lea edi, result
mov ecx, 0
lea eax, shflmask
movdqa xmm2, [eax]
.while ecx<itCounter
sub esi, 16
movdqu xmm1, [esi]
vpshufb xmm0, xmm1, xmm2
movdqa [edi], xmm0
add edi, 16
inc ecx
.endw
mov ecx, 0
.while ecx<remaining
dec esi
mov al, [esi]
mov [edi], al

inc edi
inc ecx
.endw
print addr result,13,10
invoke ExitProcess,0

main endp

end

LordAdef

  • Member
  • ****
  • Posts: 651
Re: Reverse a string - timings please
« Reply #8 on: December 12, 2018, 11:23:54 AM »

Win10, 64bits.Console quits as soon as the job is done. I paused and copied what I could:
Code: [Select]
Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
?yaw retsaf a ereht sI .elddim eht ot gnitareti elihw sretcarahc eht paws ylpmis ot esohc I ,emit CISABkciuQ ym gniruD ?ypoc a gniod tuohtiw gnirts eht esrever ot elbissop ti si tuB .redro esrever ni ypoc a etaerc dna ,gnirts eht hguorht etareti ot eb dluow yaw tselpmis eht ,gnirts )iicsa( a gnisrever ot semoc ti nehW .sucof niam a neeb sah noitalupinam gnirts tsaf CISABkciuQ fo syad dlo eht ecniS

158 ms for reversing a 4000-byte string 100000 times with Rev$() A
153 ms for reversing a 4000-byte string 100000 times with Rev$() A
139 ms for reversing a 4000-byte string 100000 times with Rev$() A
169 ms for reversing a 4000-byte string 100000 times with Rev$() A
159 ms for reversing a 4000-byte string 100000 times with Rev$() A

169 ms for reversing a 4000-byte string 100000 times with Rev$() B
147 ms for reversing a 4000-byte string 100000 times with Rev$() B
184 ms for reversing a 4000-byte string 100000 times with Rev$() B
167 ms for reversing a 4000-byte string 100000 times with Rev$() B
149 ms for reversing a 4000-byte string 100000 times with Rev$() B


317 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()288 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
372 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
302 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()
301 ms for reversing a 4000-byte string 100000 times with Masm32 rev$()

68 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
67 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
56 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
67 ms for reversing a 4000-byte string 100000 times with MasmBasic Mirror$()
5

TimoVJL

  • Member
  • ****
  • Posts: 556
Re: Reverse a string - timings please
« Reply #9 on: December 12, 2018, 08:08:57 PM »
This may help in Explorer
Code: [Select]
Windows Registry Editor Version 5.00

[HKEY_CURRENT_USER\Software\Classes\*\shell\Open With cmd\command]
@="\"cmd.exe\" \"/k %1\""
May the source be with you

jj2007

  • Member
  • *****
  • Posts: 10557
  • Assembler is fun ;-)
    • MasmBasic
Re: Reverse a string - timings please
« Reply #10 on: December 12, 2018, 10:34:17 PM »
Console quits as soon as the job is done.
Thanks, Alex. I am used to an editor that waits for a keypress if it doesn't find an Inkey in the source. Workaround: launch the exe from a command prompt.

@Timo: Nice trick :t
« Last Edit: December 13, 2018, 06:42:53 AM by jj2007 »

daydreamer

  • Member
  • *****
  • Posts: 1364
  • building nextdoor
Re: Reverse a string - timings please
« Reply #11 on: December 16, 2018, 06:41:43 PM »
the fastest trick reduces reverse string down to zero clock cycles  :P  :use a string that also is a palindrom
or fastest palindrom-making code?
Quote from Flashdance
Nick  :  When you give up your dream, you die
*wears a flameproof asbestos suit*
Gone serverside programming p:  :D
I love assembly,because its legal to write
princess:lea eax,luke
:)