For Pi Day, I have implemented the same algorithm in both OCaml and OxCaml and compared the generated assembly and runtime performance.
OxCaml is a performance-focused extension of OCaml developed at Jane Street. It adds unboxed types, stack allocation, mutable bindings, and compile-time zero-allocation checking to the language. But what do these features actually look like in practice, and do they make a measurable difference?
The algorithm #
This year, I’m going to use the Gauss-Legendre algorithm to compute pi by iteratively refining four variables. Starting from:
a = 1, b = 1/sqrt(2), t = 1/4, p = 1
each iteration updates them:
a' = (a + b) / 2
b' = sqrt(a * b)
t' = t - p * (a - a')^2
p' = 2 * p
and pi is approximated by:
pi ~ (a + b)^2 / (4 * t)
The code is deliberately structured as two functions: a step function that computes one iteration and returns the updated state, and a gauss_legendre function that iterates over step calls. The step function is marked [@inline never] to simulate a realistic cross-module call boundary of the kind that appears in real applications.
OCaml #
(* pi_ocaml.ml - OCaml 5.4.0 *)
let[@inline never] step a b t p =
let a' = (a +. b) /. 2.0 in
let b' = sqrt (a *. b) in
let d = a -. a' in
let t' = t -. p *. d *. d in
let p' = 2.0 *. p in
(a', b', t', p')
let[@inline never] gauss_legendre () =
let rec loop a b t p = function
| 0 ->
let s = a +. b in
s *. s /. (4.0 *. t)
| i ->
let (a', b', t', p') = step a b t p in
loop a' b' t' p' (i - 1)
in
loop 1.0 (1.0 /. sqrt 2.0) 0.25 1.0 25
The step function returns a float * float * float * float tuple. The gauss_legendre function recurses, threading the four values through each iteration.
OxCaml #
(* pi_oxcaml.ml - OxCaml 5.2.0+ox *)
module F = Float_u
open Float_u.O_dot
let[@zero_alloc][@inline never] step a b t p
: #(float# * float# * float# * float#) =
let a' = (a +. b) /. #2.0 in
let b' = F.sqrt (a *. b) in
let d = a -. a' in
let t' = t -. p *. d *. d in
let p' = #2.0 *. p in
#(a', b', t', p')
let[@zero_alloc][@inline never] gauss_legendre () : float# =
let mutable a = #1.0 in
let mutable b = #1.0 /. F.sqrt #2.0 in
let mutable t = #0.25 in
let mutable p = #1.0 in
for _ = 1 to 25 do
let #(a', b', t', p') = step a b t p in
a <- a'; b <- b'; t <- t'; p <- p'
done;
let s = a +. b in
s *. s /. (#4.0 *. t)
Three OxCaml features are used here:
unboxed types #
Instead of float, which would be a boxed 64-bit IEEE double, allocated on the heap and subject to garbage collection, a float# stores the value directly in a CPU register. The #(float# * float# * float# * float#) return type is an unboxed tuple: four values returned in four XMM registers, with no heap allocation at all.
Stack-local mutable bindings #
let mutable creates a mutable binding that lives on the stack.
Compile-time allocation checking #
The [@zero_alloc] annotation asks the compiler to prove that the function performs no heap allocation. If any code path allocates, that is, boxing a float or creating a tuple and thereby potentially triggering the GC, the build fails with an error showing exactly where the allocation occurs.
What the compiler generates #
Both versions perform the same arithmetic requiring the same instructions: addsd, divsd, sqrtsd, mulsd, subsd sequence. The difference is what happens when step needs to return its four results to the caller.
OCaml: 104 bytes of heap allocation #
subq $104, %r15 ; reserve 104 bytes on the minor heap
cmpq (%r14), %r15 ; enough space?
jb .L102 ; if not → trigger GC
; Box each float (16 bytes each: 8-byte GC header + 8-byte value)
movq $1277, -8(%rbx) ; GC tag for boxed float
movsd %xmm0, (%rbx) ; store p'
movq $1277, -8(%rdi) ; GC tag
movsd %xmm1, (%rdi) ; store t'
movq $1277, -8(%rsi) ; GC tag
movsd %xmm3, (%rsi) ; store b'
movq $1277, -8(%rdx) ; GC tag
movsd %xmm2, (%rdx) ; store a'
; Build the 4-element tuple (40 bytes: 8-byte header + 4 pointers)
movq $4096, -8(%rax) ; tuple header tag
movq %rdx, (%rax) ; pointer → a'
movq %rsi, 8(%rax) ; pointer → b'
movq %rdi, 16(%rax) ; pointer → t'
movq %rbx, 24(%rax) ; pointer → p'
ret
.L102:
call caml_call_gc ; garbage collection
jmp .L104
Every call to step allocates 104 bytes: four 16-byte boxed floats plus a 40-byte tuple to hold pointers to them. It also performs a GC boundary check and may trigger a garbage collection if the minor heap is full.
OxCaml: zero allocation #
vaddsd %xmm1, %xmm4, %xmm0 ; a' = (a + b) / 2
vdivsd %xmm3, %xmm0, %xmm0
vmulsd %xmm1, %xmm4, %xmm1 ; b' = sqrt(a * b)
vsqrtsd %xmm1, %xmm6, %xmm1
vsubsd %xmm0, %xmm4, %xmm4 ; d = a - a'
vmulsd %xmm5, %xmm3, %xmm3 ; p' = 2 * p
vmulsd %xmm4, %xmm5, %xmm5 ; t' = t - p * d * d
vmulsd %xmm4, %xmm5, %xmm4
vsubsd %xmm4, %xmm2, %xmm2
ret ; a' in xmm0, b' in xmm1,
; t' in xmm2, p' in xmm3
Just the pure arithmetic steps: four values go in via XMM registers, four come back out the same way.
Benchmark #
The algorithm is too fast to benchmark on its own, so I run the computation in a for loop 10 million times, resulting in 250 million step calls and measured the results with hyperfine on Linux (10 runs, 3 warmup), showing that OxCaml is 1.44x faster.
Benchmark 1: ./pi_ocaml
Time (mean +/- s): 2.931 s +/- 0.048 s [User: 2.927 s, System: 0.004 s]
Range (min ... max): 2.854 s ... 3.020 s 10 runs
Benchmark 2: ./pi_oxcaml
Time (mean +/- s): 2.033 s +/- 0.090 s [User: 2.018 s, System: 0.015 s]
Range (min ... max): 1.945 s ... 2.188 s 10 runs
Summary
./pi_oxcaml ran
1.44 +/- 0.07 times faster than ./pi_ocaml
Results #
Both versions produce the correct value!
Pi = 3.141592653589794 (error: 8.88e-16)
Why [@inline never]? #
The [@inline never] annotation is worth mentioning as without it, the two compilers behave differently, resulting in a different comparison.
OxCaml inlines step into gauss_legendre, eliminating the function call entirely, resulting in a loop which is just the register arithmetic with no call instruction at all:
; OxCaml gauss_legendre WITHOUT [@inline never] - step is fully inlined
.L124:
vmulsd %xmm0, %xmm1, %xmm4 ; b' = sqrt(a * b)
vsqrtsd %xmm4, %xmm5, %xmm4
vaddsd %xmm0, %xmm1, %xmm0 ; a' = (a + b) / 2
vdivsd %xmm5, %xmm0, %xmm0
vsubsd %xmm0, %xmm1, %xmm1 ; d = a - a'
vmulsd %xmm1, %xmm2, %xmm6 ; t' = t - p * d^2
vmulsd %xmm1, %xmm6, %xmm1
vsubsd %xmm1, %xmm3, %xmm3
vmulsd %xmm2, %xmm5, %xmm2 ; p' = 2 * p
...
jmp .L124 ; loop — no call instruction anywhere
OCaml 5.4.0 does not inline step, even without the annotation. The loop still contains call camlPi_ocaml_inline.step_274@PLT, and every call still boxes four floats and builds a tuple on the heap:
; OCaml gauss_legendre WITHOUT [@inline never] - step is NOT inlined
.L111:
cmpq $1, %rdx ; base case check (i = 0)
je .L110
movq %rdx, (%rsp) ; spill loop counter
call camlPi_ocaml_inline.step_274@PLT ; still a real call
movq 24(%rax), %rsi ; unbox returned tuple
movq 16(%rax), %rdi
movq 8(%rax), %rbx
movq (%rax), %rax
jmp .L111 ; loop - passing boxed pointers
So [@inline never] on the OxCaml version levels the playing field. It prevents flambda2 from optimising away the very overhead I was trying to measure. Without it, the gap would be even larger, because OxCaml would inline everything while OCaml would still be boxing.
In practice, [@inline never] also represents the realistic case: real applications are made of many modules, and calls across compilation-unit boundaries cannot be inlined by either compiler. The boxing overhead shown here occurs whenever a function in one .ml file returns multiple float values to a caller in another.
Note #
I wrote this post last weekend in readiness for Pi Day, not realising that I would have the chance to use these techniques during the week in my OxCaml inference engine.