Optimizing code using the gcc back end (-gen gcc -O 2)

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
AGS
Posts: 1284
Joined: Sep 25, 2007 0:26
Location: the Netherlands

Optimizing code using the gcc back end (-gen gcc -O 2)

Postby AGS » Aug 18, 2010 21:54

When using the fbc asm back end it sometimes pays to use somewhat weird 'bithacks'.

The code below consists of two implementations of a string reversal function. The first, bithackreverse, uses some bit hacks to speed up the reversal. The second, reverse, does not use any hacks (unless you consider using pointers
a hack).

Be sure to replace "all.bas" with the name of a file on your PC that can be found by the program.


Code: Select all

Function bithackreverse(s As String) As Integer
'reverses the string s in-place

Var len_ = Len(s)

'do not reverse strings of length 0 or 1
If (len_ <= 1) Then
  Return 0
End If

'it takes 8 bytes to use bit tricks
Var div_ = len_ Shr 3
'after processing using bit tricks some
'data will be reversed without bit tricks
Var mod_ = len_ - (div_ Shl 3)
'x points to start of string (first four bytes)
Dim x As ULong Ptr = Cast(ULong Ptr,StrPtr(s))
'y points to end of string (final four bytes)
Dim z As ULong
'if string is smaller then 8 characters then no bit tricks
If (div_ >= 1) Then
  'bit tricks
  Dim y As ULong Ptr = Cast(ULong Ptr,StrPtr(s)+(len_ - 4)) 

  For i As Integer = 1 To div_
    z = *y
    *y = (*x Shr 24) Or ((*x Shr 8) And &B00000000000000001111111100000000) Or _
         (*x Shl 24) Or ((*x Shl 8) And &B00000000111111110000000000000000)
    *x = (z Shr 24) Or ((z Shr 8) And &B00000000000000001111111100000000) Or _
         (z Shl 24) Or ((z Shl 8) And &B00000000111111110000000000000000)
    y -= 1
    x += 1
  Next i
End If

'now reverse the final 7 bytes not handled by the bit tricks
Select Case As Const mod_

Case 0,1
  Return 0

'x => either a 0 or a 1

'xx,x x x
Case 2,3
  Var sp = Cast(UByte Ptr,x)
  Var tmp = sp[0]
  sp[0] = sp[mod_ - 1]
  sp[mod_ - 1] = tmp

'xx xx,xx x xx
Case 4,5
  Var sp = Cast(UByte Ptr,x)
  Var tmp = sp[0]
  sp[0] = sp[mod_ - 1]
  sp[mod_ - 1] = tmp
  tmp = sp[1]
  sp[1] = sp[mod_ - 2]
  sp[mod_ - 2] = tmp

'xxx xxx,xxx x xxx
Case 6,7
  Var sp = Cast(UByte Ptr,x)
  Var tmp = sp[0]
  sp[0] = sp[mod_ - 1]
  sp[mod_ - 1] = tmp
  tmp = sp[1]
  sp[1] = sp[mod_ - 2]
  sp[mod_ - 2] = tmp
  tmp = sp[2]
  sp[2] = sp[mod_ - 3]
  sp[mod_ - 3] = tmp

End Select

Return 0

End Function

Function reverse(s As String) As Integer

Var len_ = Len(s)

'do not reverse strings of length 0 or 1
If (len_ <= 1) Then
  Return 0
End If

Dim s1 As ZString Ptr = StrPtr(s)
Dim s2 As ZString Ptr = s1 + (len_ - 1)
While (s1 < s2)
  Var tmp = s1[0][0]
  s1[0][0] = s2[0][0]
  s2[0][0] = tmp
  s1 += 1:s2 -= 1
Wend

Return 0

End Function

Open "all.bas" For input as #1

Dim t As String
Dim s As String

While (EOF(1) = 0)
  Line Input #1,t
  If (t <> "") Then
    s += t
  End If
  t = ""
Wend
Close #1


Var t1 = Timer()
bithackreverse(s)
Var t2 = Timer()
Print Using "Runtime bithackreverse: ########.#########";t2 - t1
bithackreverse(s)
t1 = Timer()
reverse(s)
t2 = Timer()
Print Using "Runtime reverse       : ########.#########";t2 - t1


(Aside: save the above program to a file called reverse.bas)

When using the asm back end runtime performance of the two functions differs quite a lot (when used on large(ish) file).
Command line used to compile the program: fbc reverse.bas
Output:

Code: Select all

Runtime bithackreverse:        0.001000678
Runtime reverse       :        0.002143515

When using the gcc back end runtime performance of the two
functions resembles that of the asm back end.
Command line used to compile the program: fbc -gen gcc reverse.bas
Output:

Code: Select all

Runtime bithackreverse:        0.000991066
Runtime reverse       :        0.002321593


And now for something completely different....
Command line used to compile the program: fbc -gen gcc -O 2 reverse.bas
Output:

Code: Select all

Runtime bithackreverse:        0.000455819
Runtime reverse       :        0.000489715

The bithacking works when using the asm back end. When using the gcc back end with the -O 2 option the benefit of using bit hacks is gone.

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 1 guest