Fast Reverse String?

[MrSwiss]

Funny results, since they are all variing wildly, from run to run, with compiled exe.
ASM is fastest, when un-optimized (looses a lot otherwise).

ASM labels changed, to also compile with: -O 3 (failed before!) and changed
return also to byref ...

Code: Select all

'JJ
Function RevString (s as const string) ByRef As string
   static As String g : g=s
   asm
      mov   rcx,[g]
      mov   rax,[g+8]
      dec   rax
      _1:
      mov   dl,[rcx]
      mov   dh,[rcx+rax]
      mov    [rcx+rax],dl
      dec   rax
      mov   [rcx],dh
      inc   rcx
      dec   rax
      jns   _1
   end asm
   return g
End function

The number of run's (10) is insufficient, for differentiation with a true meaning ...

[leopardpm]

sorry to interrupt, but I understood that the FB 'SWAP' command is very inefficient - something someone told me one time but I don't know what is faster.... is this true?

[MrSwiss]

I understood that the FB 'SWAP' command is very inefficient

Well, currently, I wouldn't sign that ... (especially the: "very" bit).
There may be faster ways, but those are usually also, more complex to code, too.

[D.J.Peters]

yes swap is slow it's a function call not a (inline) macro

edit:
wait swap is on 64 bit faster than tmp=A : A=B : B=tmp
but on 32-bit swap is slower !

Joshy

[leopardpm]

yes swap is slow it's a function call not a (inline) macro

Joshy

so....

swap a,b

is slower than

c = a : a = b : b = c

?

[srvaldez]

I think D.J.Peters wins, and without any asm hack

Code: Select all

 0.2152194976806641         Total dodicat
 0.220289945602417          total MrSwiss
 0.1716921329498291         total Munair
 0.1263442039489746         total Joshy
 

[D.J.Peters]

@leopardpm I edit my post

Joshy

[leopardpm]

I think D.J.Peters wins, and without any asm hack

...cuz he IS the King of pointer manipulation!

[fxm]

Small typo, but big effect on the last character returned:

Code: Select all

'joshy
Function strRev(byref strIn As String) Byref  As  String
  type tString
    as ubyte ptr pChars
    as integer   nChars
    as integer   nReserved
  end type 
  static as STRING strOut
  dim as tString ptr pI=cptr(tString ptr,varptr(strIn))
  dim as tString ptr pO=cptr(tString ptr,varptr(strOut))
  dim as integer nChars = pI->nChars
  if nChars<2 then return strIn
  if nChars<>pO->nChars then
    pO->pChars=reallocate(pO->pChars,nChars+1)
    pO->nChars=nChars
    pO->nReserved=nChars+1
    pO->pChars[nChars]=0
  end if
  nChars-=1
  dim as ubyte ptr pS=@pI->pChars[nChars]
  dim as ubyte ptr pD=pO->pChars,pE=pD+nChars
'  while pD<pE : *pD=*pS : pS-=1 : pD+=1 : wend
  while pD<=pE : *pD=*pS : pS-=1 : pD+=1 : wend
  return strOut
End Function

[Munair]

Taken the source code from: viewtopic.php?f=7&t=27220&start=45#p255678

I adjusted my version slightly (copy on return instead of on entry and static result variable).

Code: Select all

' dc_s-test_invFunct.bas -- dodicat

'Munair
function RevStr(byref s as const string) as string
  static r as string
  static l as uinteger
  static n as uinteger
  
  r = s
  l = len(r) - 1
  n = 0
  
  while l > n
    swap r[n], r[l]
    n += 1
    l -= 1
  wend
 
  return r
end Function

' InvStr_Func.bas -- 2018-12-11, MrSwiss
'
Function InvStr(ByVal psz as ZString Ptr) ByRef As String
    Static As String    s : s = *psz
    Dim As ULong        mi = Len(s) - 1
   
    For i As Integer = mi To 0 Step -1
        s[i] = (*psz)[mi - i]
    Next
    Return s
End Function

'dodicat
Function reverse(s As String) Byref  As  String
    Dim As zstring Ptr z=Strptr(s)
    Dim As Long ll=Len(s)-1
    static As String g:g=s
    For n As Integer=ll To 0 Step -1
      g[ll-n] = z[0][n]
    Next
    Return g
End Function

