Disclaimer

Do not optimize without running your own benchmarks
first.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

1

Disclaimer

Do not optimize without running your own benchmarks
first.
My benchmarks: 2020 Apple Mac Mini (M1) running Asahi Linux and clang 14.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

1

Dispatch Loop

while (…){
switch (…){
case …: …
case …: …
…
}}

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-122Anti-Example: enum to string
enum class my_enum { … };const char* to_string(my_enum e){switch (e){using enum my_enum;case a:return "a";case b:return "b";…
}}Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-123Anti-Example (taken from work): Subset of enum
switch (viewType){case PowerPoint::ppViewSlideMaster:case PowerPoint::ppViewTitleMaster:case …:// Handle special view type.
…
break;
default:// Do nothing.
break;}

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-124Anti-Example (taken from work): Subset of enum
if (tc::is_subset(viewType,PowerPoint::ppViewSlideMaster | PowerPoint::ppViewTitleMaster | …)){// Handle special view type.
…
}

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-124Anti-Example (taken from work): Subset of enum
if (tc::is_subset(viewType,PowerPoint::ppViewSlideMaster | PowerPoint::ppViewTitleMaster | …)){// Handle special view type.
…
}

We’re hiring: think-cell.com/cppnow
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

4

Example: Parsing a binary file
while (auto header = parse_header(reader)){switch (header.type){case header_type::integer:parse_integer(reader);break;
case header_type::string:parse_string(reader, header.length);
break;…
}}
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

5

Canonical example: Bytecode interpreter
while (*ip != bytecode::exit){
switch (*ip){
case bytecode::add:…
case bytecode::push:…
…
}}

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

6

Simple stack-based bytecode

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

7

Simple stack-based bytecode
Bytecode: instructions are single byte op-codes or data.
enum class bytecode_op : std::uint8_t{…
};
union bytecode_inst{
bytecode_op

op;

std::uint8_t value;
std::int8_t

offset;};using bytecode = std::vector<bytecode_inst>;
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

8

Simple stack-based bytecode

Stack-based: instructions modify value stack (vstack).
bytecode_op::push: push constant in next byte onto the vstacka, b, c => a, b, c, 42
bytecode_op::add: pop two values from the vstack, push sum
a, b, c => a, (b+c)

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

9

Example: Sum 3 numbers

push 1;

vstack: 1

push 2;

vstack: 1, 2

add;

vstack: 3

push 3;

vstack: 3, 3

add;

vstack: 6

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

10

Stack operations

How to use the same value multiple times?

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

11

Stack operations

How to use the same value multiple times?
bytecode_op::dup: duplicate the value on top of the vstacka, b, c => a, b, c, cJonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

11

Stack operations

How to use the same value multiple times?
bytecode_op::dup: duplicate the value on top of the vstacka, b, c => a, b, c, c

What if values on the vstack are in the wrong order?

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

11

Stack operations

How to use the same value multiple times?
bytecode_op::dup: duplicate the value on top of the vstacka, b, c => a, b, c, c

What if values on the vstack are in the wrong order?
bytecode_op::swap: swap the two values on top of the vstacka, b, c => a, c, b

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

11

Control flow

Interpreter maintains instruction pointer (ip).
Normal instruction: increment ip past opcode plus data.
bytecode_op::jump: increment ip by offset specified in next byte.
bytecode_op::jump_if: increment ip by offset specified in next byte if top is non-zero.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

12

Function calls

For simplicity: only a single function allowed.
Arguments: pushed onto the vstack before call.
Return value: left on vstack after call.
bytecode_op::recurse: save ip, set ip to beginning of bytecode.
bytecode_op::return_: jump to saved ip.

ip saved in call stack (cstack).

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

13

Example: Recursive fibonacci
fib(n) = n < 2 ? n : fib(n-1) + fib(n-2)

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

14

Example: Recursive fibonacci
fib(n) = n < 2 ? n : fib(n-1) + fib(n-2)// if n < 2

vstack: ndup; push 2; cmp_ge;

vstack: n, (n >= 2)

jump_if 3;

vstack: n// return n
vstack: fib(n)return_;// return fib(n-1) + fib(n-2)
dup; push 1; sub; recurse;

vstack: n, fib(n-1)

swap; push 2; sub; recurse;

vstack: fib(n-1), fib(n-2)

add; return_;

vstack: fib(n)Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

14Interpreter State

using bytecode_ip = const bytecode_inst*;

bytecode_ip ip instruction pointerint* vstack_ptr vstack pointerbytecode_ip* cstack_ptr cstack pointerconst bytecode& bc bytecode

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

15

Execute instructions// push*vstack_ptr++ = ip[1].value;
ip += 2;Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

16

Execute instructions// push*vstack_ptr++ = ip[1].value;
ip += 2;// dupauto top = vstack_ptr[-1];*vstack_ptr++ = top;++ip;

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

16

Execute instructions// push*vstack_ptr++ = ip[1].value;
ip += 2;// dupauto top = vstack_ptr[-1];*vstack_ptr++ = top;++ip;// add (, sub, cmp_ge, …)
auto rhs= *--vstack_ptr;

auto lhs= *--vstack_ptr;*vstack_ptr++ = lhs + rhs;++ip;
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

