## 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

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 iResultEnd FunctionDim 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, -1073741824L0:  rol ecx, 2  shr edx, 1  je L1  jnc L0  or eax, ecx  jmp L0L1:  jnc Lx2  or eax, ecxLx2:  ret  end asmend functionFunction 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 Functionsub create(a() as longint,n as long=255) redim a(n) for i as long=0 to n a(i)=doublebitter(i) nextend subredim 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 asmend functionFunction 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 iResultEnd Functionclsdim as ubyte i, i0dim as ushort o = 0, c = 0input "Number 0-255: ", ii0=i   ' keep a copyprint "in: " & i & " - " & bin(i, 8)dim as integer bitNum = 0Dim as double t=timer#define loops 10000000'0print "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   #endifNextprint using "##.### seconds, badidea A     "; timer-t;print ", out: " & o & " - " & bin(o, 16)' ************* badidea B *************t=timerFor 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   #endifNextprint using "##.### seconds, badidea B     "; timer-t;print ", out: " & o & " - " & bin(o, 16)' ************* jj2007 *************t=timerFor n as integer=1 to loops   o=duplicate(i0)Nextprint using "##.### seconds, assembly      "; timer-t;print ", out: " & o & " - " & bin(o, 16)'dodicatt=timercreate(dbitters(),i0)For n as integer=1 to loops   o=dbitters(i0)Nextprint using "##.### seconds, lookup        "; timer-t;print ", out: " & o & " - " & bin(o, 16)'coder jefft=timerFor n as integer=1 to loops   o= dup8bits(i0)Nextprint using "##.### seconds, coder jeff    "; timer-t;print ", out: " & o & " - " & bin(o, 16)Dim As Single Ln = Cubyte(Log(i0) / Log(2)) + 1t=timerFor n as integer=1 to loops   o= BitDupp(i0, Ln)Nextprint 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

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

### Re: Bit duplication

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 iResultEnd 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, -1073741824L0:  rol ecx, 2  shr edx, 1  je L1  jnc L0  or eax, ecx  jmp L0L1:  jnc Lx2  or eax, ecxLx2:  ret  end asmend functionFunction 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 Functionsub create(a() as longint,n as long=255) redim a(n) for i as long=0 to n a(i)=doublebitter(i) nextend subredim 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 asmend functionFunction 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 iResultEnd Functionclsdim as ubyte i, i0dim as ushort o = 0, c = 0input "Number 0-255: ", ii0=i   ' keep a copyprint "in: " & i & " - " & bin(i, 8)dim as integer bitNum = 0Dim as double t=timer#define loops 100000000print "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   #endifNextprint using "##.### seconds, badidea A     "; timer-t;print ", out: " & o & " - " & bin(o, 16)' ************* badidea B *************t=timerFor 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   #endifNextprint using "##.### seconds, badidea B     "; timer-t;print ", out: " & o & " - " & bin(o, 16)' ************* jj2007 *************t=timerFor n as integer=1 to loops   o=duplicate(i0)Nextprint using "##.### seconds, assembly      "; timer-t;print ", out: " & o & " - " & bin(o, 16)'dodicatt=timercreate(dbitters(),i0)For n as integer=1 to loops   o=dbitters(i0)Nextprint using "##.### seconds, lookup        "; timer-t;print ", out: " & o & " - " & bin(o, 16)'coder jefft=timerFor n as integer=1 to loops   o= dup8bits(i0)Nextprint using "##.### seconds, coder jeff    "; timer-t;print ", out: " & o & " - " & bin(o, 16)Dim As UByte Ln = Cubyte(Log(i0) / Log(2))t=timerFor n as integer=1 to loops   o= BitDupp(i0, Ln)Nextprint using "##.### seconds, UEZ           "; timer-t;print ", out: " & o & " - " & bin(o, 16)sleep`