Bit duplication

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
UEZ
Posts: 336
Joined: May 05, 2017 19:59
Location: Germany

Re: Bit duplication

Postby UEZ » Feb 19, 2019 12:57

Why is this function drastically slower?

Code: Select all

Function BitDupp(n As Ubyte, ln As Single) As Ushort
   Dim As Ushort iResult, j, k = 0
   For i As Ubyte = 0 To Ln - 1
      j = (n Shr i) And 1
      iResult += (1 Shl k) * j + (1 Shl (k + 1)) * j
      k += 2
   Next
   Return iResult
End Function

Dim As Single Ln = Cubyte(Log(i0) / Log(2)) + 1


Here the full code:

Code: Select all

function duplicate naked cdecl (byval inbyte as long) as integer
  asm
  .align 4
  mov edx, [esp+4]
  xor eax, eax
  mov ecx, -1073741824
L0:
  rol ecx, 2
  shr edx, 1
  je L1
  jnc L0
  or eax, ecx
  jmp L0
L1:
  jnc Lx2
  or eax, ecx
Lx2:
  ret
  end asm
end function

Function doublebitter(Byval n As Long) As longint
 Var b=Bin(n),position=0
 position=Instr(b,"1")
 While position>0
 b=Mid(b,1,position-1) & "11" & Mid(b,position+Len("1"))
 position=Instr(position+Len("11"),b,"1")
 Wend
 position=Instr(b,"0")
 While position>0
 b=Mid(b,1,position-1) & "00" & Mid(b,position+Len("0"))
 position=Instr(position+Len("00"),b,"0")
 Wend
 Return culngint("&b" + b)
End Function


sub create(a() as longint,n as long=255)
 redim a(n)
 for i as long=0 to n
 a(i)=doublebitter(i)
 next
end sub

redim as longint dbitters()

function dup8bits naked cdecl ( byval x as ulong ) as ulong
   asm
#ifdef __FB_64BIT__
   .align 16
   #ifdef __FB_LINUX__
      mov rax, rdi
   #else
      mov rax, rcx
   #endif
#else
      .align 4
      mov eax, [esp+4]
#endif
      '' r and &h00ff
      and eax, &h00ff
     
      '' r = (r or (r shl 4)) and &h0f0f
      mov edx, eax
      shl edx, 4
      or  eax, edx
      and eax, &h0f0f
     
      '' r = (r or (r shl 2)) and &h3333
      mov edx, eax
      shl edx, 2
      or  eax, edx
      and eax, &h3333
     
      '' r = (r or (r shl 1)) and &h5555
      mov edx, eax
      shl edx, 1
      or  eax, edx
      and eax, &h5555
     
      '' return r * 3
      mov edx, eax
      shl edx, 1
      or eax, edx
      ret
   end asm
end function


Function BitDupp(n As Ubyte, ln As Single) As Ushort
   Dim As Ushort iResult, j, k = 0
   For i As Ubyte = 0 To Ln - 1
      j = (n Shr i) And 1
      iResult += (1 Shl k) * j + (1 Shl (k + 1)) * j
      k += 2
   Next
   Return iResult
End Function


cls
dim as ubyte i, i0
dim as ushort o = 0, c = 0
input "Number 0-255: ", i
i0=i   ' keep a copy
print "in: " & i & " - " & bin(i, 8)
dim as integer bitNum = 0
Dim as double t=timer
#define loops 10000000'0
print "testing ";loops;" iterations"

' ************* badidea A *************
For n as integer=1 to loops
   i=i0
   o=0
   bitNum = 0
   #if 1
      do
         c = i and 1 'least significant bit of i
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         i shr= 1
      loop until i = 0
   #else
      do
         c = i and 1 'least significant bit of i
         c = (c shl 1) or c 'duplicate lsb
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 2
         i shr= 1
      loop until i = 0
   #endif
Next
print using "##.### seconds, badidea A     "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

' ************* badidea B *************
t=timer
For n as integer=1 to loops
   i=i0
   o=0
   bitNum = 0
   #if 0
      do
         c = i and 1 'least significant bit of i
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         i shr= 1
      loop until i = 0
   #else
      do
         c = i and 1 'least significant bit of i
         c = (c shl 1) or c 'duplicate lsb
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 2
         i shr= 1
      loop until i = 0
   #endif
Next
print using "##.### seconds, badidea B     "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

' ************* jj2007 *************
t=timer
For n as integer=1 to loops
   o=duplicate(i0)
Next
print using "##.### seconds, assembly      "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

'dodicat
t=timer
create(dbitters(),i0)
For n as integer=1 to loops
   o=dbitters(i0)
Next
print using "##.### seconds, lookup        "; timer-t;
print ", out: " & o & " - " & bin(o, 16)
'coder jeff
t=timer
For n as integer=1 to loops
   o= dup8bits(i0)
Next
print using "##.### seconds, coder jeff    "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

Dim As Single Ln = Cubyte(Log(i0) / Log(2)) + 1
t=timer
For n as integer=1 to loops
   o= BitDupp(i0, Ln)
Next
print using "##.### seconds, UEZ           "; timer-t;
print ", out: " & o & " - " & bin(o, 16)
sleep


My expectation was rather 1.5~2.0 slower than badidea's slowest version but over 3x times was a surprise for me.

