Tutorial, Other
OCaml Locals Save Allocations | OCaml Unboxed
- Objective: Demonstrate how the
localkeyword in a specialized OCaml compiler (Jane Street's branch) reduces memory allocation and garbage collection overhead by restricting value lifetimes to specific regions. - Region Definition: In this compiler model, both function bodies and loop bodies define distinct "regions" where local values are guaranteed not to escape.
- Benchmark Program: A test loop iterates 10,000 times, generating a random-length list of integers and counting elements divisible by five.
- Baseline Allocation: Without optimizations, the standard implementation (using
list.initandlist.iter) allocates approximately 204,000 words, verified viaocamloptandocamloptflags (-v 1024). - Escape Analysis Failure: Simply annotating a variable as
localfails if the function consuming it (e.g., standardlist.iter) allows the value to escape, as the standard library does not yet support locality annotations. - Custom Implementation Requirement: To achieve locality, custom implementations of
iterandinitare required because they must explicitly enforce that arguments and return values do not escape their defining regions. - Type Inference Nuance: Removing type annotations from helper functions allows the compiler to infer locality; however, adding explicit types without the
localmodifier causes the compiler to conservatively assume values might escape, triggering errors. - Function Annotator Logic:
- The custom
iterfunction must label both the list and the function argumentfaslocal. - The custom
initfunction must label the generator functionfand the result list aslocal. - Recursive helper functions within these definitions (e.g.,
loop) must also be labeledlocalunless explicitly moved outside the region usingexclave.
- The custom
- Exclave Usage: The
exclavekeyword is used to explicitly allow a value to escape its region when necessary, often required for tail-recursive functions or when returning a locally constructed value from a region that must end early. - Optimization Results:
- Replacing standard library functions with local-aware custom versions reduced allocations from ~204,000 words to ~90,000 words (a reduction of roughly half).
- Further refining function arguments to be
localand ensuring no accidental escapes reduced allocations to near-zero (minimal overhead remains from system calls and printing).
- Garbage Collection Impact: By ensuring values are deallocated when their region ends rather than waiting for mark-and-sweep garbage collection, the system reduces GC latency and workload.
- Compiler Mode: Experiments utilized
ocamlopt(native code mode) rather thanocamlc(bytecode) to ensure optimal performance visibility. - Future Development: The
localfeature is experimental and expected to be upstreamed to the main OCaml compiler following community consultation. - Code Availability: The implementation code is hosted on GitHub for reproducibility and further study.