PureBasic Forums - English

Posted: **Sun Apr 10, 2016 2:57 am**

There was once a stupid trick using local lookup tables for direct conversion, via xlat, or modern equivalent.

You can build a 256 entry table mapping 8 bits to # of bits, and then do an xlat. It's only useful in stupid cases...and nothing else.
With a swap and an add, you can do 16. Duplicate for 32, etc. I don't know modern latencies for memory access, so it will probably be horribly slow. Also, setup is very slow, so it will only look better if you count performance after the table is built.

Even if it works, I will be surprised. But it was the fast way when processors were slower and fewer instructions.

Posted: **Sun Apr 10, 2016 12:44 pm**

I don't have a better assembler code which is clear because wilbert & co are doing the best job...

...but I just want to add two ideas how to it also possible to achieve a fine speed:
1) create tables (PopCount9a is as fast as the best routines above)
2) use macros (PopCount9b only needs 1/3 of the time)

Code: Select all

; Initialization
Global Dim pc9table.i($FFFF)
Global pc9
For pc9=0 To $FFFF
	pc9table(pc9)=PopCount0(pc9); any procedure you like here
Next pc9

Procedure.l PopCount9a (v.l)
	ProcedureReturn pc9table(v&$FFFF)+pc9table(v>>16)
EndProcedure
Macro PopCount9b (v)
	pc9table(v&$FFFF)+pc9table(v>>16)
EndMacro

Posted: **Sun Apr 10, 2016 7:08 pm**

Such tables also work well for trig, curves or "analog" functions.
The xlat/table thing was very handy for weighting in neural nets, fuzzy logic and weighted thresholds with multiple outputs.

Posted: **Wed Oct 05, 2016 10:43 pm**

Bo Marchais wrote:There was once a stupid trick using local lookup tables for direct conversion, via xlat, or modern equivalent. You can build a 256 entry table mapping 8 bits to # of bits, and then do an xlat. It's only useful in stupid cases...and nothing else.

I was interested in this stupid trick!

Code: Select all

Procedure.i GetBitCount(byte.a)
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
  ! mov rax, [p.v_byte]
  ! mov rdx, rbx
  ! mov rbx, BitCounts
  ! xlatb
  ! mov rbx, rdx
CompilerElseIf #PB_Compiler_Processor = #PB_Processor_x86
  ! mov eax, [p.v_byte]
  ! mov edx, ebx
  ! mov ebx, BitCounts
  ! xlatb
  ! mov ebx, edx
  CompilerEndIf
  ProcedureReturn
  DataSection
    !BitCounts:
    Data.a 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6
    Data.a 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7
    Data.a 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7
    Data.a 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8  
  EndDataSection  
EndProcedure

It performs very well, i used John's test from the first page of this thread, but doubled the amount of tests to make the results a bit clearer as they're all so fast:

Code: Select all

t0 = 36 ms     (10%)  <-- popcnt instruction
t1 = 350 ms   (100%)
t2 = 420 ms   (120%)
t3 = 1032 ms  (294%)
t4 = 1906 ms  (544%)
t5 = 1837 ms  (524%)
t6 = 1242 ms  (354%)
t7 = 57 ms     (16%)
t8 = 44 ms     (12%)  <-- this demo using xlatb

Posted: **Thu Oct 06, 2016 6:19 am**

@Keya, your x64 code didn't work on MacOS.
I had to change it into this using lea

Code: Select all

  ! mov rax, [p.v_byte]
  ! mov rdx, rbx
  ! lea rbx, [BitCounts]
  ! xlatb
  ! mov rbx, rdx

Lookups are fast but even faster without xlatb

Code: Select all

Procedure.i GetBitCount(byte.a)
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
    !movzx eax, byte [p.v_byte]
    !lea rdx, [BitCounts]
    !movzx eax, byte [rdx + rax]
  CompilerElseIf #PB_Compiler_Processor = #PB_Processor_x86
    !movzx eax, byte [p.v_byte]
    !movzx eax, byte [BitCounts + eax]
  CompilerEndIf
  ProcedureReturn
  DataSection
    !BitCounts:
    Data.a 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6
    Data.a 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7
    Data.a 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7
    Data.a 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8  
  EndDataSection  
EndProcedure

PureBasic Forums - English

Population count

Re: Population count

Re: Population count

Re: Population count

Re: Population count

Re: Population count