Btw, there must be a formula which calculates also the proper outcome...
Last edited by UEZ on Feb 19, 2019 13:22, edited 1 time in total.
jj2007
Posts: 1214
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Bit duplication

Postby jj2007 » Feb 19, 2019 13:07

Multiplication is costly (and division is much worse).
UEZ
Posts: 336
Joined: May 05, 2017 19:59
Location: Germany

Re: Bit duplication

Postby UEZ » Feb 19, 2019 13:32

This is more optimized version of my function:

Code: Select all

Function BitDupp(n As Ubyte, ln As Ubyte) As Ushort
   Dim As Ushort iResult, k = 0, l
   For i As Ubyte = 0 To Ln
      l = (1 Shl k)
      If ((n Shr i) And 1) Then iResult += l + (l Shl 1)
      k += 2
   Next
   Return iResult
End Function


Code: Select all

function duplicate naked cdecl (byval inbyte as long) as integer
  asm
  .align 4
  mov edx, [esp+4]
  xor eax, eax
  mov ecx, -1073741824
L0:
  rol ecx, 2
  shr edx, 1
  je L1
  jnc L0
  or eax, ecx
  jmp L0
L1:
  jnc Lx2
  or eax, ecx
Lx2:
  ret
  end asm
end function

Function doublebitter(Byval n As Long) As longint
 Var b=Bin(n),position=0
 position=Instr(b,"1")
 While position>0
 b=Mid(b,1,position-1) & "11" & Mid(b,position+Len("1"))
 position=Instr(position+Len("11"),b,"1")
 Wend
 position=Instr(b,"0")
 While position>0
 b=Mid(b,1,position-1) & "00" & Mid(b,position+Len("0"))
 position=Instr(position+Len("00"),b,"0")
 Wend
 Return culngint("&b" + b)
End Function


sub create(a() as longint,n as long=255)
 redim a(n)
 for i as long=0 to n
 a(i)=doublebitter(i)
 next
end sub

redim as longint dbitters()

function dup8bits naked cdecl ( byval x as ulong ) as ulong
   asm
#ifdef __FB_64BIT__
   .align 16
   #ifdef __FB_LINUX__
      mov rax, rdi
   #else
      mov rax, rcx
   #endif
#else
      .align 4
      mov eax, [esp+4]
#endif
      '' r and &h00ff
      and eax, &h00ff
     
      '' r = (r or (r shl 4)) and &h0f0f -> 0000‭111100001111‬
      mov edx, eax
      shl edx, 4
      or  eax, edx
      and eax, &h0f0f
     
      '' r = (r or (r shl 2)) and &h3333 -> ‭0011001100110011‬
      mov edx, eax
      shl edx, 2
      or  eax, edx
      and eax, &h3333
     
      '' r = (r or (r shl 1)) and &h5555 -> ‭0101010101010101‬
      mov edx, eax
      shl edx, 1
      or  eax, edx
      and eax, &h5555
     
      '' return r * 3
      mov edx, eax
      shl edx, 1
      or eax, edx
      ret
   end asm
end function

Function BitDupp(n As Ubyte, ln As Ubyte) As Ushort
   Dim As Ushort iResult, k = 0, l
   For i As Ubyte = 0 To Ln
      l = (1 Shl k)
      If ((n Shr i) And 1) Then iResult += l + (l Shl 1)
      k += 2
   Next
   Return iResult
End Function


cls
dim as ubyte i, i0
dim as ushort o = 0, c = 0
input "Number 0-255: ", i
i0=i   ' keep a copy
print "in: " & i & " - " & bin(i, 8)
dim as integer bitNum = 0
Dim as double t=timer
#define loops 100000000
print "testing ";loops;" iterations"

' ************* badidea A *************
For n as integer=1 to loops
   i=i0
   o=0
   bitNum = 0
   #if 1
      do
         c = i and 1 'least significant bit of i
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         i shr= 1
      loop until i = 0
   #else
      do
         c = i and 1 'least significant bit of i
         c = (c shl 1) or c 'duplicate lsb
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 2
         i shr= 1
      loop until i = 0
   #endif
Next
print using "##.### seconds, badidea A     "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

' ************* badidea B *************
t=timer
For n as integer=1 to loops
   i=i0
   o=0
   bitNum = 0
   #if 0
      do
         c = i and 1 'least significant bit of i
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         i shr= 1
      loop until i = 0
   #else
      do
         c = i and 1 'least significant bit of i
         c = (c shl 1) or c 'duplicate lsb
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 2
         i shr= 1
      loop until i = 0
   #endif
Next
print using "##.### seconds, badidea B     "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

' ************* jj2007 *************
t=timer
For n as integer=1 to loops
   o=duplicate(i0)
Next
print using "##.### seconds, assembly      "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

'dodicat
t=timer
create(dbitters(),i0)
For n as integer=1 to loops
   o=dbitters(i0)
Next
print using "##.### seconds, lookup        "; timer-t;
print ", out: " & o & " - " & bin(o, 16)
'coder jeff
t=timer
For n as integer=1 to loops
   o= dup8bits(i0)
Next
print using "##.### seconds, coder jeff    "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

Dim As UByte Ln = Cubyte(Log(i0) / Log(2))
t=timer
For n as integer=1 to loops
   o= BitDupp(i0, Ln)
Next
print using "##.### seconds, UEZ           "; timer-t;
print ", out: " & o & " - " & bin(o, 16)
sleep

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 4 guests