'joshy
Function strRev(byref strIn As String) Byref  As  String
  type tString
    as ubyte ptr pChars
    as integer   nChars
    as integer   nReserved
  end type 
  static as STRING strOut
  dim as tString ptr pI=cptr(tString ptr,varptr(strIn))
  dim as tString ptr pO=cptr(tString ptr,varptr(strOut))
  dim as integer nChars = pI->nChars
  if nChars<2 then return strIn
  if nChars<>pO->nChars then
    pO->pChars=reallocate(pO->pChars,nChars+1)
    pO->nChars=nChars
    pO->nReserved=nChars+1
    pO->pChars[nChars]=0
  end if
  nChars-=1
  dim as ubyte ptr pS=@pI->pChars[nChars]
  dim as ubyte ptr pD=pO->pChars,pE=pD+nChars
  while pD<pE : *pD=*pS : pS-=1 : pD+=1 : wend
  return strOut
End Function


Dim As String s = "abcdefghijklmnopqrstuvwxyz"

For n As Long = 1 To 19
    s+=s
Next

Print "Length of string  ";Len(s)
Print

Dim As Double accD,accS,accM,accJ
Dim As Double t,t2
dim as string ret
For m As Long=1 To 10
    sleep 50
    ret=""
    t=Timer
    ret= reverse(s)
    t2=Timer
    accD+=t2-t
    Print t2-t, "dodicat"
    Print Left(ret,26),Left(s,26)
    Sleep 50
    ret=""
    t=Timer
    ret=invstr(s)
    t2=Timer
    accS+=t2-t
    Print t2-t,"Mr Swiss"
    Print Left(ret,26),Left(s,26)
    Sleep 50
    ret=""
    t=Timer
    ret=revstr(s)
    t2=Timer
    accM+=t2-t
    Print t2-t,"Munair"
    Print Left(ret,26),Left(s,26)
    Sleep 50
    ret=""
    t=Timer()
    ret=strRev(s)
    t2=Timer()
    accJ+=t2-t
    Print t2-t,"Joshy"
    Print Left(ret,26),Left(s,26)
    Print
Next m

Print accD,"Total dodicat"
Print accS,"total MrSwiss"
Print accM,"total Munair"
Print accJ,"total Joshy"
Sleep 

On Linux 64 bits

without optimization:
0.5962741374969482 Total dodicat
0.5579135417938232 total MrSwiss
0.5234484672546387 total Munair
0.4568610191345215 total Joshy

with -O3:
0.3029398918151855 Total dodicat
0.2604489326477051 total MrSwiss
0.2473878860473633 total Munair
0.1864223480224609 total Joshy

[D.J.Peters]

@fxm good find (it's fixed know)

pE = pD + nChars + 1
while pD<pE
...
should be faster than
pE = pD + nChars
while pD<=pE

I will try it

Joshy

[Munair]

wait swap is on 64 bit faster than tmp=A : A=B : B=tmp

Joshy

Indeed.

[D.J.Peters]

...cuz he IS the King of pointer manipulation!

Not really but I know how to help a compiler :-)

Long time ago, FreeBASIC was a x86 compiler (emitter) only I have done many things with inline assembler
but since FreeBASIC is a real cross compiler and run's on my cute Raspberry PI and Beagle Bone black also
I try to get my best in "BASIC" as a hobby.

The fastest solution is to have addresses or better offsets to memory addresses calculated to compile time not runtime.

I won't lay me out the window but should be hard to get it faster than this version.

Joshy

Code: Select all

