Exploring Tail-Call Optimization in Rust for Uxn Emulation

Recently, I embarked on an intriguing journey to implement a tail-call interpreter using the 'become' keyword in Rust, which has been a recent addition to the language. This endeavor was part of my ongoing exploration of high-performance emulation for the Uxn CPU, a simple stack machine utilized within the Hundred Rabbits ecosystem. My previous implementations included a Rust version and a hand-coded ARM64 assembly, both of which were outperformed by the new tail-call-based virtual machine (VM).

## Uxn Emulation Basics

Uxn operates with 256 instructions and a limited memory structure, including two 256-byte stacks and 65536 bytes of RAM. The simplest emulator reads bytes from RAM, executing instructions that may alter the program counter. The challenge lies in optimizing these operations, as the current implementation stores values in memory rather than registers, making the main operation branch unpredictable.

## Assembly vs. Tail Calls

In my assembly implementation, I used threaded code to store CPU state in registers, achieving significant speedups. However, this method requires maintaining a large and unsafe codebase. The tail-call approach in Rust aims to replicate this efficiency without the need for hand-written assembly. By storing program state in function arguments and ending each function with a call to the next, I hoped to achieve similar performance gains.

## Implementing Tail Calls in Rust

The implementation involved reconstructing the Uxn object at the beginning of each function and deconstructing it when calling the next operation. Despite initial stack overflow issues, the use of the 'become' keyword in nightly Rust allowed the compiler to replace the caller's stack frame with the callee's, preventing stack buildup.

## Performance Analysis

On ARM64 systems, the tail-call interpreter outperformed my hand-written assembly, particularly in benchmarks like Fibonacci and Mandelbrot. However, on x86 systems, the assembly backend still held an edge, especially in microbenchmarks. The generated code for INC and ADD2 opcodes revealed inefficiencies, such as unnecessary register spills, which could be attributed to the immaturity of the feature in rustc.

## WebAssembly Challenges

Testing the tail-call interpreter in WebAssembly (WASM) environments like Firefox and Chrome showed disappointing results, with the tail-call approach being significantly slower than native implementations. This suggests that patterns generating efficient assembly do not translate well to the WASM stack machine.

## Conclusion and Future Work

The tail-call interpreter has been integrated into the 0.3.0 release, defaulting on ARM64 systems. While it shows promise, particularly on ARM64, there is room for improvement on x86 and WASM platforms. I welcome any insights or suggestions for enhancing performance across different architectures.