16

Execute instructions// push// jump_if*vstack_ptr++ = ip[1].value;

auto condition = *--vstack_ptr;

ip += 2;if (condition != 0)
ip += ip[1].offset;// dupelse

auto top = vstack_ptr[-1];ip += 2;*vstack_ptr++ = top;++ip;// add (, sub, cmp_ge, …)
auto rhs= *--vstack_ptr;

auto lhs= *--vstack_ptr;*vstack_ptr++ = lhs + rhs;++ip;
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

16

Execute instructions// push// jump_if*vstack_ptr++ = ip[1].value;

auto condition = *--vstack_ptr;

ip += 2;if (condition != 0)
ip += ip[1].offset;// dupelse

auto top = vstack_ptr[-1];ip += 2;*vstack_ptr++ = top;++ip;// recurse*cstack_ptr++ = ip + 1;// add (, sub, cmp_ge, …)
auto rhs= *--vstack_ptr;

auto lhs= *--vstack_ptr;

ip = bc.data();*vstack_ptr++ = lhs + rhs;++ip;
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

16

Execute instructions// push// jump_if*vstack_ptr++ = ip[1].value;

auto condition = *--vstack_ptr;

ip += 2;if (condition != 0)
ip += ip[1].offset;// dupelse

auto top = vstack_ptr[-1];ip += 2;*vstack_ptr++ = top;++ip;// recurse*cstack_ptr++ = ip + 1;// add (, sub, cmp_ge, …)
auto rhs= *--vstack_ptr;

auto lhs= *--vstack_ptr;*vstack_ptr++ = lhs + rhs;

ip = bc.data();// returnip = *--cstack_ptr;++ip;Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

16Interpreter
int execute(const bytecode& bc, int argument){
int

vstack[vstack_size];

bytecode_ip cstack[cstack_size];
bytecode_ip ip= bc.data();

auto vstack_ptr = &vstack[0];auto cstack_ptr = &cstack[0];*cstack_ptr++ = &exit_instruction;*vstack_ptr++ = argument;
return dispatch(ip, vstack_ptr, cstack_ptr, bc);}
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

17

Missing piece

int dispatch(bytecode_ip ip, int* vstack_ptr, bytecode_ip* cstack_ptr,
const bytecode& bc);

Read ip->op.
Execute appropriate body and increment ip.
Repeat until exit instruction.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

18

Aside: Safety

Bytecode interpreters are prime candidates for remote code execution exploits.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

19

Aside: Safety

Bytecode interpreters are prime candidates for remote code execution exploits.

NEVER start executing untrusted, unverified bytecode.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

19

Dispatch Technique #0: switch

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

20

Idea: switch over opcode
while (true){
switch (ip->op){case bytecode_op::push:…
case bytecode_op::add:…
case bytecode_op::exit:
return *--vstack_ptr;}}
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

21

Idea: switch over opcode
while (true){
switch (ip->op){case bytecode_op::push:…
case bytecode_op::add:…
case bytecode_op::exit:
return *--vstack_ptr;
default:__builtin_unreachable();}}Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

21

Interlude: AArch64 Assembly
Registers
General purpose registers: r0-r30
x0-x30 64-bit access
w0-w30 32-bit access (lower half)

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

22Interlude: AArch64 Assembly
Registers
General purpose registers: r0-r30
x0-x30 64-bit access
w0-w30 32-bit access (lower half)

