Can OxCaml make the whole parser fast?

Ahead of OCaml parsers; behind C++

• reusable — one parser kept warm across documents
• one-shot — fresh buffers on every call

Unboxed types

let twice (x : float) =
  x +. x

let twice (x : float#) =
  Float_u.add x x

SIMD support

let bytes =
  Int8x16.String.unsafe_get input ~byte:0 in
let quote = Int8x16.const1 #34s in
let matches = Int8x16.equal bytes quote in
Int8x16.movemask matches

Stack allocation

type point = {
  x : int;
  y : int;
}

let make_points () =
  let heap = { x = 1; y = 2 } in
  let local = stack_ { x = 3; y = 4 } in
  print_int (local.x + local.y);
  heap

@ local constrains where a value may flow; stack_ is what forces where it is allocated. A heap value is accepted anywhere a local one is—so a @ local return type alone guarantees nothing.

Zero-allocation checking

let[@zero_alloc] wrap x =
  Some x

(* [Some x] allocates a block *)

The scanner produces a structural index

Positions where parsing decisions can occur—not parsed values.

The parser builds values from the index

The parser writes values to a tape

Values remain in document order; decoded strings live in a side buffer.

The DOM borrows the parser’s tape

dom::parser parser;
dom::element doc = parser.parse(json);
auto answer = doc["answer"].get_int64();
for (auto item : doc["items"].get_array()) {
  use(item);
}

parser.parse(next_json); // reuses the tape

The project exposes both output contracts

let p = Tape.Parser.create ()
let tape = Tape.Parser.parse p input |> Result.get_ok

let root = Tape.tag tape 0
let entries = Tape.length tape

let _next = Tape.Parser.parse p next |> Result.get_ok
(* [tape] is now invalid *)

let p = Parser.create ()
let json = Parser.parse p input |> Result.get_ok

match json with
| Json.Object fields -> use fields
| _ -> ()

let _next = Parser.parse p next |> Result.get_ok
(* [json] is still valid *)

Same scanner and parsing routines; different storage and lifetime.

OxCaml SIMD maps directly to the scanner

let all_quotes =
  Int8x64.equal Int8x64.ascii_quote block in
let quotes_mask =
  Int64_u.(all_quotes &~ escaped_mask) in
let string_mask =
  Int64_u.(prefix_xor quotes_mask lxor state_mask)

let low = lookup ~table:low_lut block in
let high = lookup ~table:high_lut (high_nibbles block) in
let klass = Int8x64.(low land high) in
let operator_mask =
  Int8x64.equal
    Int8x64.(klass land vector_group_operators)
    (Int8x64.zero ())
  |> Int64_u.lnot

Here Int8x64.equal returns the 64-bit lane mask directly—compare and movemask fused—so vector results compose with ordinary Int64_u bit operations.

The first scanner reached only 0.4 GB/s

0.4 GB/sfaithful first implementation · twitter.json

Correct SIMD source was not enough.

Dynarray allocated per structural position

Packed masks removed output growth

The fold loop still allocated twice per block

Simd.Int8x64.String.fold_blocks input
  ~init:{ state = initial_state; block_idx = 0 }
  ~f:(fun { state; block_idx } block ->
    let result = scan_block state block in
    Structure.set_mask structure block_idx
      result.structural_mask;
    { state = result.state;
      block_idx = block_idx + 1 })
|> ignore

Even a tiny nested helper remained a call

let process block =
  let low_class = lookup ~table:low_lut block in
  let high_class =
    block |> high_nibbles |> lookup ~table:high_lut
  in
  let klass = low_class land high_class in
  let make_group_mask group =
    equal (klass land group) (zero ())
    |> Int64_u.lnot
  in
  let operator_mask =
    make_group_mask vector_group_operators
  in
  ...

Its definition and every call site were visible inside one top-level function.

Tactical inlining doubled throughput

Still required under -O3: removing them costs 11–28% and puts allocation back into a zero-allocation path.

Integer intrinsics lacked [@@builtin]

external count_set_bits = ...
  [@@noalloc]
external count_trailing_zeros = ...
  [@@noalloc]

external count_set_bits = ...
  [@@noalloc] [@@builtin]
external count_trailing_zeros = ...
  [@@noalloc] [@@builtin]

call caml_int64_popcnt_unboxed_to_untagged@PLT

caml_int64_popcnt_unboxed_to_untagged:
  call __popcountdi2

popcnt  %rax, %rax
ret

The scanner reached 6 GB/s

That measures mask production; the parser still has to visit every structural position.

The scanner is fast; now the parser needs positions

Producing masks and consuming positions favor different layouts

Flat helps only when its 4× buffer is already warm

Packed gives up a negligible warmed-parser win and avoids touching 32× more index storage.

With packed indices fixed, compare both output APIs

Borrowed tape peaks at 1.2 GB/s

0 minor and 0 major words on all seven fixtures—measured. [@zero_alloc] covers the leaf helpers; the composed public path is not annotated, so the property is observed rather than certified.

Owned Json.t runs at 730 MB/s

match json with
| Object fields -> ...
| Array items -> ...
| Int n -> ...
| Float f -> ...
| _ -> ...

Json.t arrays use shared scratch storage

Reusing that scratch array makes it long-lived

Amortized growth, but every young pointer write crosses the GC barrier.

For small arrays, parse directly into the result

Flattening object fields exposed a library gap

type assoc = {
  key : string;
  value : Json.t;
}

assoc# array
(* layout: value & value *)

value & value lacked a complete bulk-operation path

So the parser boxed associations

Fixture-dependent: from a 10% loss to an 8% win. A tradeoff forced by the missing operations, not a universal speedup.

Owned numeric leaves still allocate

Objects hit a library gap; leaves hit a language one.

Unboxed variants could avoid leaf blocks

The OxCaml parser simply does more work

What worked