What will you do? How will you do it?
We will design a flattened representation for Bril!

Background: Typically, the way to implement an interpreter is to create an explicit AST data type, but this requires allocating AST nodes on the heap. Instead, as demonstrated in this blogpost by Adrian, we can flatten the AST into an array, i.e. pack all AST nodes into one single contiguous array, and refer to children in the AST using array indices (as opposed to pointers). This has enormous performance benefits!

Task: In light of this, we aim to design a flattened representation for Bril. This would have 2 components:

1. Infrastructure to convert existing Bril JSON files to/from our flattened format (+ round-trip tests to make sure this works)
2. An alternate Bril interpreter that operates directly on the flattened data structure (as opposed to the existing one brili, which has to parse JSON)

Since all the AST nodes are stored within one contiguous array, the in-memory & disk representations are the same! To serialize, we can just use Rust's zerocopy library to convert the array into a blob of bytes that can be written to disk directly (no need for pretty-printing!) To deserialize, we can just use mmap(2) it (no need to parse json!) We plan on following the approach outlined in another blogpost by Adrian for turning our flattened Bril representation into a file format using zerocopy.

Some foreseen challenges are storing strings for variable names and handling instructions w/ different no. of operands, as in both of these cases we deal with variable-length data. For instance we will probably want to use a separate array to store arguments. Additionally, for simplicity, our initial plan is to flatten the non-SSA version of Bril rather than trying to adapt our data structures to exploit SSA form.

We plan on implementing our project in Rust for 3 reasons: 1.) to maintain consistency with Adrian’s blogposts, 2.) to take advantage of useful Rust libraries like zerocopy and 3.) to make our implementation performant (and comparable with the existing Rust interpreter brilirs). Our collective experience with Rust is limited (only one of the 3 of us has experience writing Rust), but we’re happy to learn Rust as part of this project. (If you have ideas on any alternate languages we could use, we’d be happy to hear them! To make the comparison of our interpreter with the existing interpreter fair, it seems like we would either have to use TypeScript or Rust, since the two existing Bril interpreters are written in those languages.)

How will you empirically measure success?

We will empirically measure success in two components: the correctness of our implementation (i.e. that transformed programs behave the same way as the original programs) and the performance benefit of our implementation. To quantify the performance benefit, we plan on comparing the CPU wall clock time & memory usage of our interpreter vs the standard one (although we’re not sure if these are the best metrics). We also plan on comparing the file size of our file format (that we get from converting the array to bytes) vs the default JSON representation for Bril programs.

We plan to evaluate our implementation first on a hand-crafted set of microbenchmarks (e.g. random generation of Bril programs à la Adrian’s blogposts), then on the /core benchmarks suite in bril. Specifically, for testing the correctness of our implementation, we will perform round-trip tests converting JSON files to/from our flattened format and back, checking that these JSON files remain the same.

Team members:
@ngernest, @samuelbreckenridge, @katherinewu312