Interview
Compiler Optimization with Greta Yorsh
- Greta Jorsch, a compiler engineer at Jane Street's London office, transitions from a background in software verification and program analysis to focusing on compiler optimization, driven by the realization that formal verification alone cannot solve all correctness challenges due to undecidability.
- Her research at IBM, ARM, and Queen Mary University of London highlighted that while correctness is paramount for compilers, performance metrics like CPU-specific micro-optimizations often yield more tangible and measurable improvements for end-users.
- She identifies a key limitation in traditional verification as the difficulty of keeping external specifications aligned with evolving source code, contrasting this with OCaml's type system where the type serves as the specification, reducing the maintenance gap.
- Jorsch advocates for combining testing and formal verification to leverage the speed of concrete execution (testing) to guide and accelerate the slower, broader scope of formal proofs.
- One specific technique she explores involves executing a program to collect specific states, abstracting those states to cover a larger set of possibilities, and then using formal decision procedures to identify remaining uncovered paths.
- Super optimization is defined as a search-based technique that aims to find an optimal instruction sequence for a given program segment by proving equivalence to the original, rather than applying sequential transformation passes.
- Current practical applications of super optimization are limited to compiler infrastructure development and hardware co-design rather than daily developer builds, due to the high computational cost of the required verification decision procedures.
- In the hardware collaboration context, super optimization allows engineers to rapidly evaluate the performance potential of new microarchitectures by generating the theoretically optimal code for them without needing to manually rewrite complex compiler passes.
- Jane Street implemented Feedback-Directed Optimization (FDO) in the OCaml compiler using a sampling-based approach to reduce instrumentation overhead, resulting in 10–20% performance improvements in critical programs.
- FDO optimizes memory layout by ordering functions and basic blocks based on execution profiles, ensuring frequently calling functions reside in close physical memory to minimize cache misses and improve access speed.
- Beyond raw performance gains, FDO stabilizes runtime performance by removing noise caused by library updates or unrelated code changes that previously altered instruction placement and cache behavior.
- Jorsch notes that while modern hardware (e.g., branch predictors) handles some optimization dynamically, the compiler retains a superior ability to reason about long-term program structure and future execution paths, suggesting a complementary relationship rather than redundancy.
- Moving from C/C++ to OCaml for compiler implementation allowed Jorsch to significantly reduce code volume by leveraging the language's mathematical declarative style, powerful type system, and automatic garbage collection.
- She identifies the OCaml backend's strong focus on portability across architectures (e.g., AMD64, ARM) as a constraint that sometimes limits the depth of architecture-specific micro-optimizations, such as register allocation strategies for ARM.
- A recent miscompilation bug introduced by an optimization change in the OCaml compiler was caught by an internal test suite, leading to a cultural process of immediate rollback, post-mortem analysis, and the creation of new preventative test infrastructure.
- Jane Street aims to influence upstream OCaml development by open-sourcing performance tooling and benchmarks (such as the Sandmark repository) to demonstrate the value of optimizations like FDO to the broader community.
- Resistance to upstream adoption of Jane Street-specific optimizations stems from concerns about added complexity and maintenance burden, suggesting that modularizing compiler passes could allow external contributions without blooming the core shared codebase.