OCaml Compiler Implemented in C++: It's Not Just Faster—It Also Increases Trust

Ecosystem
1

You’re absolutely right to be skeptical of your compiler binaries. In this post, we’ll explore how a comprehensive C++ reimplementation unlocks DDC verification for OCaml — while delivering meaningful compile-time improvements. :rocket:

Wait! Don’t leave yet! The rest of this was typed character by character by a human.

We had some fun here recently talking about an unrelated project, the OCaml runtime ported to Rust, and this led to an interesting side-channel discussion that surfaced a paper on Debootstrapping without Archeology by Nathanaëlle Courant, Julien Lepiller and Gabriel Scherer. I somehow had never come across this before!

Background brief on trusting trust: once upon a time, UNIX god Ken Thompson trolled the world during an acceptance speech by asking “wouldn’t it be hilarious if your beloved compiler authors had introduced a backdoor years (decades) ago that was still lurking today???” (paraphrased). The crux of the matter was that, to compile a C compiler which is implemented in C, you need an existing C compiler binary and that’s an opportunity to introduce malware that wakes up when it recognizes it’s compiling a target program (like login).

Ever since then, the infosec community has been… curious… about trusting trust and they breathed a huge sigh of relief when David A. Wheeler proposed diverse double compilation (DDC) as a mitigation. So, has anyone done this for our favorite language?

Yes! In the Debootstrapping OCaml paper, the authors describe writing an OCaml interpreter in MiniML (an OCaml subset) and a compiler for MiniML in Scheme to do DDC, which proved that OCaml 4.07.1 has no trusting trust backdoors when compiling itself. But notice this part in their paper:

If we assume unlimited work resources, tailored debootstrapping is a trivial problem: just port your programming-language implementation to another language that has already been debootstrapped (for example C). But this is a massive effort that may never happen in practice – especially as you have to first convince your language implementors to work in a different programming language.

Tee hee.

I present this independent OCaml compiler implemented in C++. It runs a OOMs faster than the MiniML/Scheme debootstrapper, solves DDC for OCaml 5.5.1 release (and 5.6+trunk), produces identical byte outputs to the OCaml compiler, and it even runs faster than the official OCaml compiler(!)

NOTE for quick skimmers: this project does not make your OCaml programs faster. It may only let you compile OCaml programs faster.

Regarding byte-identical outputs. There’s a few documented minor divergences that could be closed if there’s interest. The divergences do not preclude DDC and they’re minor enough that I am claiming byte identical.

Most importantly: because we have done DDC, we can conclude the OCaml 5.5.1 (and 5.6+trunk) bootstrap has no back doors when compiling the compiler. Furthermore, because we do produce byte identical outputs as upstream, arguably no back door is lurking outside of the source-available views.[1]

Regrettably, not only is there no backdoor in the OCaml compiler, there isn’t even an easter egg. Sad! I would have at least snuck in something like mb4c4rell4_waz_here, but that’s probably why the good people behind OCaml have commit bits and I don’t.

How to run DDC yourself

Clone the repo git clone https://github.com/mbacarella/cxx-ocaml and follow the instructions in cxx/DDC.md.

Install an opam switch that uses the C++-based OCaml compiler

Do this to get a switch whose ocamlc and ocamlopt are the C++ version.

opam switch create cxx-5.5 --empty
opam pin add -n ocaml-variants.5.5.1 'git+https://github.com/mbacarella/cxx-ocaml#cxx-5.5'
opam pin add -n ocaml-option-cxx.1   'git+https://github.com/mbacarella/cxx-ocaml#cxx-5.5'
opam install ocaml-option-cxx ocaml-variants
opam switch set-invariant --packages=ocaml-variants,ocaml-option-cxx

To check that you’re actually running the C++ version, do ocamlc -cxx-version. The stock compiler stays available in the switch as ocaml*.stock.

Requirements: clang++ 18 or newer, cmake, ninja, and libzstd’s dev files.

Don’t @ me that this is all a big hoax because you’re missing some dependencies. We have all seen how that goes.

Next steps

Minimize the extra dependencies needed above, like swapping clang for gcc to match OCaml upstream.

I’ve only tested this on x86-64 on Linux, so ARM64 is an obvious next addition. Also probably should add support for flambda.

There’s still some low hanging performance-fruit wins that don’t involve doing anything too obscene[2] to go after.

I’m happy to hear your feedback! We can chat here or on the OCaml Discord’s #ai channel.

Let me know what you’d like to see!

Benchmarks

Take these with a grain of salt. Benchmarks are easy to embarass yourself with. That said.

My benchmark host was a Desktop Ryzen 9 7950X with 128GB of RAM running Linux.

