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.