'joshy
Function strRev(byref strIn As String) Byref  As  String
  type tString
    as ubyte ptr pChars
    as integer   nChars
    as integer   nReserved
  end type  
  static as STRING strOut
  var pI=cptr(tString ptr,varptr(strIn))
  var pO=cptr(tString ptr,varptr(strOut))
  var nChars = pI->nChars
  if nChars<2 then return strIn
  if nChars<>pO->nChars then
    pO->pChars=reallocate(pO->pChars,nChars+1)
    pO->nChars=nChars
    pO->nReserved=nChars+1
    pO->pChars[nChars]=0
  end if
  dim as ubyte ptr pS=@pI->pChars[nChars-1]
  dim as ubyte ptr pD=pO->pChars,pE=pD+nChars
  #define NOT_A_TRICK(a) pD[a]=pS[-a]
  while nChars>64
    NOT_A_TRICK(0)  : NOT_A_TRICK(1)  : NOT_A_TRICK(2)  : NOT_A_TRICK(3)
    NOT_A_TRICK(4)  : NOT_A_TRICK(5)  : NOT_A_TRICK(6)  : NOT_A_TRICK(7)
    NOT_A_TRICK(8)  : NOT_A_TRICK(9)  : NOT_A_TRICK(10) : NOT_A_TRICK(11)
    NOT_A_TRICK(12) : NOT_A_TRICK(13) : NOT_A_TRICK(14) : NOT_A_TRICK(15)
    
    NOT_A_TRICK(16) : NOT_A_TRICK(17) : NOT_A_TRICK(18) : NOT_A_TRICK(19)
    NOT_A_TRICK(20) : NOT_A_TRICK(21) : NOT_A_TRICK(22) : NOT_A_TRICK(23)
    NOT_A_TRICK(24) : NOT_A_TRICK(25) : NOT_A_TRICK(26) : NOT_A_TRICK(27)
    NOT_A_TRICK(28) : NOT_A_TRICK(29) : NOT_A_TRICK(30) : NOT_A_TRICK(31)
    
    NOT_A_TRICK(32) : NOT_A_TRICK(33) : NOT_A_TRICK(34) : NOT_A_TRICK(35)
    NOT_A_TRICK(36) : NOT_A_TRICK(37) : NOT_A_TRICK(38) : NOT_A_TRICK(39)
    NOT_A_TRICK(40) : NOT_A_TRICK(41) : NOT_A_TRICK(42) : NOT_A_TRICK(43)
    NOT_A_TRICK(44) : NOT_A_TRICK(45) : NOT_A_TRICK(46) : NOT_A_TRICK(47)
    
    NOT_A_TRICK(48) : NOT_A_TRICK(49) : NOT_A_TRICK(50) : NOT_A_TRICK(51)
    NOT_A_TRICK(52) : NOT_A_TRICK(53) : NOT_A_TRICK(54) : NOT_A_TRICK(55)
    NOT_A_TRICK(56) : NOT_A_TRICK(57) : NOT_A_TRICK(58) : NOT_A_TRICK(59)
    NOT_A_TRICK(60) : NOT_A_TRICK(61) : NOT_A_TRICK(62) : NOT_A_TRICK(63)    
    pD+=64:pS-=64:nChars-=64
  wend  

  while nChars>32
    NOT_A_TRICK(0)  : NOT_A_TRICK(1)  : NOT_A_TRICK(2)  : NOT_A_TRICK(3)
    NOT_A_TRICK(4)  : NOT_A_TRICK(5)  : NOT_A_TRICK(6)  : NOT_A_TRICK(7)
    NOT_A_TRICK(8)  : NOT_A_TRICK(9)  : NOT_A_TRICK(10) : NOT_A_TRICK(11)
    NOT_A_TRICK(12) : NOT_A_TRICK(13) : NOT_A_TRICK(14) : NOT_A_TRICK(15)
    
    NOT_A_TRICK(16) : NOT_A_TRICK(17) :  NOT_A_TRICK(18) : NOT_A_TRICK(19)
    NOT_A_TRICK(20) : NOT_A_TRICK(21) :  NOT_A_TRICK(22) : NOT_A_TRICK(23)
    NOT_A_TRICK(24) : NOT_A_TRICK(25) :  NOT_A_TRICK(26) : NOT_A_TRICK(27)
    NOT_A_TRICK(28) : NOT_A_TRICK(29) :  NOT_A_TRICK(30) : NOT_A_TRICK(31)
    pD+=32:pS-=32:nChars-=32
  wend

  while nChars>16
    NOT_A_TRICK(0)  : NOT_A_TRICK(1)  : NOT_A_TRICK(2)  : NOT_A_TRICK(3)
    NOT_A_TRICK(4)  : NOT_A_TRICK(5)  : NOT_A_TRICK(6)  : NOT_A_TRICK(7)
    NOT_A_TRICK(8)  : NOT_A_TRICK(9)  : NOT_A_TRICK(10) : NOT_A_TRICK(11)
    NOT_A_TRICK(12) : NOT_A_TRICK(13) : NOT_A_TRICK(14) : NOT_A_TRICK(15)
    pD+=16:pS-=16:nChars-=16
  wend

  while nChars>8
    NOT_A_TRICK(0) : NOT_A_TRICK(1) :  NOT_A_TRICK(2) : NOT_A_TRICK(3)
    NOT_A_TRICK(4) : NOT_A_TRICK(5) :  NOT_A_TRICK(6) : NOT_A_TRICK(7)
    pD+=8:pS-=8:nChars-=8
  wend

  while nChars>4
    NOT_A_TRICK(0) : NOT_A_TRICK(1) :  NOT_A_TRICK(2) : NOT_A_TRICK(3)
    pD+=4:pS-=4:nChars-=4
  wend

  while pD<pE : *pD=*pS : pS-=1 : pD+=1 : wend
  return strOut
End Function

32-bit gen gcc no optimization
0.445 Joshy
0.808 dodicat
0.864 MrSwiss
0.957 Munair

64-bit gen gcc no optimization
0.431 Joshy
0.768 dodicat
0.942 Munair
1.045 MrSwiss

[leopardpm]

@joshy

say what you will... but in looking at the various code samples from each of you - I know that am in the presence of greatness...

[Munair]

@Joshy, I am unable to reproduce your results on 64 bits Linux. My results on average do not come close to yours.