Addressing modes[x0] (indirect) address stored in x0[x0, #42] (offset) address stored in x0 offset by 42

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

22Interlude: AArch64 Assembly
Registers
General purpose registers: r0-r30
x0-x30 64-bit access
w0-w30 32-bit access (lower half)

Addressing modes[x0] (indirect) address stored in x0[x0, #42] (offset) address stored in x0 offset by 42[x0, #42]! (pre-increment) increment x0 by 42, then address stored in x0[x0], #42 (post-increment) address stored in x0, then increment x0 by 42

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

22Interlude: AArch64 Assembly
Registers
General purpose registers: r0-r30
x0-x30 64-bit access
w0-w30 32-bit access (lower half)

Addressing modes[x0] (indirect) address stored in x0[x0, #42] (offset) address stored in x0 offset by 42[x0, #42]! (pre-increment) increment x0 by 42, then address stored in x0[x0], #42 (post-increment) address stored in x0, then increment x0 by 42[x0, x1, lsl 3] (index) address stored in x0 offset by x1 << 3Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

22

Generated assembly.loop:
ldrb w8, [x0] ; w8 := ip->op
cmp

w8, #0; w8 == bytecode_op::push?

b.eq .push; then: goto pushcmp

; w8 == bytecode_op::add

w8, #1b.eq .add; then: goto add…
b .exit; else: goto exit

.push:.exit:

ldrb w8, [x0, #1]

ldur w0, [x1, #-4]

str

w8, [x1], #4

ret

add

x0, x0, 2

b .loop
Jonathan Müller — @foonathan; exit loop

; goto loop
A deep dive into dispatching techniques

C++Now

2023-05-12

23

Actual generated “assembly”
if (ip->op < 4) // 0-3{
if (ip->op <= 1)// 0-1{
if (ip->op == 0)
goto push;elsegoto add;}else // 2-3
{
…
}
}
else
{
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

24

Benchmark
Measure the time for fib(35).

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

25

Benchmark
Measure the time for fib(35).

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

25

Benchmark
Measure the time for fib(35).

Is that fast?
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

25

Aside: How to benchmark

1
2
3

Take multiple runs.
Report average and standard deviation.
Compare against some alternative implementation (!).

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1226

hyperfine
A command-line benchmarking tool.

github.com/sharkdp/hyperfine
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

27

How to Optimize

1

Guess a problem

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1228

Interlude: CPU instruction pipeline
Simplified

Assembly instruction execution happens inphases.
1
Fetch: fetch memory of the next
instruction
2
Decode: figure out what the next
instruction is
3
Execute: actually execute theinstruction
4
Write-back: write the results intomemoryJonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1229

Interlude: CPU instruction pipeline
Simplified

Assembly instruction execution happens inphases.
1
Fetch: fetch memory of the next
instruction
2
Decode: figure out what the next
instruction is
3
Execute: actually execute theinstruction
4
Write-back: write the results intomemoryThis is done in parallel.
By en:User:Cburnett - This W3C-unspecified vector image was created with Inkscape.,
CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1499754

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1229

Interlude: CPU branch prediction
Simplified

Idea: predict which branch is taken and start processing its assembly instruction.

Correct prediction: efficient use of the pipeline.
Incorrect prediction: pipeline has to be cleared, rolled back → expensive.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1230

Interlude: CPU branch prediction
Simplified

Idea: predict which branch is taken and start processing its assembly instruction.

Correct prediction: efficient use of the pipeline.
Incorrect prediction: pipeline has to be cleared, rolled back → expensive.
As such: remember history for branches to predict correctly.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1230

Interlude: CPU branch prediction
Simplified

Idea: predict which branch is taken and start processing its assembly instruction.

Correct prediction: efficient use of the pipeline.
Incorrect prediction: pipeline has to be cleared, rolled back → expensive.
As such: remember history for branches to predict correctly.
But: we’re executing different bytecode ops in each iteration.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1230

How to Optimize

1

Guess a problem

2

Measure to verify guess

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

31

Branch misses
perf stat: query hardware performance counters$ perf stat -e branches,branch-misses ./vm_switch.out

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

32

Branch misses
perf stat: query hardware performance counters$ perf stat -e branches,branch-misses ./vm_switch.out

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

32

Branch misses
perf stat: query hardware performance counters$ perf stat -e branches,branch-misses ./vm_switch.out

Is that a lot?
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

32

How to Optimize

1

Guess a problem

2

Measure to verify guess

3

Workaround problem

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

33

Dispatch Technique #1: Call threading 1

1

It has nothing to do with threads.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

34

Idea: Array of function pointersvoid do_execute_push(bytecode_ip& ip, int*& vstack_ptr,
bytecode_ip*& cstack_ptr, const bytecode& bc) { … }void do_execute_add(bytecode_ip& ip, int*& vstack_ptr,
bytecode_ip*& cstack_ptr, const bytecode& bc) { … }constexpr std::array execute_table= {&do_execute_push, &do_execute_add, …};
while (ip->op != bytecode_op::exit){
execute_table[int(ip->op)](ip, vstack_ptr, cstack_ptr, bc);}

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

35

Generated assembly; setup omitted.loop:
add x0, sp, #24; x0 := &ip

add x1, sp, #16; x1 := &vstack_ptr

add x2, sp, #8; x2 := &cstack_ptr

mov x3, x19; x3 := bc

ldr x8, [x20, w8, lsl #3] ; x8 := &execute_table[int(ip->op)]
blr x8; x8()

ldrb w8, [sp, #24]

; w8 := ip->op

cmp w8, #9; w8 == bytecode_op::exit?

b.ne .loop; exit omitted
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

36

Benchmark

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

37

Aside: How to create bad graphs

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

38

Benchmark

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

39

Benchmark

Memory overhead.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

39

Generated assembly of execute functions
Call-by-value
do_execute_push:
ldrb

w8, [x0, #1]

str

w8, [x1], #4

addx0, x0, #2

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

40

Generated assembly of execute functions
Call-by-value

Call-by-reference

do_execute_push:

do_execute_push:

ldrb

w8, [x0, #1]

str

w8, [x1], #4

addx0, x0, #2

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

ldr

x8, [x0]

ldrb

w8, [x8, #1]

ldr

x9, [x1]

str

w8, [x9], #4

strx9, [x1]

ldr

x8, [x0]

add

x8, x8, #2

str

x8, [x0]

C++Now

2023-05-12

40

Generated assembly of execute functions
Call-by-value

Call-by-reference

do_execute_push:

do_execute_push:

ldrb

w8, [x0, #1]

str

w8, [x1], #4

addx0, x0, #2

ldr

x8, [x0]

ldrb

w8, [x8, #1]

ldr

x9, [x1]

str

w8, [x9], #4

strx9, [x1]

ldr

x8, [x0]

add

x8, x8, #2

str

x8, [x0]

CPU can only work on register values.
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

40

How to Optimize

1

Guess a problem

2

Measure to verify guess

3

Workaround problem

4

Repeat 3 if necessary

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

41

Dispatch Technique #2: Token threading22

Sometimes imprecisely referred to as indirect threading.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1242

GNU Extension: Computed goto
Normal goto
Label a statement:label: foo;
goto label:goto label;

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

43

GNU Extension: Computed goto
Normal goto
Label a statement:label: foo;
goto label:goto label;Computed goto
Take address of label:
void* label_addr = &&label;goto label by dereferencing its address:
goto *label_addr;

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

43

Idea: Array of labels (jump table)
constexpr std::array execute_table = {&&do_execute_push, &&do_execute_add, …};
while (true){
goto *execute_table[int(ip->op)];
do_execute_push:…
continue;
do_execute_add:…
continue;…
do_execute_exit:
break;}
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

44

Generated assembly.loop:
ldrb w9, [x0]; w9 := ip->op

ldr

x9, [x8, x9, lsl #3]; x9 := execute_table[w9]brx9; goto.do_execute_push:…
addx0, x0, 2

br .loop ; continue.do_execute_add:…
addx0, x0, 1

br .loop ; continue…
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

45

Actual generated assembly
ldrb w9, [x0]; w9 := ip->op

ldr

x9, [x8, x9, lsl #3]; x9 := execute_table[w9]brx9; goto.do_execute_push:…
ldrb w9, [x0, #2]!

; ip += 2; w9 := ip->op

ldr

x9, [x8, x9, lsl #3]; x9 := execute_table[w9]brx9; goto.do_execute_add:…
ldrb w9, [x0, #1]!

; ip += 1; w9 := ip->op

ldr

x9, [x8, x9, lsl #3]; x9 := execute_table[w9]brx9; gotoJonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

46

Canonical token threaded dispatch implementation
constexpr std::array execute_table = {&&do_execute_push, &&do_execute_add, …};goto *execute_table[int(ip->op)];
do_execute_push:…
goto *execute_table[int(ip->op)];
do_execute_add:…
goto *execute_table[int(ip->op)];…

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

47

Benchmark

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1248

That’s still a branch

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1249

Duplicated dispatch code

switch dispatch:Single dispatch for all bytecode instruction
handlers.
Single location for branch prediction.
Can only learn about common bytecode
instructions.

Jonathan Müller — @foonathan

Threaded dispatch:

A deep dive into dispatching techniques

Separate dispatch after each bytecode
instruction handler.
Separate locations for branch prediction.
Can learn what bytecode instruction
usually follows.

C++Now

2023-05-1250

Let’s figure out what’s still slow
$ perf record ./vm_token_threading.out

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

51

Let’s figure out what’s still slow
$ perf record ./vm_token_threading.out$ perf report
Overhead

Shared Object

Symbol........

.........................

......................

99.85%

vm_token_threading.out[.] dispatch

0.10%

ld-linux-aarch64.so.1[.] _dl_lookup_symbol_x

0.04%

ld-linux-aarch64.so.1[.] do_lookup_x

0.00%

ld-linux-aarch64.so.1[.] copy_hwcaps

0.00%

ld-linux-aarch64.so.1[.] _dl_start

0.00%

ld-linux-aarch64.so.1[.] _start

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

51

Wishlist

Separate functions for executing bytecode instructions.
No memory overhead.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

52

Dispatch Technique #2.5: Token-threaded dispatch with tailcalls

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1253

Idea: Each bytecode instruction handler calls next handle
constexpr std::array execute_table = {&do_execute_push, &do_execute_add, …};
int do_execute_push(bytecode_ip ip, int* vstack_ptr,
bytecode_ip* cstack_ptr, const bytecode& bc){…
return execute_table[int(ip->op)](ip, vstack_ptr, cstack_ptr, bc);}
int do_execute_add(bytecode_ip ip, int* vstack_ptr,
bytecode_ip* cstack_ptr, const bytecode& bc){…
return execute_table[int(ip->op)](ip, vstack_ptr, cstack_ptr, bc);}
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

54

Call stack
Call pushes program counter (PC) and jumps to label, return pops and jumps back.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

55

Call stack
Call pushes program counter (PC) and jumps to label, return pops and jumps back.
dispatch

Jonathan Müller — @foonathan

1

A deep dive into dispatching techniques

Push PC.

C++Now

2023-05-12

55

Call stack
Call pushes program counter (PC) and jumps to label, return pops and jumps back.
dispatch
do_execute_dup

Jonathan Müller — @foonathan

123

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.

C++Now

2023-05-12

55

Call stack
Call pushes program counter (PC) and jumps to label, return pops and jumps back.
dispatch
do_execute_dup
do_execute_push

1
2
3
4
5

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.
Jump to second execute.
Push PC.

C++Now

2023-05-12

55

Call stack
Call pushes program counter (PC) and jumps to label, return pops and jumps back.
dispatch
do_execute_dup

123

do_execute_push

4

…

5
6

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.
Jump to second execute.
Push PC.
…

C++Now

2023-05-12

55

Call stack
Call pushes program counter (PC) and jumps to label, return pops and jumps back.
dispatch
do_execute_dup

123

do_execute_push

4

…

5
6

do_execute_exit

78Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.
Jump to second execute.
Push PC.
…
Jump to final execute.
Push PC.

C++Now

2023-05-12

55

Call stack
Call pushes program counter (PC) and jumps to label, return pops and jumps back.
dispatch
do_execute_dup

123

do_execute_push

4

…

5
6
7
8
7

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.
Jump to second execute.
Push PC.
…
Jump to final execute.
Push PC.
Pop PC and jump back.

C++Now

2023-05-12

55

Call stack
Call pushes program counter (PC) and jumps to label, return pops and jumps back.
dispatch
do_execute_dup
do_execute_push

1
2
3
4
5
6
7
8
7
7

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.
Jump to second execute.
Push PC.
…
Jump to final execute.
Push PC.
Pop PC and jump back.
Pop PC and jump back.

C++Now

2023-05-12

55

Call stack
Call pushes program counter (PC) and jumps to label, return pops and jumps back.
dispatch
do_execute_dup

1
2
3
4
5
6
7
8
7
7
8

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.
Jump to second execute.
Push PC.
…
Jump to final execute.
Push PC.
Pop PC and jump back.
Pop PC and jump back.
Pop PC and jump back.

C++Now

2023-05-12

55

Call stack
Call pushes program counter (PC) and jumps to label, return pops and jumps back.
dispatch

1
2
3
4
5
6
7
8
7
7
8
9

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.
Jump to second execute.
Push PC.
…
Jump to final execute.
Push PC.
Pop PC and jump back.
Pop PC and jump back.
Pop PC and jump back.
Pop PC and jump back.

C++Now

2023-05-12

55

Actual call stack

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

56

Actual call stackdispatch

Jonathan Müller — @foonathan

1

A deep dive into dispatching techniques

Push PC.

C++Now

2023-05-12

56

Actual call stackdispatch
do_execute_dup

Jonathan Müller — @foonathan

123

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.

C++Now

2023-05-12

56

Actual call stackdispatch
do_execute_dup
do_execute_push

1
2
3
4
5

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.
Jump to second execute.
Push PC.

C++Now

2023-05-12

56

Actual call stackdispatch
do_execute_dup

123

do_execute_push

4

…

5
6

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.
Jump to second execute.
Push PC.
…

C++Now

2023-05-12

56

Actual call stackdispatch
do_execute_dup

123

do_execute_push

4

…

5
6

Stack overflow

Jonathan Müller — @foonathan

7

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Push PC.
Jump to second execute.
Push PC.
…
Stack overflow.

C++Now

2023-05-12

56

Tail call optimization

If a function ends with return foo();, just jump there without push.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

57

Tail call optimization

If a function ends with return foo();, just jump there without push.
dispatch

Jonathan Müller — @foonathan

1

A deep dive into dispatching techniques

Push PC.

C++Now

2023-05-12

57

Tail call optimization

If a function ends with return foo();, just jump there without push.
dispatch
do_execute_dup

Jonathan Müller — @foonathan

12

A deep dive into dispatching techniques

Push PC.
Jump to first execute.

C++Now

2023-05-12

57

Tail call optimization

If a function ends with return foo();, just jump there without push.
dispatch
do_execute_push

Jonathan Müller — @foonathan

123

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Jump to second execute.

C++Now

2023-05-12

57

Tail call optimization

If a function ends with return foo();, just jump there without push.
dispatch
…

1
2
3
4

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Jump to second execute.
…

C++Now

2023-05-12

57

Tail call optimization

If a function ends with return foo();, just jump there without push.
dispatch
do_execute_exit

1
2
3
4
5

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Jump to second execute.
…
Jump to final execute.

C++Now

2023-05-12

57

Tail call optimization

If a function ends with return foo();, just jump there without push.
dispatch

1
2
3
4
5
6

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

Push PC.
Jump to first execute.
Jump to second execute.
…
Jump to final execute.
Pop PC and jump back to caller.

C++Now

2023-05-12

57

clang Extension: [[clang::musttail]]

https://clang.llvm.org/docs/AttributeReference.html#musttail
If a return statement is marked musttail, this indicates that the compiler must generatea tail call for the program to be correct, even when optimizations are disabled. Thisguarantees that the call will not cause unbounded stack growth if it is part of a recursive
cycle in the call graph.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

58

Idea: Each bytecode instruction handler tail calls the next handler
constexpr std::array execute_table = {&do_execute_push, &do_execute_add, …};
int do_execute_push(bytecode_ip ip, int* vstack_ptr,
bytecode_ip* cstack_ptr, const bytecode& bc){…
[[clang::musttail]] return execute_table[int(ip->op)](ip, vstack_ptr, cstack_ptr, bc);}
int do_execute_add(bytecode_ip ip, int* vstack_ptr,
bytecode_ip* cstack_ptr, const bytecode& bc){…
[[clang::musttail]] return execute_table[int(ip->op)](ip, vstack_ptr, cstack_ptr, bc);}
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

59

Generated assembly
dispatch:
adrp x8, execute_tableadd

x8, x8, :lo12:execute_table ; x8 := execute_table

ldrb w9, [x0]; w9 := ip->op

ldr

x9, [x8, x9, lsl #3]; x9 := x8[w9]brx9; tail call

do_execute_push:…
adrp x8, execute_tableadd

x8, x8, :lo12:execute_table ; x8 := execute_table

ldrb w9, [x0, #2]!

; ip += 2; w9 := ip->op

ldr

x9, [x8, x9, lsl #3]; x9 := x8[w9]brx9; tail call

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

60

Benchmark

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

61

Branch misses

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

62

Let’s figure out what’s still slow
$ perf record ./vm_token_tail_call.out$ perf report
Overhead

Shared Object

Symbol........

.........................

......................

15.97%

vm_token_tail_call.out[.] do_execute_push

15.21%

vm_token_tail_call.out[.] do_execute_add

12.74%

vm_token_tail_call.out[.] do_execute_sub

12.58%

vm_token_tail_call.out[.] do_execute_dup

9.91%

vm_token_tail_call.out[.] do_execute_cmp_ge

9.64%

vm_token_tail_call.out[.] do_execute_jump_if

9.30%

vm_token_tail_call.out[.] do_execute_recurse

8.98%

vm_token_tail_call.out[.] do_execute_return_

5.57%

vm_token_tail_call.out[.] do_execute_swap

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

63Interlude: register keyword

Dear C compiler, please keep this variable in a register.
register bytecode_ip ip;
register int* vstack_ptr;
register bytecode_ip* cstack_ptr;// Interpreter loop here.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

64Interlude: register keyword

Dear C compiler, please keep this variable in a register.
register bytecode_ip ip;
register int* vstack_ptr;
register bytecode_ip* cstack_ptr;// Interpreter loop here.

Modern compilers do it for you.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

64Interlude: register keyword

Dear C compiler, please keep this variable in a register.
register bytecode_ip ip;
register int* vstack_ptr;
register bytecode_ip* cstack_ptr;// Interpreter loop here.

Modern compilers do it for you.
Except when they don’t.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

64Why LuaJIT’s interpreter is written in assembly

Mike Pall, http://lua-users.org/lists/lua-l/2011-02/msg00742.html
We can use a direct or indirect-threaded interpreter even in C, e.g. with the computed ‘goto&’ feature of GCC. […] This effectively replicates the load and the dispatch, which helps the
CPU branch predictors. But it has its own share of problems: […] The register allocator
can only treat each of these segments separately and will do a real bad job. There’s
just no way to give it a goal function like “I want the same register assignment before eachgoto”.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

65Interlude: Calling convention
Simplified

Function call: jump to address.

How are arguments passed?

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

66

Interlude: Calling convention
Simplified

Function call: jump to address.

How are arguments passed?

Calling convention for AArch64
x0 to x7: Argument values
x9 to x15: Local variables (caller saved).
x19 tox29: Local variables (callee saved).

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

66

Calling convention forces register assignment
Want something in a register? Pass it as argument.
int do_execute_push(bytecode_ip ip, int* vstack_ptr,
bytecode_ip* cstack_ptr, const bytecode& bc){…
}
do_execute_push:
ldrb

w8, [x0, #1]

str

w8, [x1], #4

adrp

x9, execute_tableadd

x9, x9, :lo12:execute_table

ldrb

w8, [x0, #2]!

ldr

x4, [x9, x8, lsl #3]

brx4

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

67

Calling conventions

Standard calling convention
AArch64: 8 registers for arguments
x86_64 Linux: 6 registers for arguments
x86_64 Windows: 4 registers for arguments

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

68

Calling conventions

Standard calling convention
AArch64: 8 registers for arguments
x86_64 Linux: 6 registers for arguments
x86_64 Windows: 4 registers for arguments
We can use a custom calling convention!

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

68

Calling conventions

Standard calling convention
AArch64: 8 registers for arguments
x86_64 Linux: 6 registers for arguments
x86_64 Windows: 4 registers for arguments
We can use a custom calling convention!

[[gnu::regcall]] : Pass as many arguments as possible in registers.
AArch64: ignored
x86_64 Linux: 12 registers for arguments
x86_64 Windows: 11 registers for arguments

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

68

The fast and slow path

Mike Pall, http://lua-users.org/lists/lua-l/2011-02/msg00742.html
If you write an interpreter loop in assembler, you can do much better:
Keep a fixed register assignment for all [bytecode] instructions.
Keep everything in registers for the fast paths. Spill/reload only in the slow paths.
Move the slow paths elsewhere, to help with I-Cache density.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

69

Interlude: I-Cache
Simplified

Assembly instructions are stored in memory.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1270Interlude: I-Cache
Simplified

Assembly instructions are stored in memory.
Memory access is slow.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1270Interlude: I-Cache
Simplified

Assembly instructions are stored in memory.
Memory access is slow.
Special cache for instructions: I-cache.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-1270Interlude: I-Cache
Simplified

Assembly instructions are stored in memory.
Memory access is slow.
Special cache for instructions: I-cache.
But: don’t pollute it with cold code.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

70

A bytecode instruction with a slow pathbytecode_op::print42: print the top value if it is 42
x => xint do_execute_print42(bytecode_ip ip, int* vstack_ptr,
bytecode_ip* cstack_ptr, const bytecode& bc){
if (vstack_ptr[0] == 42)
std::puts("42");++ip;[[clang::musttail]] return execute_table[int(ip->op)](ip, vstack_ptr, cstack_ptr, bc);}

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

71

Benchmark
fib(35): once with initial print42, once without.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

72

Benchmark
fib(35): once with initial print42, once without.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

72

Benchmark
fib(35): once with initial print42, once without.

4ms slower.
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

72

Generated assembly.LBB1_2:

do_execute_print42:
stp

x29, x30, [sp, #-48]!

ldrb

w8, [x22, #1]!

stp

x22, x21, [sp, #16]

adrp

x9, execute_table

mov

x29, spmov

x0, x22stp

x20, x19, [sp, #32]

add

x9, x9, :lo12:execute_table

ldr

w8, [x1]

mov

x1, x21mov

x19, x3

mov

x2, x20mov

x20, x2

mov

x3, x19mov

x21, x1

ldp

x20, x19, [sp, #32]

movx22, x0

ldp

x22, x21, [sp, #16]

cmp

w8, #42ldr

x4, [x9, x8, lsl #3]

b.ne.LBB1_2

ldp

x29, x30, [sp], #48

adrpx0, .L.str

br

x4

add

x0, x0, :lo12:.L.str

bl

puts

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

73

Hoist the slow path
int do_execute_print42(bytecode_ip ip, int* vstack_ptr,
bytecode_ip* cstack_ptr, const bytecode& bc){
if (vstack_ptr[0] == 42)[[clang::musttail]] return do_print_impl(…);++ip;[[clang::musttail]] return execute_table[int(ip->op)](…);}[[gnu::noinline]] int do_print_impl(bytecode_ip ip, int* vstack_ptr,
bytecode_ip* cstack_ptr, const bytecode& bc){
std::puts("42");++ip;[[clang::musttail]] return execute_table[int(ip->op)](…);}
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

74

Generated assembly
do_execute_print42:
ldr

w8, [x1]

cmp

w8, #42b.ne.LBB1_2b

do_print_impl.LBB1_2:
ldrb

w8, [x0, #1]!

adrp

x9, execute_tableadd

x9, x9, :lo12:execute_table

ldr

x4, [x9, x8, lsl #3]

brx4

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

75

Benchmark

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

76

You can’t actually return!
int do_execute_recurse(bytecode_ip ip, int* vstack_ptr,
bytecode_ip* cstack_ptr, const bytecode& bc){
if (*cstack_ptr == END_OF_CALL_STACK)[[clang::musttail]] return grow_call_stack(…);*cstack_ptr++ = ip + 1;
ip

= bc.data();[[clang::musttail]] return execute_table[int(ip->op)](…);}[[gnu::noinline]] int grow_call_stack(bytecode_ip ip, int* vstack_ptr,
bytecode_ip* cstack_ptr, const bytecode& bc){
cstack_ptr = allocate_bigger_and_copy_old(cstack_ptr);[[clang::musttail]] return do_execute_recurse(…);}
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

77

Conclusion?

[[clang::musttail]] enables threading via function calls:

Detailed performance tracking in perf record
Force the compiler to use a particular register assignment
Remember to hoist slow paths; no regular function calls in the hot code

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

78

Conclusion?

[[clang::musttail]] enables threading via function calls:

Detailed performance tracking in perf record
Force the compiler to use a particular register assignment
Remember to hoist slow paths; no regular function calls in the hot code

Trick the compiler into generating the exact assembly you
want.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

78

Let’s benchmark on my old laptop

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

79

Benchmarks
New benchmarks: 2016 Thinkpad 13 running Arch Linux and clang 14.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

80

Benchmarks
New benchmarks: 2016 Thinkpad 13 running Arch Linux and clang 14.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

80

Benchmarks
New benchmarks: 2016 Thinkpad 13 running Arch Linux and clang 14.

... Uhm?
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

80

Branch misses!

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

81Interlude: Branch target prediction
Simplified
Conditional branch, fixed target:

Unconditional branch, variable target:
adrp

x9, execute_table

ldrb w8, [x0]addx9, x9, :lo12:execute_table

cmp

w8, #0ldr

x4, [x9, x8, lsl #3]

b.eq .pushbrx4.loop:

cmp

w8, #1b.eq .add…
b .exitJonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

82Interlude: Branch target prediction
Simplified
Conditional branch, fixed target:

Unconditional branch, variable target:
adrp

x9, execute_table

ldrb w8, [x0]addx9, x9, :lo12:execute_table

cmp

w8, #0ldr

x4, [x9, x8, lsl #3]

b.eq .pushbrx4.loop:

cmp

w8, #1b.eq .add…
b .exitBranch target prediction: determine where a branch is going.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

82

Workaround bad branch target prediction[[clang::musttail]] return execute_table[int(ip->op)](…);

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

83Workaround bad branch target prediction[[clang::musttail]] return execute_table[int(ip->op)](…);
switch (ip->op){case bytecode_op::push:[[clang::musttail]] return do_execute_push(…);
case bytecode_op::add:[[clang::musttail]] return do_execute_add(…);…
default:__builtin_unreachable();}Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

83Branch misses

2016 Thinkpad 13 running Arch Linux and clang 14.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

84

Benchmark
2016 Thinkpad 13 running Arch Linux and clang 14.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

85

Conclusion?

Trust the compiler to do dispatching, it knows best.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

86Actual generated assembly for a switch
if (ip->op < 4) // 0-3{
if (ip->op <= 1)// 0-1{
if (ip->op == 0)
goto push;elsegoto add;}else // 2-3
{
…
}
}
else
{
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

87Actual actual generated assembly for a switch.loop:
ldrb

w8, [x23]

adr

x9, .push

ldrb

w10, [x24, x8]

addx9, x9, x10, lsl #2

brx9.push:…
.add:…

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

88Actual actual generated assembly for a switch.loop:
ldrb

w8, [x23]

adr

x9, .push

ldrb

w10, [x24, x8]

addx9, x9, x10, lsl #2

brx9.push:…
.add:…

That’s a jump table.
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

88

Benchmarks
New new benchmarks: 2021 Thinkpad X1 Carbon (Intel® Core™ i5-1145G7) running Arch Linuxand clang 15.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

89

Benchmarks
New new benchmarks: 2021 Thinkpad X1 Carbon (Intel® Core™ i5-1145G7) running Arch Linuxand clang 15.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

89

Generated assembly on x86_64
Manual jump table
movzx

eax, byte ptr [rbx]; rax := ip->op

jmp

qword ptr [r13 + 8*rax]; goto *execute_table[rax]Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

90Generated assembly on x86_64
Manual jump table
movzx

eax, byte ptr [rbx]; rax := ip->op

jmp

qword ptr [r13 + 8*rax]; goto *execute_table[rax]Switch jump table
movzx

eax, byte ptr [rbx]; rax := ip->op

movsxdrax, dword ptr [r13 + 4*rax]; rax := execute_table[rax]addrax, r13; rax := rax + &execute_table

jmp

rax

; gotoJonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

90Generated assembly on x86_64
Manual jump table
movzx

eax, byte ptr [rbx]; rax := ip->op

jmp

qword ptr [r13 + 8*rax]; goto *execute_table[rax]Switch jump table
movzx

eax, byte ptr [rbx]; rax := ip->op

movsxdrax, dword ptr [r13 + 4*rax]; rax := execute_table[rax]addrax, r13; rax := rax + &execute_table

jmp

rax

; gotoCompiler generates jump table with 4 byte relative offsets, not 8 byte absolute offsets.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

90

Conclusion???

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

91

Conclusion???
Benchmark on the target hardware, then optimize.

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

91Advanced dispatch techniques

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

92Token-threaded dispatch
Computed goto

Tail calls

enum class bytecode_op

enum class bytecode_op

{

{
push,

push,

…

…
};

};

std::array execute_table

std::array execute_table= {&do_execute_push, …};= {&&do_execute_push, …};

int do_execute_push(…) {do_execute_push:…

…

return execute_table[ip->op](…);

goto *execute_table[ip->op];}
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

93

Direct-threaded dispatch
Computed goto

Tail calls

namespace bytecode_op

namespace bytecode_op{{
int push(…);

void* push;

…

…
}

}
do_execute_push:int bytecode_op::push(…) {…

…

return ip(…);

goto *ip;}

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

94

Generated assembly

do_execute_push:
ldrb

w8, [x0, #8]

strw8, [x1], #4

ldrx4, [x0, #16]!

brx4

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

95

Direct-threaded dispatch

Pro best dispatch code so far

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

96

Direct-threaded dispatch

Pro best dispatch code so far
Con
Opcode is 64-bit
Requires branch target prediction
Trivial remote code execution exploits possible

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

96Inline-threaded dispatch// 1 + 2
push 1;

push 2;

add;

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

97

Inline-threaded dispatch// 1 + 2
push 1;

push 2;

add;

Jonathan Müller — @foonathan

ldrb

w8, [x0, #1]

str

w8, [x1], #4

addx0, x0, #2

ldrb

w8, [x0, #1]

str

w8, [x1], #4

addx0, x0, #2

ldr

w8, [x1, #-4]!

ldur

w9, [x1, #-4]

add

w8, w9, w8

stur

w8, [x1, #-4]

addx0, x0, #1

A deep dive into dispatching techniques

C++Now

2023-05-12

97

Inline-threaded dispatch// 1 + 2
push 1;

push 2;

add;

ldrb

w8, [x0, #1]

str

w8, [x1], #4

addx0, x0, #2

ldrb

w8, [x0, #1]

str

w8, [x1], #4

addx0, x0, #2

ldr

w8, [x1, #-4]!

ldur

w9, [x1, #-4]

add

w8, w9, w8

stur

w8, [x1, #-4]

addx0, x0, #1

Copy & paste assembly
Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

97

Inline-threaded dispatch

Pro the fastest dispatch is no dispatch
Con requires JIT compilation

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

98

Conclusion

Benchmark on the target hardware, then optimize.
jonathanmueller.dev/talk/deep-dive-dispatch
Mastodon: @foonathan@fosstodon.org
YouTube: youtube.com/@foonathan

Jonathan Müller — @foonathan

A deep dive into dispatching techniques

C++Now

2023-05-12

99