# Effects based scheduling for the OCaml compiler pipeline *2025-04-01 — idea* In order to compile the OCaml program `foo.ml` containing: ``` Stdlib.print_endline "Hello, world" ``` the OCaml compilers only require the compiled `stdlib.cmi` interface to exist in order to determine the type of `Stdlib.print_endline`. This separate compilation technique allows modules of code to be compiled before the _code_ they depend on has necessarily been compiled. When OCaml was first written, this technique was critical to reduce recompilation times. As CPU core counts increased through the late nineties and early 2000s, separate compilation also provided a parallelisation benefit, where modules which did not depend on each other could be compiled at the same time as each other benefitting _compilation_ as well as _recompilation_. For OCaml, as in many programming languages, the compilation of large code bases is handled by a separate _build system_ (for example, `dune`, `make` or `ocamlbuild`) with the _compiler driver_ (`ocamlc` or `ocamlopt`) being invoked by that build system as required. In this project, we'll investigate how to get the OCaml compiler itself to be responsible for exploiting available parallelism. Some previous work (parts of which are available on GitHub[^1]) showed the benefits of sharing the typing information known to the compiler between each invocation. The hypothesis was during a _sequential_ computation, a considerable amount of time is spent by the compiler searching for and reloading typing information, as well as the overheads of launching thousands of copies of the compiler in a given build. Our test compiler with an adapted version of Dune showed as much as a halving of compilation time in _sequential_ builds. However, in _parallel_ builds, the results were not as impressive - although the many invocations of the compiler repeat the same loading operations, much of this cost is (quite predictably) masked by performing the work in parallel. The previous investigation was carried out on OCaml 4.07. Although it shared the typing information between "invocations" of the compiler, the compiler pipeline itself was unaltered - a file only started to be processed when all of its dependencies were ready. Furthermore, it remained the responsibility of a build system to provide this dependency ordering. Fast forward to the present day, and we have OCaml 5.x, with both first class support for [parallelism](https://anil.recoil.org/papers/2020-icfp-retropar) and [algebraic effects](https://anil.recoil.org/papers/2021-pldi-retroeff). Domains provide an obvious ability for a single compiler process to compile several files simultaneously. Effects should allow us to break the pipeline into stages, suspending the compilation whenever new type information is required by performing an effect. Using this model, it should be possible to start with the entry module for a program and allow the type checker itself to discover the dependency graph. it should be possible to see many files being _progressively_ type-checked in parallel. The hypothesis is that this will be both faster, but also considerably simpler. The "scheduler" required for handling the effects should be a considerably simpler program than a full-blown separate build system. Key challenges in this work: - the compiler library functions are not parallel-safe. It will be necessary to adapt the compiler either to work around or eliminate its global mutable state. This was necessary in the OCaml 4.07 as well. - The compiler becomes a much longer-lived process, and the garbage collector becomes more relevant. The OCaml 4.07 version required "ancient heaps" to be used to keep the major collector under control - otherwise significant amount of time are spent by the runtime marking major heap which will never be collected. This technique will need revising for OCaml 5, potentially with a direct alteration to the runtime to support stop-the-world promotion of items from the major heap to the ancient heap. - It will not be possible to achieve an upstreamable change to OCaml during a project of this length, but given that the comparison will be against a real build system operating with the same level of parallelism, it should be possible to perform a wide-range of measurements building existing OCaml projects. - There's lots of potential for additional exploration, particularly dispatching multiple build targets to the compiler (i.e. building multiple libraries and executables in the one invocation) and in using reusing previous build graph computations to inform scheduling decisions. [^1]: see [dra27/ocaml#nandor-dune-work](https://github.com/dra27/ocaml/commits/nandor-dune-work/), [dra27/dune#nandor-shmap](https://github.com/dra27/dune/commits/nandor-shmap), and [nandor/offheap](https://github.com/nandor/offheap). ## Weeknotes Lucas Ma did this as a UROP over the summer of 2025, and kept [weeknotes](https://lucasma8795.github.io/blog/) as he went. The aim was to let the compiler notice a missing dependency partway through a build, go and build that, and pick up where it left off, rather than needing a build system to work out the right order in advance. - [Week 1](https://lucasma8795.github.io/blog/2025/07/04/effects-scheduling-w01.html) was reading. He arrived with one term of functional programming behind him, so the first days went on how a running program can be stopped partway through and later resumed. - [Week 2](https://lucasma8795.github.io/blog/2025/07/11/effects-scheduling-w02.html) had it working. Compiling a file that depends on one that has not been built yet normally just fails. Instead the compiler now stops at that point, builds the missing file in a separate process and carries on. He then used it to build parts of the OCaml compiler itself\! - [Week 3](https://lucasma8795.github.io/blog/2025/07/18/effects-scheduling-w03.html) built a whole OCaml installation that way, driven by a script rather than the usual makefile, with the interface files left out of the recipe for the compiler to find on its own. Compared against a normal installation, the only difference was the one file he had added to the compiler. - [Week 4](https://lucasma8795.github.io/blog/2025/07/25/effects-scheduling-w04.html) went parallel. He wrote a small pool of workers first, then on [David Allsopp](https://www.dra27.uk)'s advice started with separate processes rather than threads, to sidestep the compiler's pile of global variables. The main process compiles, and hands each missing interface to a child. - [Week 5](https://lucasma8795.github.io/blog/2025/08/01/effects-scheduling-w05.html) is where that bit. Stopping and resuming a computation preserves the call stack but not the compiler's global variables, so a resumed task woke up with the wrong ones. Merlin had already hit this and their code for snapshotting and restoring that state dropped straight in. The bug that survived took two days and a great many print statements to pin on a single function in the type checker. Status: Completed Level: Any Year: 2025 Project: OxCaml Labs Supervisors: Anil Madhavapeddy, David Allsopp Students: Lucas Ma ## Related - [Retrofitting a build system into a compiler](https://www.dra27.uk/blog/platform/2025/09/25/building-with-effects.html) (feed, 2025-09-25) - [EEG internships for the summer of 2025](https://anil.recoil.org/notes/eeg-interns-2025) (note, 2025-06-28) - [OxCaml Labs](https://anil.recoil.org/projects/oxcaml) (project, 2025-01-01) - [Retrofitting effect handlers onto OCaml](https://anil.recoil.org/papers/2021-pldi-retroeff) (paper, 2021-06-01) - [Retrofitting parallelism onto OCaml](https://anil.recoil.org/papers/2020-icfp-retropar) (paper, 2020-08-01) --- Canonical: https://anil.recoil.org/ideas/effects-scheduling-ocaml-compiler Type: idea License: CC BY 4.0 Tags: ocaml, functional, effects, urop