I’d prepare an opam switch with each compiler and all project dependencies first.

The benchmark itself is a full build of awso, an AWS library that has coverage for all of 300+ AWS services, including some very huge auto-generated modules with ppx.

It builds byte code, native and assembles a gigantic awso-cli that links every aws library. I timed dune build and took the best of 3.

I think this is a good real world test because it contains about 100,000 build artifacts and it was a major quality of life issue to both do full rebuilds every time I tinkered with something. opam-ci certainly didn’t appreciate how huge it was either.

dune selected up to 32 cores on my host.

Results

  • ocaml 5.5.1: 4998.41s user 1016.62s system 1904% cpu 5:15.91 total
  • c++ocaml 5.5.1: 3281.87s user 990.02s system 1984% cpu 3:35.30 total

As we can see, both the CPU time and wall clock time are lower in the C++ version. In terms of wall time we are 1.47x faster.

Every build artifact is bitwise identical to upstream: .cmi, .cmo, .cmx, .o, .cma, .cmxa. So are executables built in the same switch (in the C++ switch the stock compiler is ocamlopt.stock and the C++ version is renamed over ocamlopt). The one difference is the .cmt/.cmti files, which are used by editor tooling. They decode to the same data but stock OCaml’s marshalling has a form of structural sharing we didn’t completely reproduce the layout of.[3]

Note there’s more than just the ocaml compiler itself running a build. A ton of time is spent in the gcc toolchain (like as). The improvement in individual artifacts is more substantial than the wall clock time suggests, but it’s also a lot more work to describe. So I’ll leave that for later if anyone is interested.

AI disclosure

I obviously didn’t implement an OCaml compiler in C++ myself. I used Claude Code. This wasn’t easy for Claude either: it has been working on this project for 4 months now, though progress sped up between the releases of Opus 4.8, 5.0 and 5.5, with some guest appearances by Fable.

This is not an April fool’s

Don’t confuse this with Stephen Dolan’s troll, which compiled OCaml into C++ template metaprograms. Game respects game though.

Footnotes

  1. This method in this project does not certify that your C/C++ toolchain, other OS tools or your firmware are backdoor free, only that if a backdoor is present it did not originate from the code in this project.

  2. I’m not against doing the obscene for even moar performance! Anything especially obscene would go in a separate branch though and be opt-in.

  3. Mostly just to save on tokens. We didn’t cheat the benchmarks by doing this. We’re actually slower than stock OCaml at writing .cmt files and that cost shows up in the benchmarks.

2

How many LOC of C++ it is? Compared to the one written in OCaml?

3

very cool; formal proofs when?

4

LOC is a not the best measure between languages but it’s actually about 1:1 for the parts of OCaml that were implemented, so, about 130,000 lines for both.

I was expecting the C++ line count to be a lot higher, but the C++ has longer lines on average. Also I guess “modern C++” has more expressive power than the C++ we may have been first traumatized by so the line counts come down further.

While we’re talking about the generated code, I first started the project by having Claude try to greenfield it and implement each compiler pass from first principles and use the various test suites as oracles (and also what it knew about OCaml from training). This worked pretty well for the lexer and parser. The lambda part produced working code but it wasn’t byte identical; good enough for DDC but I wanted to go harder. Typing never really worked properly as a greenfield approach (though DDC didn’t need a real type checker, the compiler’s sources were already known to type check), we tried several different approaches and then just gave up and ported the existing code function by function, starting with typing and then lambda and everything afterwards. English might be the new programming language but OCaml code is the best spec.

5

