It is currently Tue Jan 19, 2021 7:51 pm

All times are UTC + 1 hour




Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: jmp tables
PostPosted: Sun May 24, 2015 1:00 am 
Offline
Addict
Addict
User avatar

Joined: Fri Sep 21, 2007 5:52 am
Posts: 3556
Location: New Zealand
I'm curious to see if we can implement a jump table macro for PB as an alternative to using select / case
which results in a chain of if's that aren't particularly optimal if there's a lot of cases to wade through.
If the cases are serialized eg 0 to n, a jump table is a better option with O(1) worst case vs O(n) for selects worse case.
though any performance increase will likely be negligible in general useage.

This works on linux x64 and probably on x86 with fasm but I don't know if it'll work on OSX or Windows x64

Edit: changed to using lea and using a datasection


Code:
Macro JumpTable(table)
  DataSection
    ! table :
EndMacro     

CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
  Macro JumpTableData
  !dd
  EndMacro   
CompilerElse
  Macro JumpTableData
  !dq
  EndMacro   
CompilerEndIf

Macro Switch(table,switch)
  EndDataSection
  EnableASM
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    mov eax, switch
    jmp dword [ table + eax * 4]
  CompilerElse
   lea rdx, [ table ]
   mov rax,  switch
   jmp qword [rdx + rax * 8]
  CompilerEndIf
  DisableASM
EndMacro   

Macro caseJT(label,endlabel)
  !jmp endlabel
  ! label :
EndMacro   

Macro EndJumpTable(label)
  ! label :
EndMacro   


Procedure foo(a.i)
  Protected result
 
  JumpTable(jmp_table_foo)    ;define a jumptable
  JumpTableData le,l1,l2,l3   ;set the labels 0 offset 
 
  Switch(jmp_table_foo,a)     ;switch the table with the index 
    caseJT(l1,le)
      result = a * 10
    caseJT(l2,le)
      result = a * 20
    casejt(l3,le)
     result = a * 30
  EndJumpTable(le)
 
  ProcedureReturn result
 
EndProcedure   

Debug foo(2)  ;should return 40



Top
 Profile  
Reply with quote  
 Post subject: Re: jmp tables
PostPosted: Sun May 24, 2015 8:17 pm 
Offline
Addict
Addict

Joined: Fri Nov 09, 2012 11:04 pm
Posts: 1807
Location: Uttoxeter, UK
I tried it on Windows 7 x64 compiled with PureBasic 5.31 x64.

Gave this error:
POLINK: error: Relocation type ADDR32 is invalid without /LARGEADDRESSAWARE:NO, for symbol '.code'.

Clever idea: I do hope you get it working.

_________________
DE AA EB


Top
 Profile  
Reply with quote  
 Post subject: Re: jmp tables
PostPosted: Sun May 24, 2015 10:58 pm 
Offline
Addict
Addict
User avatar

Joined: Fri Sep 21, 2007 5:52 am
Posts: 3556
Location: New Zealand
thanks for that Davido

I've had another go at it, and rearranged it based on a solution wilbert sent me
it's a little messy but I don't think there's an easier alternative in PB 5.22
since it can't resolve pb labels in the procedure and datasection .

it looks like
Code:
Procedure foo(a.i)
  Protected result
 
  JumpTable(jmp_table_foo)    ;define a jumptable
  JumpTableData le,l1,l2,l3      ;set the jump labels 0 offset 
 
  Switch(jmp_table_foo,a)        ;switch the table to index 
    caseJT(l1,le)                        :switch case
      result = a * 10
    caseJT(l2,le)                         
      result = a * 20
    casejt(l3,le)
     result = a * 30
  EndJumpTable(le)
 
  ProcedureReturn result
 
EndProcedure   

Debug foo(2)  ;should return 40


Top
 Profile  
Reply with quote  
 Post subject: Re: jmp tables
PostPosted: Mon May 25, 2015 6:04 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3710
Location: Netherlands
Works fine now :)

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: jmp tables
PostPosted: Mon May 25, 2015 6:29 am 
Offline
Addict
Addict
User avatar

Joined: Fri Sep 21, 2007 5:52 am
Posts: 3556
Location: New Zealand
wilbert wrote:
Works fine now :)


Thanks, it'll only be marginally faster than a select, though it depends on what's being done.
If you had 20 cases you could expect at most a 20% speed up on average but otherwise it'd be negligible
unless it was constantly selects worst case, then it'd be 2 to 3 times faster.


Top
 Profile  
Reply with quote  
 Post subject: Re: jmp tables
PostPosted: Tue May 26, 2015 1:58 am 
Offline
Addict
Addict

Joined: Fri Apr 25, 2003 11:10 pm
Posts: 1232
idle
jump tables were popular in the 8-bit and 16-bit world, but I don't think they are a good idea in todays CPU's, have a look at this blog http://lolengine.net/blog/2011/9/17/pla ... u-pipeline


Top
 Profile  
Reply with quote  
 Post subject: Re: jmp tables
PostPosted: Tue May 26, 2015 7:12 am 
Offline
Addict
Addict
User avatar

Joined: Fri Sep 21, 2007 5:52 am
Posts: 3556
Location: New Zealand
I'd still think an optimizing compiler would produce a branch table over an if else switch if the boot fits.
it's just a case of consistency and quantity and a switch in it's worst case is slower than
a binary search which is slower than a jump table, even if it incurs a cache hit.
if you know it's quicker and the boot fits why wouldn't you use one?


Top
 Profile  
Reply with quote  
 Post subject: Re: jmp tables
PostPosted: Fri May 29, 2015 1:51 am 
Offline
Addict
Addict
User avatar

Joined: Thu Aug 07, 2003 7:01 pm
Posts: 3164
Location: United Kingdom
jmp tables will be faster than the case statements if you call procedures or any commands in the case statements - as they would also break the pipeline too on a mondern day cpu.

_________________
https://deluxepixel.com <- My Business website
https://reportcomplete.com <- School end of term reports system


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 1 guest


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