jmp tables

Bare metal programming in PureBasic, for experienced users
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

jmp tables

Post by idle »

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: Select all

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

Windows 11, Manjaro, Raspberry Pi OS
Image
davido
Addict
Addict
Posts: 1890
Joined: Fri Nov 09, 2012 11:04 pm
Location: Uttoxeter, UK

Re: jmp tables

Post by davido »

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
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: jmp tables

Post by idle »

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: Select all

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
Windows 11, Manjaro, Raspberry Pi OS
Image
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: jmp tables

Post by wilbert »

Works fine now :)
Windows (x64)
Raspberry Pi OS (Arm64)
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: jmp tables

Post by idle »

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.
Windows 11, Manjaro, Raspberry Pi OS
Image
jack
Addict
Addict
Posts: 1336
Joined: Fri Apr 25, 2003 11:10 pm

Re: jmp tables

Post by jack »

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
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: jmp tables

Post by idle »

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?
Windows 11, Manjaro, Raspberry Pi OS
Image
User avatar
DoubleDutch
Addict
Addict
Posts: 3219
Joined: Thu Aug 07, 2003 7:01 pm
Location: United Kingdom
Contact:

Re: jmp tables

Post by DoubleDutch »

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
Post Reply