BTW, I’ve also started 2 weeks ago to write an OCaml compiler from scratch using AI, but taking another direction: how to make one with far less LOC. The result, 7000 LOC for a pretty descent one here: IX/languages/ml at main · aryx/IX · GitHub (and there is even a tiny version here IX/tiny/TinyML.ml at main · aryx/IX · GitHub in less than 2000 LOC. In both cases it does not support functors, nor objects, but I’ve found this subset a better language than the full OCaml. I’ve even experimented with adding type classes to it :slight_smile:

6

Hey @mbacarella, I found out that you started to upstream fixes for performance issues to vanilla OCaml. Good job, keep going!

I’m wondering in which places (why) C++ implementation run faster then OCaml one? Does this happen for specific files, or for specific compilation passes? Or everywhere? I didn’t any research yet, but my wild guesses would be:

  1. Data structures can be smaller because of field packing
  2. In some places tree-like (pointer-heavy) data structures started looking more like arrays, and auto vectorisation was applied. Something similar to the one described in “Clean code, horrible performance” talk
7

Thanks @Kakadu!

Here are some thoughts on where the improvement comes from.

Maybe unsurprisingly, most of the C++ side win is because there’s no GC. Official OCaml spends about 28% of time in GC[1] whereas C++-OCaml spends about 5% in malloc/arenas.

It’s hard to account for the impact of flatter data structures (like C++ vector by default instead of cons lists) directly because they’re amortized over the GC, but it does directly help with a few percentage points here and there. Finer bit packing helps for a few points as well.

perf says there’s about 9% of time in Official OCaml is being spent in polymorphic compare/hashing and closure application. Specializing these might be a nice bite sized project.

Tangent, because I didn’t know about this before: official OCaml relies on a neat performance trick via Marshal, basically these are a very fast path for just shoving serialized objects back into runtime memory with minimal decoding. Each compiler invocation loads .cmi files directly into runtime memory this way, and without it performance would be a lot worse. There isn’t much room to make this faster. The C++ version doesn’t benefit from loading .cmi files so it does its own form of dumping and then mmaping data structures back into memory (these are called .img files).

Re: memory usage, official OCaml has lower peak memory usage for really large compiles; this is worth some improvement in performance during big parallel jobs because it burdens the system memory less, though across a whole parallel build the C++ version still wins.

There’s probably some tuning of minor heap size that could be done but it may be a tradeoff against making larger jobs slower to make smaller jobs faster.

  1. Clod says “Allocation in type copying (Ctype.copy/instance) is the biggest source of garbage: about 40–50% of the port’s typing zone is dead by the end of typing. Allocating less there would cut GC time directly”. That seems like a pretty gnarly change though.

I have some detailed benchmarks done by Claude here.

Other housekeeping

Since this thread is getting bumped by my reply I’ll take the opportunity to work in some other developments.

  • flambda is in
  • ARM64 support is in
  • dependencies are reduced to simply requiring g++ on top of whatever Official OCaml requires (that is ninja, cmake and clang are no longer needed).

The opam switch install instructions are the same.

I still haven’t pushed into doing any additional performance improvements. Might be more to say later.

8

As far as I understand, copying is often required for soundness (or makes the code more obviously correct). I think the claim about a large portion being dead is not surprising: the intermediate structures don’t need to be part of the final typing, but they are necessary for checking. It’s not a sign that this garbage can be avoided (and the algorithms still have to be readable!).

In addition, it’s sometimes difficult to eliminate garbage while also improving performance: short-lived values are often especially cheap, but require contortions to avoid. I think this points out a deficiency in how we can measure garbage: we can of course measure major and minor words, but that doesn’t directly translate to a performance impact. Some minor words might improve performance, others might force us to promote intermediate lifetime objects to the major heap.

9

I have something in progress here: Inline the full-application part of caml_apply by smuenzel · Pull Request #14925 · ocaml/ocaml · GitHub

But it needs a lot more benchmarking, in my limited benchmarks, I saw good results.

10

A long time ago I used to work inside the JVM. And I did a lot of performance-analysis of commercial Java codes to boot. One thing I rapidly figured out, was that “allocation avoidance” was a great way of speeding up code. So “buffer pooling” for instance. I was actually trying to speed up code for real (screaming, paying customers), so I never had the time to investigate -why- pooling was effective – was it GC avoidance? Cache locality of the pages being reused? something else? Literally I made a hacked version of the JVM where the profiler used a “clock” that counted bytes-allocated instead of elapsed time. Then finding ways to minimize allocation became the performance-improvement method, instead of finding ways to directly speed up code.

Long ago Henry Baker pointed out that the stack is a kind of nursery: he implemented a GC-like language where objects got allocated on the stack and “evicted” if necessary to the heap, and (IIRC) found that this got speedups. Of course, the ZAM does this very thing for closures to excellent effect.

11

The compiler build model is such that it is invoked many times, often on very small files. At the same time the OCaml default runtime parameters are tuned for longer-running programs (because typically people want better performance for longer programs, while performance of very quick programs matters less). This remark can lead in two directions, both valuable:

  1. We can notice things that make no difference for larger runs (larger compiles), but make a difference in practice when building many small files, and optimize them. Your example of filesystem accesses on OSX is probably in this category.
  2. To get a comparison about the performance of the two versions when actually doing work, I think it would be important/useful/instructive to filter out short-running invocations. Could you collect speedup statistics over compiler invocations that last more than 0.5s?

For example, the fact that camlinternalFormatBasics sees a slowdown with your implementation is notable, because it is one of the harder files to type-check. It is very possible that some aspects of your compiler are noticeably slower on demanding files, but this is hidden by better constant factors on startup / when doing IO.