[Pitch] Direct-threaded interpreters in safe Swift

Hi, I am wondering if there is any interest in this,
I prototyped an extension to swift to support the construction of direct threaded interpreters in Swift.

That prototype is here at the moment: GitHub - lorrden/swift at experiment/threaded-interpreters · GitHub

This has obvious implications on interpreter performance, see benchmarks below,
but also interpreted emulators, and the approach here is also useful for structured,
finite state machines (protocol handling etc).

The main outcome of the prototype is that I managed to get a Swift-based interpreter
running at the same speed as one implemented in C.

The thought occured to me after the latest PHP issue
and why interpreters usually are written in C.
One of the key reasons is that threaded interpreters in C
are simply much faster than equivalent switch based interpreters
in languages like Swift and Rust.
However, even with C, you need language extensions to make this worthwile,
especially the labels as values support in GCC and clang.
In the latter case this is lowered via LLVM indirectbr and the blockaddr operations.

The only discussion reasonably relevant on this here, that I found is this:

My approach is different though, and as mentioned already prototyped.

This example illustrates the way my prototype works on a syntactic level:

enum Opcode {
    case increment
    case halt
}

struct Counter {
    var value = 0
    var pc = 0

    @_interpreterEntry
    mutating func run(_ program: Span<Opcode>) {
        pc = 0
        dispatch at pc
    }

    @_opcodeHandler(Opcode.increment)
    private mutating func increment() -> Int? {
        value += 1
        pc += 1
        dispatch at pc
    }
}

extension Counter {
    @_opcodeHandler(Opcode.halt)
    private mutating func halt() -> Int? {
        return nil
    }
}

let program: [Opcode] = [.increment, .increment, .halt]
var counter = Counter()
counter.run(program.span)
print(counter.value) // 2

The main point with this is that the functions are all lowered into a single LLVM function,
where jumps are directed using indirectbr.
This works with extensions, as well, but the use of structs here allows scoping.
E.g. multiple interpreters in the same program.

The compiler generates a map between enum opcodes and block addresses
so we can look up the handler like this:

targets[i] = blockAddrTable[program[i]]

interpreter:
    load r1, targets[r2]
    jump r1

opHandlerA:
    ;; Work
    inc r2
    load r1, targets[r2]
    jump r1

The target derivation can be cached if necessary (not done in the prototype, but anway).

Benchmarks

The benchmark runs a synthetic eight-opcode interpreter
on two 64k-instruction programs (a repeating opcode layout
and a deterministic shuffle).

The benchmarks were implemented in C, Rust, and Swift.
Variants were rebuilt and measured in a single session on arm64 macOS (MacBook Air M1),
with 13 trials of 50 million VM instructions per variant and program.

Results are reported as median nanoseconds per VM instruction.

The experimental Swift direct-threaded timings include preparing and freeing the handler-address streams which are not cached at the moment,
while the C direct-threaded timing uses a stream prepared before the timer starts.

Variant Predictable Shuffled
C switch 2.168 7.948
C indirect threading 2.353 7.313
C direct threading 2.155 5.595
Rust match 2.318 7.992
Rust function-pointer threading 3.592 6.827
Swift switch, raw pointers 2.142 7.965
Swift function-pointer threading 3.584 6.826
Swift hand-written SIL switch 2.426 9.278
Swift hand-written SIL direct threading 1.933 5.531
Swift source switch, entry loop 2.713 8.060
Swift source direct threading, entry loop 2.453 5.654
Swift source switch, handler chain 2.305 7.842
Swift source direct threading, handler chain 2.079 5.471

As can be seen the Swift handler chain used 3.6% less time per instruction on the predictable stream
and 2.2% less on the shuffled stream than C direct threading.
It was faster in all 13 rounds on each stream.

Against the matched Swift switch,
the handler chain delivered 1.43x shuffled throughput.
Broadly, the results were inline with direct threading in C.
And I wound not make the conclusion that Swift was faster than C,
due to LLVM versions and other differences, but they clearly indicate that we can get Swift to match C-performance in these cases.

This broadly also matches my experience with direct threaded emulators.

Limitations

The following are the obvious things that is not yet implemented,
but there is multiple other things to these as well:

  • Handler parameters
  • Throwing handlers
  • Reusable prepared programs
  • Considerations for things not behaving nicely
    (emulators with paged virtual memory, dynamic code patching etc).
  • Testing with more real-world workloads.

Next Steps

I would like to know if there is interest in this, if so I will continue working on this,
hopefully making a formal proposal in due time.

I appreciate any comments on the ideas here as well.

5 Likes

I'm not convinced that your approach is better than using the standard LLVM machinery for tail-calls. Your approach is both less general and deeply coupled to a particular implementation strategy for implementing threaded interpreters. It's also not clear to me why your opcode handlers are required to return Int?.

Explicit tail calls already handle this correctly in Rust (see Godbolt), and are also the direction C(++) is going with [[clang::musttail]] & [[gnu::musttail]].

The only issues to solve are how to spell tail calls, and specifying the conditions where a function can be tail cailed. The semantics of explicit tail-calls are already a solved problems. deinits and defers must run before the call, because otherwise its physically impossible to optimize to a jump.

2 Likes

Kind of, this is partially equivalent and the automatic conversion of opcodes to block pointers is not the essential part. The single LLVM function with indirectbr use is the important part, because it offers better automatic optimization opportunities.

The return was a leftover from previous experiments.

Tail calls give us in the shuffled example 6.329 ns per operation, which is much better than without it. Parts of that can be manually improved by changing the calling signature (I squeezed it down to about 5.7 by playing with the function arguments, but that part is automatic in the single LLVM function with indirectbr). I was also able to improve performance in the direct threaded cases by playing with the heuristics for the taildup pass, because in my bench at least it was not triggered, and that tweak improved the shuffled case of the C direct threaded to 1.581 (predictable) and 5.158 (non-predictable).

Tailcalls is a better model probably, but the closed function set is needed to produce the single LLVM function with indirectbr.