It is currently Mon Nov 30, 2020 6:36 pm

View unanswered posts | View active topics


Board index » PureBasic » Assembly Programming

All times are UTC + 1 hour




Post new topic Reply to topic  Page 3 of 3
  [ 36 posts ]  Go to page Previous  1, 2, 3
  Print view Previous topic | Next topic 
Author Message
Bo Marchais
 Post subject: Re: Population count
PostPosted: Sun Apr 10, 2016 2:57 am 
Offline
User
User

Joined: Sun Apr 03, 2016 12:03 am
Posts: 61
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.
Top
 Profile  
Reply with quote  
Michael Vogel
 Post subject: Re: Population count
PostPosted: Sun Apr 10, 2016 12:44 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Feb 09, 2006 11:27 pm
Posts: 2551
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:
; 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
Top
 Profile  
Reply with quote  
Bo Marchais
 Post subject: Re: Population count
PostPosted: Sun Apr 10, 2016 7:08 pm 
Offline
User
User

Joined: Sun Apr 03, 2016 12:03 am
Posts: 61
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.
Top
 Profile  
Reply with quote  
Keya
 Post subject: Re: Population count
PostPosted: Wed Oct 05, 2016 10:43 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 04, 2015 7:10 am
Posts: 1672
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:
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:
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

_________________
Thankyou to all the coders who generously helped & encouraged me in the nearly 2yrs when i was welcome here,
it was a tremendous privilege. I learned a lot. I wish you and your families all the best and success for the future.

Top
 Profile  
Reply with quote  
wilbert
 Post subject: Re: Population count
PostPosted: Thu Oct 06, 2016 6:19 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3706
Location: Netherlands
@Keya, your x64 code didn't work on MacOS.
I had to change it into this using lea
Code:
  ! mov rax, [p.v_byte]
  ! mov rdx, rbx
  ! lea rbx, [BitCounts]
  ! xlatb
  ! mov rbx, rdx


Lookups are fast but even faster without xlatb :wink:
Code:
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

_________________
macOS 10.15 Catalina, Windows 10

Top
 Profile  
Reply with quote  
davido
 Post subject: Re: Population count
PostPosted: Mon Jan 06, 2020 7:45 pm 
Offline
Addict
Addict

Joined: Fri Nov 09, 2012 11:04 pm
Posts: 1792
Location: Uttoxeter, UK
Deleted!!
Added in Error, Sorry.

_________________
DE AA EB

Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 3 of 3
  [ 36 posts ]  Go to page Previous  1, 2, 3

Board index » PureBasic » Assembly Programming

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 4 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye