Blog post · programming-languages, performance, compilers

Writing a DSL for high performance parallel programming in OxCaml

First published at blog.janestreet.com.

A Jane Street summer intern project: Nicholas Yang describes building an embedded DSL in OxCaml for writing SIMD kernels, replacing esoteric C inner loops used for options pricing and risk checks with portable, vectorized code, plus benchmarks and planned scheduling transformations.

*The following is part of a series of posts about 2026 summer intern projects—for more, see “What the interns have wrought, special jumbo 2026 edition”*

We have a lot of performance-critical SIMD code (single-instruction, multiple-data) running on CPUs across the firm. These are highly parallel programs where you run the same computation across arrays of data, in our case for options pricing or for low-latency risk checks. Because OCaml hasn’t historically exposed SIMD instructions, these programs often involve an inner loop written in fairly esoteric C. Writing these loops requires implementers to think carefully about hardware, and doing performance tuning, such as modifying unroll factors or vector widths, can require major changes to the code. Moreover, these programs are constrained to a specific instruction set. If we were to target a different architecture or a newer processor, we’d have to rewrite the program.

Blog post · programming-languages, performance, compilers

Writing a DSL for high performance parallel programming in OxCaml

First published at blog.janestreet.com.

A Jane Street summer intern project: Nicholas Yang describes building an embedded DSL in OxCaml for writing SIMD kernels, replacing esoteric C inner loops used for options pricing and risk checks with portable, vectorized code, plus benchmarks and planned scheduling transformations.

*The following is part of a series of posts about 2026 summer intern projects—for more, see “What the interns have wrought, special jumbo 2026 edition”*

We have a lot of performance-critical SIMD code (single-instruction, multiple-data) running on CPUs across the firm. These are highly parallel programs where you run the same computation across arrays of data, in our case for options pricing or for low-latency risk checks. Because OCaml hasn’t historically exposed SIMD instructions, these programs often involve an inner loop written in fairly esoteric C. Writing these loops requires implementers to think carefully about hardware, and doing performance tuning, such as modifying unroll factors or vector widths, can require major changes to the code. Moreover, these programs are constrained to a specific instruction set. If we were to target a different architecture or a newer processor, we’d have to rewrite the program.

):\n\n```\n# let quote = \u003c[2 + 3]> in \u003c[$quote * 4]>;;\n- : \u003c[int]> expr = \u003c[Base.( * ) (Base.( + ) 2 3) 4]>\n```\n\nSo rather than writing the standard recursive `power` function that computes `x^n`:\n\n```\n# let rec power n x =\n if n = 0 then 1 else x * power (n - 1) x;;\nval power : int -> int -> int = \u003cfun>\n```\n\nyou can write a `power_expr` function that creates a quoted expression that will compute\n`x^n` for a given `n`, effectively inlining and optimizing the recursive function into a\nsingle expression. This is a form of [partial\nevaluation](https://en.wikipedia.org/wiki/Partial_evaluation) where we’re able to take a\nfunction and produce a much faster version specialized to a particular value of `n`.\n\n```\n# let rec power_expr n xq =\n if n = 0 then \u003c[1]>\n else \u003c[$xq * $(power_expr (n - 1) xq)]>;;\nval power_expr : int -> \u003c[int]> expr -> \u003c[int]> expr @ once = \u003cfun>\n\n# \u003c[ fun x -> $(power_expr 5 \u003c[x]>) ]>;;\n- : \u003c[int -> int]> expr =\n\u003c[fun x -> Base.( * ) x (Base.( * ) x (Base.( * ) x (Base.( * ) x (Base.( * ) x 1))))]>\n```\n\nSai’s backend walked the DAG and emitted OxCaml code for each node. For instance, the\nbackend emits the following quoted OxCaml code for arithmetic expressions:\n\n```\nlet rec emit node =\n match node with\n | Add (x, y) -> \u003c[ F32.O.( + ) $(emit x) $(emit y) ]>\n | Mul (x, y) -> \u003c[ F32.O.( * ) $(emit x) $(emit y) ]>\n | Load (input, idx) -> \u003c[ Slice.Imm.unsafe_get $input $(emit idx) ]>\n```\n\nIf we were to compile a basic kernel such as:\n\n```\n(fun graph [ a; b; c ] [ Dim i ] -> exclave_\n let open (val Spmd.open_ graph) in\n let i = index i in\n F32.((a.!(i) +. b.!(i)) *. c.!(i)))\n```\n\nwe’d get a DAG that represents the arithmetic operations, and use that to generate quoted\nOxCaml code:\n\n```\nemit (Mul (Add (Load a, Load b), Load c))\n= \u003c[ F32.O.( * ) $(emit (Add (Load a, Load b))) $(emit (Load c)) ]>\n= \u003c[ F32.O.( * )\n (F32.O.( + ) $(emit (Load a)) $(emit (Load b)))\n $(emit (Load c)) ]>\n= \u003c[ F32.O.( * )\n (F32.O.( + )\n (Slice.Imm.unsafe_get a (I32.to_i64 i))\n (Slice.Imm.unsafe_get b (I32.to_i64 i)))\n (Slice.Imm.unsafe_get c (I32.to_i64 i)) ]>\n```\n\nSai implemented these emitters for all of the node types in the DAG, such as the `if_`,\n`if_var` and `select` control flow constructs.\n\n## Cross-checking and benchmarking every program and implementation\n\nAt this point, Sai needed to validate that his JIT implementation was both fast and\ncorrect. One strategy he used was to compare the JIT against a reference implementation.\nWe had previously implemented an interpreter that took the front-end representation and\ndirectly executed it. While extremely slow, we could be fairly confident that the\ninterpreter would have the correct behavior, so could be used to verify that the JIT was\nalso correct.\n\nSai wrote four example programs, including an implementation of Newton’s square root\nalgorithm and a kernel adapted from some production code, in plain OxCaml, C with AVX2\nintrinsics, C with AVX512 intrinsics, and as an SPMD kernel (which could be either\nexecuted by the interpreter or JIT compiled). Each combination was benchmarked on inputs\nof various sizes.\n\nSai also worked on an extensive test suite for all of the different language features and\nedge-cases. This suite included a test that generated random inputs with Quickcheck\ngenerators, then ran those inputs on the four example programs. Their outputs were\ncross-checked and compared bit by bit. He also wrote tests confirming that the code didn’t\nallocate on the heap.\n\n### How did the JIT do?\n\n[![Bar chart of the interpreter, plain OxCaml, and the first JIT for four kernels, as time relative to C with AVX2 on a wide scale; the interpreter is 237x to 1,267x slower than C, while the JIT and plain OxCaml are within 36x](https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-interpreter.png)](https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-interpreter.png)\n\nThe benchmarks found that the JIT was much faster than the interpreter. However, the JIT\nwas about the same speed (or slightly slower) than the manual OxCaml code and\nsignificantly slower than the C implementations. This wasn’t that surprising, since we\nhadn’t implemented any real optimizations or tuning in the compiler. Naturally, this\nneeded to change if we wanted to catch up to the C implementations.\n\n## Optimizing using an intermediate representation\n\nSai then started looking at adding optimizations to the compiler. With the current\ncompilation pipeline, this would have been slightly painful. Our front end representation\nwas not designed to be easily analyzed or optimized. While that wouldn’t have necessarily\nstopped us from doing analysis, it’s often a better idea to add an intermediate\nrepresentation (IR) that is more amenable to optimization. Sai implemented an IR based on\nA-normal form (ANF), a format where each intermediate value gets its own variable. This is\nthe IR that we saw in the previous section about optimizing away control flow:\n\nShow IR\n\n```\nlet%expect_test \"IR: euclidean\" =\n let lowered = For_testing.Ir.of_kernel (measure ~metric:Euclidean) in\n print_string (For_testing.Ir_body.to_string lowered.body);\n [%expect\n {|\n let n = shape[0]\n for i in n (normal) {\n let v = load_f32 in0[i]\n let v1 = load_f32 in1[i]\n let v2 = f32_sub v v1\n let v3 = f32_mul v2 v2\n store out[i] = v3\n }\n |}]\n;;\n\nlet%expect_test \"IR: manhattan\" =\n let lowered = For_testing.Ir.of_kernel (measure ~metric:Manhattan) in\n print_string (For_testing.Ir_body.to_string lowered.body);\n [%expect\n {|\n let n = shape[0]\n for i in n (normal) {\n let v = load_f32 in0[i]\n let v1 = load_f32 in1[i]\n let v2 = f32_sub v v1\n let v3 = f32 0.\n let v4 = f32_ge v2 v3\n let v5 = f32_sub v3 v2\n let v6 = select v4 v2 v5\n store out[i] = v6\n }\n |}]\n;;\n```\n\nThe IR is more verbose but easier to analyze. For example, because all intermediate values\nare assigned a variable, it becomes easy to remove dead code; just look if an intermediate\nvalue is used anywhere after its definition.\n\n### Designing the IR to make code generation trivial\n\nSai designed this IR with a key design principle in mind: Generating the final OxCaml code\nfrom the IR should be a trivial process. Any interesting compilation logic should end up\nexplicitly represented in the IR.\n\nOne instance of this principle shows up in how we model loops. As we mentioned before,\nkernels only declare *what* we do on each loop iteration, not *how* we loop over the code\nitself.\n\n```\n(fun graph [ x; scale ] [ Dim i ] -> exclave_\n let open (val Spmd.open_ graph) in\n let i = index i in\n F32.((x.!(i) *. broadcast scale.!(I32.lit #0l)) +. of_i32 i))\n```\n\nBut in the IR, we explicitly specify the loop, as well as load/store logic. That way, the\noptimizer can reason about how to re-order or unroll loops. For example, the above kernel\nwould produce the following IR:\n\n```\nlet n = shape[0]\nfor i in n (normal) {\n let v = load_f32 in0[i]\n let v1 = i32 0\n let v2 = load_f32 in1[v1]\n let v3 = f32_mul v v2\n let v4 = f32_of_i32 i\n let v5 = f32_add v3 v4\n store out[i] = v5\n}\n```\n\nThe optimizer can analyze this IR and see that `v1` and `v2` do not depend on `i` and\ntherefore can be lifted out of the loop:\n\n```\nlet n = shape[0]\nlet v1 = i32 0\nlet v2 = load_f32 in1[v1]\nfor i in n (normal) {\n let v = load_f32 in0[i]\n let v3 = f32_mul v v2\n let v4 = f32_of_i32 i\n let v5 = f32_add v3 v4\n store out[i] = v5\n}\n```\n\nIt can also rewrite the loop to process 4 elements at a time, which reduces the amount of\nbranching in the code.\n\n```\nlet n = shape[0]\nlet v1 = i32 0\nlet v2 = load_f32 in1[v1]\nfor io in div n 4 (normal) {\n let i_0 = add (mul io 4) 0\n let i_1 = add (mul io 4) 1\n let i_2 = add (mul io 4) 2\n let i_3 = add (mul io 4) 3\n let v_0 = load_f32 in0[i_0]\n let v_1 = load_f32 in0[i_1]\n let v_2 = load_f32 in0[i_2]\n let v_3 = load_f32 in0[i_3]\n let v3_0 = f32_mul v_0 v2\n let v3_1 = f32_mul v_1 v2\n let v3_2 = f32_mul v_2 v2\n let v3_3 = f32_mul v_3 v2\n let v4_0 = f32_of_i32 i_0\n let v4_1 = f32_of_i32 i_1\n let v4_2 = f32_of_i32 i_2\n let v4_3 = f32_of_i32 i_3\n let v5_0 = f32_add v3_0 v4_0\n let v5_1 = f32_add v3_1 v4_1\n let v5_2 = f32_add v3_2 v4_2\n let v5_3 = f32_add v3_3 v4_3\n store out[i_0] = v5_0\n store out[i_1] = v5_1\n store out[i_2] = v5_2\n store out[i_3] = v5_3\n}\n```\n\nBy making the IR fairly explicit, we’re able to reason about—and therefore optimize—the\ncode effectively.\n\n### Validating the IR backend\n\nLike with the previous backend implementation, Sai put in a lot of work to validate the\ncorrectness of the new compilation path. He added the new backend to the existing\ncross-validation logic across the test suite, then added expect tests that printed the IR\nand the emitted OxCaml for various examples, which helped us confirm that the behavior was\nexactly as expected.\n\nOnce we were confident that the new IR-based path was correct, Sai deleted the previous\nbackend.\n\n## How fast is the new backend?\n\nWith the current implementation, the IR backend generates essentially the same code as the\nfirst JIT, so the two perform about the same.\n\n[![Bar chart of plain OxCaml, the first JIT, and the IR JIT for four kernels, as time relative to C with AVX2; the two JIT backend bars are nearly the same length for every kernel](https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-ir-jit.png)](https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-ir-jit.png)\n\nHowever, optimizations are now significantly easier to add. We’re currently working on\nadding vectorization and constant hoisting to the compiler. Preliminary benchmarks have found\nthat these changes result in code that is on-par with our C AVX2 implementation.\n\n[![Bar chart of the vectorized JIT and plain OxCaml for four kernels at 65,536 elements, as time relative to C with AVX2; the vectorized JIT is within 1.4x of C for every kernel and matches C on newton sqrt](https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-vectorized.png)](https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-vectorized.png)\n\nWe’re also working on adding scheduling. Scheduling lets users customize how the kernel\nloops over the code with a sophisticated set of transformations like “split this loop into 8\npiece chunks, vectorize these chunks, then unroll by 4”. Intelligent scheduling is important\nfor getting the maximum possible performance out of the kernel. Eventually these schedules\ncould also be auto-generated and benchmarked, so that the compiler can find the optimal\none for your kernel.\n","body_html":"\u003cp>*The following is part of a series of posts about 2026 summer intern projects—for more,\nsee \u003ca href=\"https://blog.janestreet.com/wrought-2026/\" rel=\"nofollow ugc noopener\">“What the interns have wrought, special jumbo 2026\nedition”\u003c/a>*\u003c/p>\n\u003cp>We have a lot of performance-critical SIMD code (single-instruction, multiple-data)\nrunning on CPUs across the firm. These are highly parallel programs where you run the same\ncomputation across arrays of data, in our case for options pricing or for low-latency risk\nchecks. Because OCaml hasn’t historically exposed SIMD instructions, these programs often\ninvolve an inner loop written in fairly esoteric C. Writing these loops requires\nimplementers to think carefully about hardware, and doing performance tuning, such as\nmodifying unroll factors or vector widths, can require major changes to the code.\nMoreover, these programs are constrained to a specific instruction set. If we were to\ntarget a different architecture or a newer processor, we’d have to rewrite the program.\u003c/p>\n\u003cp>For his summer internship, Sai Konkimalla built a compiler for a domain specific language\n(DSL) that makes SIMD more ergonomic and widely accessible. The compiler takes advantage\nof \u003ca href=\"https://oxcaml.org/\" rel=\"nofollow ugc noopener\">OxCaml\u003c/a> features that were only very recently added to the\nlanguage, such as runtime metaprogramming, to enable users to write a kernel just once as\na regular-ish OxCaml function, then compile and run it on multiple architectures.\u003c/p>\n\u003ch2 id=\"single-program-multiple-data\">Single Program, Multiple Data\u003c/h2>\n\u003cp>To help solve the problem of SIMD code being rather difficult to write and maintain, our\nDSL uses the S\u003cstrong>P*\u003cem>MD, or “single *\u003c/em>program\u003c/strong>, multiple data” programming model. As\nopposed to SIMD intrinsics, SPMD is higher level and not tied to a specific instruction\nset. We might normally think of higher-level languages as slower, but with SPMD, a higher\nlevel of abstraction lets the compiler make better decisions about how to optimally use\nthe underlying hardware. This ability can lead to significantly faster code.\u003c/p>\n\u003cp>SPMD was popularized by CUDA (for Nvidia GPUs) and ISPC (for Intel CPUs). In this model,\nyou write a program describing what happens at each index of a loop, then the compiler\nconverts it into a parallel computation. For example, in CUDA:\u003c/p>\n\u003cpre>\u003ccode>__global__ void kernel(const float* x, float* out, int n) {\n int idx = blockIdx.x * blockDim.x + threadIdx.x;\n if (idx < n) {\n out[idx] = 2.0f * x[idx] + idx;\n }\n}\u003c/code>\u003c/pre>\n\u003cp>Notice how there’s no loop here: you only define the loop body, and the compiler decides\nhow to run it. In CUDA, when you launch a kernel on a GPU, you can declare how many blocks\nof threads to run and the GPU will schedule them accordingly.\u003c/p>\n\u003cp>In ISPC, \u003ccode>foreach\u003c/code> also abstracts away how the loop is actually executed:\u003c/p>\n\u003cpre>\u003ccode>export void kernel(uniform float x[], uniform float out[], uniform int n) {\n foreach (i = 0 ... n) {\n out[i] = 2.0f * x[i] + i;\n }\n}\u003c/code>\u003c/pre>\n\u003cp>In both cases, the compiler translates the code into low-level SIMD instructions. Not\nspecifying the exact instructions also means SPMD programs can benefit from future\nhardware improvements. If we get a new, faster CPU with a different instruction set, the\nSPMD compiler can seamlessly compile existing code to it.\u003c/p>\n\u003ch2 id=\"a-quick-overview-of-the-dsl\">A quick overview of the DSL\u003c/h2>\n\u003cp>Let’s go over an example of the DSL that Sai implemented. We start by defining the\nkernel’s signature, including its output type, input types, and the dimension of the\noutput:\u003c/p>\n\u003cpre>\u003ccode>Spmd.Kernel.create\n F32 (* output element type *)\n [ F32; F32 ] (* input slice types *)\n [ () ] (* one output dimension *)\n (fun graph [ x; scale] [ Dim i ] -> exclave_\n ...)\u003c/code>\u003c/pre>\n\u003cp>In this example, we’re writing a kernel that takes in two \u003ccode>F32\u003c/code> slices and returns one\n\u003ccode>F32\u003c/code> slice.\u003c/p>\n\u003cp>Future work on a ppx syntax extension will make it possible to rewrite the above simply\nas:\u003c/p>\n\u003cpre>\u003ccode>let%spmd kernel (x : f32 slice) (scale : f32) (i : dim) : f32 =\u003c/code>\u003c/pre>\n\u003cp>Next, we write the actual computation:\u003c/p>\n\u003cpre>\u003ccode>Spmd.Kernel.create\n F32 (* output element type *)\n [ F32; F32 ] (* input slice types *)\n [ () ] (* one output dimension *)\n (fun graph [ x; scale ] [ Dim i ] -> exclave_\n let open (val Spmd.open_ graph) in\n let i = index i in\n F32.((x.!(i) *. broadcast scale.!(I32.lit #0l)) +. of_i32 i))\u003c/code>\u003c/pre>\n\u003cp>Note the \u003ccode>let open (val Spmd.open_ graph) in\u003c/code>. This brings the DSL operations which\nconstruct a computational graph into scope. You can think of the \u003ccode>graph\u003c/code> value as proof\nthat you’re in the graph-construction phase, not the runtime of the generated program.\n(\u003ca href=\"https://github.com/janestreet/bonsai\" rel=\"nofollow ugc noopener\">Bonsai\u003c/a> uses a \u003ca href=\"https://github.com/janestreet/bonsai_web/blob/master/docs/guide/thinking_in_bonsai.md#what-is-bonsaigraph\" rel=\"nofollow ugc noopener\">similar\ntrick\u003c/a>\nfor creating its incremental graph.)\u003c/p>\n\u003cp>Like CUDA, we don’t write the kernel as a loop. Instead, the developer writes a function\nthat computes a single entry of the output slice, and the SPMD compiler generates code to\nloop over the output slice and compute the value at each index.\u003c/p>\n\u003cp>You may wonder why we loop over the \u003cem>output\u003c/em> and not the inputs. Looping over the output\nis easier to model because each iteration writes to exactly one location, so iterations\ncan be easily vectorized, reordered, or parallelized. If we were to loop over the inputs,\ndifferent iterations could write to the same output entry. The compiler would then have to\nreason about whether the writes could be re-ordered. By guaranteeing that each output\nentry is written exactly once, we can avoid this complexity.\u003c/p>\n\u003ch2 id=\"where-runtime-metaprogramming-comes-in\">Where runtime metaprogramming comes in\u003c/h2>\n\u003cp>One wrinkle with Sai’s project is that we wanted to execute the SPMD compiler at runtime.\nRuntime compilation (often called just-in-time or JIT compilation) is when the compiler\ngenerates code while the program is running. This gives us two main advantages: we don’t\nhave to worry about building for all potential target architectures at compile time, and\nwe can use data obtained at runtime for optimizations.\u003c/p>\n\u003cp>That latter point is especially important for generating high-performance code. When\nexecuting at runtime, the compiler has more data that it can use to optimize the code than\nit would when executing ahead-of-time. For example, our compiler can use runtime data to\ncompile away branch instructions, which can slow down execution by consuming CPU\nresources.\u003c/p>\n\u003cp>To implement our JIT compiler, we used runtime metaprogramming, a feature that lets us\ngenerate, compile, and evaluate OxCaml code at runtime by using the OxCaml compiler as a\nlibrary. As far as we know, Sai’s project was the first real program at Jane Street to use\nit. (He discovered some bugs in its implementation and helped report/reproduce them for\nthe OxCaml team.)\u003c/p>\n\u003cp>Let’s take a look at an example that illustrates the power of compiling at runtime. In\nthis code, we match on the \u003ccode>metric\u003c/code> to choose which algorithm to execute:\u003c/p>\n\u003cpre>\u003ccode>type metric =\n | Euclidean\n | Manhattan\n\nlet measure ~metric =\n Spmd.Kernel.create\n F32\n [ F32; F32 ]\n [ () ]\n (fun graph [ samples; targets ] [ Dim i ] -> exclave_\n let open (val Spmd.open_ graph) in\n let sample = samples.!(index i) in\n let target = targets.!(index i) in\n let diff = F32.(sample -. target) in\n match metric with\n | Euclidean -> F32.(diff *. diff)\n | Manhattan ->\n let zero = broadcast (F32.lit #0.s) in\n select F32.(diff >=. zero) ~pass:diff ~fail:F32.(zero -. diff))\n;;\u003c/code>\u003c/pre>\n\u003cp>With a normal OCaml program, this would create a branch and two code paths. Every time we\nexecute this code, we’d have to spend time evaluating the branch and picking the right\ncode path.\u003c/p>\n\u003cp>With the SPMD compiler, we can compile \u003cem>after\u003c/em> we know the value of \u003ccode>metric\u003c/code>. Then the JIT\ncompiler can evaluate the branch during compilation and produce more efficient code. For\nexample, here’s the intermediate representation that the code gets compiled into:\u003c/p>\n\u003cpre>\u003ccode>let%expect_test "IR: euclidean" =\n let lowered = For_testing.Ir.of_kernel (measure ~metric:Euclidean) in\n print_string (For_testing.Ir_body.to_string lowered.body);\n [%expect\n {|\n let n = shape[0]\n for i in n (normal) {\n let v = load_f32 in0[i]\n let v1 = load_f32 in1[i]\n let v2 = f32_sub v v1\n let v3 = f32_mul v2 v2\n store out[i] = v3\n }\n |}]\n;;\n\nlet%expect_test "IR: manhattan" =\n let lowered = For_testing.Ir.of_kernel (measure ~metric:Manhattan) in\n print_string (For_testing.Ir_body.to_string lowered.body);\n [%expect\n {|\n let n = shape[0]\n for i in n (normal) {\n let v = load_f32 in0[i]\n let v1 = load_f32 in1[i]\n let v2 = f32_sub v v1\n let v3 = f32 0.\n let v4 = f32_ge v2 v3\n let v5 = f32_sub v3 v2\n let v6 = select v4 v2 v5\n store out[i] = v6\n }\n |}]\n;;\u003c/code>\u003c/pre>\n\u003cp>Notice how we don’t branch on \u003ccode>metric\u003c/code> in the emitted code. Because the compiler knows the\nvalue of \u003ccode>metric\u003c/code>, it can emit just the chosen algorithm.\u003c/p>\n\u003ch2 id=\"implementing-the-front-end\">Implementing the front end\u003c/h2>\n\u003cp>Sai started his project by working on the compiler’s front end. The front end takes the\nkernel definition that we saw above and translates it into the following\n\u003ca href=\"https://dev.realworldocaml.org/gadts.html\" rel=\"nofollow ugc noopener\">GADT\u003c/a> that models a directed acyclic graph\n(DAG):\u003c/p>\n\u003cpre>\u003ccode>type (_ : any, _) node =\n | Literal : 'a Literal.t -> ('a, uniform) node\n | Broadcast : ('a, uniform) t -> ('a, varying) node\n | Load : { storage : 'a Storage.t; idx : (i32, 'u) t } -> ('a, 'u) node\n | Dimop : { op : ('a, 'u) Dimop.t; dim : 'd Dim.t } -> ('a, 'u) node\n | Binop : { op : ('o, 'x, 'y) Binop.t\n ; x : ('x, 'u) t; y : ('y, 'u) t } -> ('o, 'u) node\n | Unop : { op : ('o, 'x) Unop.t; x : ('x, 'u) t } -> ('o, 'u) node\n | Select : { cond : (bool#, varying) t\n ; pass : ('a, 'u) t; fail : ('a, 'u) t } -> ('a, varying) node\n | If : { cond : (bool#, uniform) t; then_; else_ } -> ('a, 'u) node\n | If_var : { cond : (bool#, varying) t; then_; else_ } -> ('a, varying) node\n\nand ('a : any, 'u) t = { node : ('a, 'u) node; ty : 'a Ty.t; id : int }\u003c/code>\u003c/pre>\n\u003cp>(The \u003ccode>'u\u003c/code> type variable in this GADT declares the expression’s \u003cem>rate\u003c/em>, which indicates\nwhether an expression is the same for every index in the entire output slice (\u003ccode>uniform\u003c/code>)\nor may change at each element in the slice (\u003ccode>varying\u003c/code>). In other words, it signals which\npieces of your computation only need to be computed once and which pieces need to be\ncomputed per index.)\u003c/p>\n\u003cp>Sai’s first task was to add support for numeric data types such as \u003ccode>I8\u003c/code>, \u003ccode>I16\u003c/code>, \u003ccode>I64\u003c/code>,\n\u003ccode>U8\u003c/code>–\u003ccode>U64\u003c/code> and \u003ccode>F64\u003c/code>, including arithmetic operations and conversion operators. After\nthat, he started implementing booleans and control flow constructs. Unlike most\nconventional programming languages, SPMD has some nuances to its control flow. Instead of\na single \u003ccode>if\u003c/code> construct, SPMD has three separate constructs all designed for parallel\nexecution:\u003c/p>\n\u003cdiv class=\"table-wrap\">\u003ctable>\u003cthead>\u003ctr>\u003cth>form\u003c/th>\u003cth>condition\u003c/th>\u003cth>semantics\u003c/th>\u003c/tr>\u003c/thead>\u003ctbody>\u003ctr>\u003ctd>\u003ccode>select\u003c/code>\u003c/td>\u003ctd>bool# varying\u003c/td>\u003ctd>The selected branch can vary per index. Both branches are always evaluated.\u003c/td>\u003c/tr>\u003ctr>\u003ctd>\u003ccode>if_\u003c/code>\u003c/td>\u003ctd>bool# uniform\u003c/td>\u003ctd>Every index picks the same branch. The untaken branch is not executed.\u003c/td>\u003c/tr>\u003ctr>\u003ctd>\u003ccode>if_var\u003c/code>\u003c/td>\u003ctd>bool# varying\u003c/td>\u003ctd>The selected branch can vary based on index. The untaken branch is not observable, but may or may not be executed.\u003c/td>\u003c/tr>\u003c/tbody>\u003c/table>\u003c/div>\n\u003cp>\u003ccode>if_var\u003c/code> lets you branch on data that varies per index (i.e., per SIMD lane). In the code\nbelow, the \u003ccode>if_var\u003c/code> allows the user to guard code that should only be run when \u003ccode>g\u003c/code> happens\nto be positive:\u003c/p>\n\u003cpre>\u003ccode>(fun graph [ group; totals; counts ] [ Dim i ] -> exclave_\n let open (val Spmd.open_ graph) in\n let g = group.!(index i) in\n let zero = broadcast (I32.lit #0l) in\n if_var I32.(g > zero)\n ~then_:F32.(totals.!(g) /. of_i32 counts.!(g))\n ~else_:(broadcast (F32.lit #0.s)))\u003c/code>\u003c/pre>\n\u003cp>The plain \u003ccode>if_\u003c/code> can’t do that, because the condition is a \u003ccode>bool# uniform\u003c/code> and therefore it\nmust be the same value for all lanes.\u003c/p>\n\u003cp>\u003ccode>select\u003c/code> and \u003ccode>if_var\u003c/code> are similar in that they both take in a condition of type \u003ccode>bool#\nvarying\u003c/code>. Where the two constructs differ is in how the branches are evaluated. With\n\u003ccode>if_var\u003c/code>, the compiler can decide whether to execute the branch that is \u003cem>not\u003c/em> chosen by\nthe condition, whereas with \u003ccode>select\u003c/code>, both branches are always evaluated. Further,\nif \u003ccode>if_var\u003c/code> executes an untaken branch, any potential side effects, such as raising\nexceptions, will not be observable. So \u003ccode>select true 1 (1/0)\u003c/code> will raise an exception,\nbut \u003ccode>{if,if_var} true 1 (1/0)\u003c/code> will not.\u003c/p>\n\u003ch2 id=\"writing-the-backend\">Writing the backend\u003c/h2>\n\u003cp>Usually, a high-performance JIT compiler would target a low-level language such as\nassembly or LLVM IR, which necessitates thinking quite hard about complicated details such\nas registers, pointers, and so on. Luckily, we didn’t have to do this, since we could use\nmetaprogramming to emit OxCaml code. This also lets us rely on optimizations in the OxCaml\ncompiler, saving us from having to implement them ourselves.\u003c/p>\n\u003cp>OxCaml’s metaprogramming features let us explicitly generate OxCaml code at runtime using\n\u003cem>quotes\u003c/em> and \u003cem>splices\u003c/em>. A quotation represents an OxCaml expression that is created at\nruntime and will be evaluated at a later time. For example, \u003ccode><[if Random.bool () then 42\nelse 5]>\u003c/code> represents an unevaluated expression of type \u003ccode>int\u003c/code>, so the quotation itself has\ntype \u003ccode><[int]> expr\u003c/code>. Once this expression is evaluated, its result will be an \u003ccode>int\u003c/code>.\u003c/p>\n\u003cp>Quotations can be interpolated into other quotations by splicing (\u003ccode>$\u003c/code>):\u003c/p>\n\u003cpre>\u003ccode># let quote = <[2 + 3]> in <[$quote * 4]>;;\n- : <[int]> expr = <[Base.( * ) (Base.( + ) 2 3) 4]>\u003c/code>\u003c/pre>\n\u003cp>So rather than writing the standard recursive \u003ccode>power\u003c/code> function that computes \u003ccode>x^n\u003c/code>:\u003c/p>\n\u003cpre>\u003ccode># let rec power n x =\n if n = 0 then 1 else x * power (n - 1) x;;\nval power : int -> int -> int = <fun>\u003c/code>\u003c/pre>\n\u003cp>you can write a \u003ccode>power_expr\u003c/code> function that creates a quoted expression that will compute\n\u003ccode>x^n\u003c/code> for a given \u003ccode>n\u003c/code>, effectively inlining and optimizing the recursive function into a\nsingle expression. This is a form of \u003ca href=\"https://en.wikipedia.org/wiki/Partial_evaluation\" rel=\"nofollow ugc noopener\">partial\nevaluation\u003c/a> where we’re able to take a\nfunction and produce a much faster version specialized to a particular value of \u003ccode>n\u003c/code>.\u003c/p>\n\u003cpre>\u003ccode># let rec power_expr n xq =\n if n = 0 then <[1]>\n else <[$xq * $(power_expr (n - 1) xq)]>;;\nval power_expr : int -> <[int]> expr -> <[int]> expr @ once = <fun>\n\n# <[ fun x -> $(power_expr 5 <[x]>) ]>;;\n- : <[int -> int]> expr =\n<[fun x -> Base.( * ) x (Base.( * ) x (Base.( * ) x (Base.( * ) x (Base.( * ) x 1))))]>\u003c/code>\u003c/pre>\n\u003cp>Sai’s backend walked the DAG and emitted OxCaml code for each node. For instance, the\nbackend emits the following quoted OxCaml code for arithmetic expressions:\u003c/p>\n\u003cpre>\u003ccode>let rec emit node =\n match node with\n | Add (x, y) -> <[ F32.O.( + ) $(emit x) $(emit y) ]>\n | Mul (x, y) -> <[ F32.O.( * ) $(emit x) $(emit y) ]>\n | Load (input, idx) -> <[ Slice.Imm.unsafe_get $input $(emit idx) ]>\u003c/code>\u003c/pre>\n\u003cp>If we were to compile a basic kernel such as:\u003c/p>\n\u003cpre>\u003ccode>(fun graph [ a; b; c ] [ Dim i ] -> exclave_\n let open (val Spmd.open_ graph) in\n let i = index i in\n F32.((a.!(i) +. b.!(i)) *. c.!(i)))\u003c/code>\u003c/pre>\n\u003cp>we’d get a DAG that represents the arithmetic operations, and use that to generate quoted\nOxCaml code:\u003c/p>\n\u003cpre>\u003ccode>emit (Mul (Add (Load a, Load b), Load c))\n= <[ F32.O.( * ) $(emit (Add (Load a, Load b))) $(emit (Load c)) ]>\n= <[ F32.O.( * )\n (F32.O.( + ) $(emit (Load a)) $(emit (Load b)))\n $(emit (Load c)) ]>\n= <[ F32.O.( * )\n (F32.O.( + )\n (Slice.Imm.unsafe_get a (I32.to_i64 i))\n (Slice.Imm.unsafe_get b (I32.to_i64 i)))\n (Slice.Imm.unsafe_get c (I32.to_i64 i)) ]>\u003c/code>\u003c/pre>\n\u003cp>Sai implemented these emitters for all of the node types in the DAG, such as the \u003ccode>if_\u003c/code>,\n\u003ccode>if_var\u003c/code> and \u003ccode>select\u003c/code> control flow constructs.\u003c/p>\n\u003ch2 id=\"cross-checking-and-benchmarking-every-program-and-implementation\">Cross-checking and benchmarking every program and implementation\u003c/h2>\n\u003cp>At this point, Sai needed to validate that his JIT implementation was both fast and\ncorrect. One strategy he used was to compare the JIT against a reference implementation.\nWe had previously implemented an interpreter that took the front-end representation and\ndirectly executed it. While extremely slow, we could be fairly confident that the\ninterpreter would have the correct behavior, so could be used to verify that the JIT was\nalso correct.\u003c/p>\n\u003cp>Sai wrote four example programs, including an implementation of Newton’s square root\nalgorithm and a kernel adapted from some production code, in plain OxCaml, C with AVX2\nintrinsics, C with AVX512 intrinsics, and as an SPMD kernel (which could be either\nexecuted by the interpreter or JIT compiled). Each combination was benchmarked on inputs\nof various sizes.\u003c/p>\n\u003cp>Sai also worked on an extensive test suite for all of the different language features and\nedge-cases. This suite included a test that generated random inputs with Quickcheck\ngenerators, then ran those inputs on the four example programs. Their outputs were\ncross-checked and compared bit by bit. He also wrote tests confirming that the code didn’t\nallocate on the heap.\u003c/p>\n\u003ch3 id=\"how-did-the-jit-do\">How did the JIT do?\u003c/h3>\n\u003cp>\u003ca href=\"https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-interpreter.png\" rel=\"nofollow ugc noopener\">\u003cimg src=\"https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-interpreter.png\" alt=\"Bar chart of the interpreter, plain OxCaml, and the first JIT for four kernels, as time relative to C with AVX2 on a wide scale; the interpreter is 237x to 1,267x slower than C, while the JIT and plain OxCaml are within 36x\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" />\u003c/a>\u003c/p>\n\u003cp>The benchmarks found that the JIT was much faster than the interpreter. However, the JIT\nwas about the same speed (or slightly slower) than the manual OxCaml code and\nsignificantly slower than the C implementations. This wasn’t that surprising, since we\nhadn’t implemented any real optimizations or tuning in the compiler. Naturally, this\nneeded to change if we wanted to catch up to the C implementations.\u003c/p>\n\u003ch2 id=\"optimizing-using-an-intermediate-representation\">Optimizing using an intermediate representation\u003c/h2>\n\u003cp>Sai then started looking at adding optimizations to the compiler. With the current\ncompilation pipeline, this would have been slightly painful. Our front end representation\nwas not designed to be easily analyzed or optimized. While that wouldn’t have necessarily\nstopped us from doing analysis, it’s often a better idea to add an intermediate\nrepresentation (IR) that is more amenable to optimization. Sai implemented an IR based on\nA-normal form (ANF), a format where each intermediate value gets its own variable. This is\nthe IR that we saw in the previous section about optimizing away control flow:\u003c/p>\n\u003cp>Show IR\u003c/p>\n\u003cpre>\u003ccode>let%expect_test "IR: euclidean" =\n let lowered = For_testing.Ir.of_kernel (measure ~metric:Euclidean) in\n print_string (For_testing.Ir_body.to_string lowered.body);\n [%expect\n {|\n let n = shape[0]\n for i in n (normal) {\n let v = load_f32 in0[i]\n let v1 = load_f32 in1[i]\n let v2 = f32_sub v v1\n let v3 = f32_mul v2 v2\n store out[i] = v3\n }\n |}]\n;;\n\nlet%expect_test "IR: manhattan" =\n let lowered = For_testing.Ir.of_kernel (measure ~metric:Manhattan) in\n print_string (For_testing.Ir_body.to_string lowered.body);\n [%expect\n {|\n let n = shape[0]\n for i in n (normal) {\n let v = load_f32 in0[i]\n let v1 = load_f32 in1[i]\n let v2 = f32_sub v v1\n let v3 = f32 0.\n let v4 = f32_ge v2 v3\n let v5 = f32_sub v3 v2\n let v6 = select v4 v2 v5\n store out[i] = v6\n }\n |}]\n;;\u003c/code>\u003c/pre>\n\u003cp>The IR is more verbose but easier to analyze. For example, because all intermediate values\nare assigned a variable, it becomes easy to remove dead code; just look if an intermediate\nvalue is used anywhere after its definition.\u003c/p>\n\u003ch3 id=\"designing-the-ir-to-make-code-generation-trivial\">Designing the IR to make code generation trivial\u003c/h3>\n\u003cp>Sai designed this IR with a key design principle in mind: Generating the final OxCaml code\nfrom the IR should be a trivial process. Any interesting compilation logic should end up\nexplicitly represented in the IR.\u003c/p>\n\u003cp>One instance of this principle shows up in how we model loops. As we mentioned before,\nkernels only declare \u003cem>what\u003c/em> we do on each loop iteration, not \u003cem>how\u003c/em> we loop over the code\nitself.\u003c/p>\n\u003cpre>\u003ccode>(fun graph [ x; scale ] [ Dim i ] -> exclave_\n let open (val Spmd.open_ graph) in\n let i = index i in\n F32.((x.!(i) *. broadcast scale.!(I32.lit #0l)) +. of_i32 i))\u003c/code>\u003c/pre>\n\u003cp>But in the IR, we explicitly specify the loop, as well as load/store logic. That way, the\noptimizer can reason about how to re-order or unroll loops. For example, the above kernel\nwould produce the following IR:\u003c/p>\n\u003cpre>\u003ccode>let n = shape[0]\nfor i in n (normal) {\n let v = load_f32 in0[i]\n let v1 = i32 0\n let v2 = load_f32 in1[v1]\n let v3 = f32_mul v v2\n let v4 = f32_of_i32 i\n let v5 = f32_add v3 v4\n store out[i] = v5\n}\u003c/code>\u003c/pre>\n\u003cp>The optimizer can analyze this IR and see that \u003ccode>v1\u003c/code> and \u003ccode>v2\u003c/code> do not depend on \u003ccode>i\u003c/code> and\ntherefore can be lifted out of the loop:\u003c/p>\n\u003cpre>\u003ccode>let n = shape[0]\nlet v1 = i32 0\nlet v2 = load_f32 in1[v1]\nfor i in n (normal) {\n let v = load_f32 in0[i]\n let v3 = f32_mul v v2\n let v4 = f32_of_i32 i\n let v5 = f32_add v3 v4\n store out[i] = v5\n}\u003c/code>\u003c/pre>\n\u003cp>It can also rewrite the loop to process 4 elements at a time, which reduces the amount of\nbranching in the code.\u003c/p>\n\u003cpre>\u003ccode>let n = shape[0]\nlet v1 = i32 0\nlet v2 = load_f32 in1[v1]\nfor io in div n 4 (normal) {\n let i_0 = add (mul io 4) 0\n let i_1 = add (mul io 4) 1\n let i_2 = add (mul io 4) 2\n let i_3 = add (mul io 4) 3\n let v_0 = load_f32 in0[i_0]\n let v_1 = load_f32 in0[i_1]\n let v_2 = load_f32 in0[i_2]\n let v_3 = load_f32 in0[i_3]\n let v3_0 = f32_mul v_0 v2\n let v3_1 = f32_mul v_1 v2\n let v3_2 = f32_mul v_2 v2\n let v3_3 = f32_mul v_3 v2\n let v4_0 = f32_of_i32 i_0\n let v4_1 = f32_of_i32 i_1\n let v4_2 = f32_of_i32 i_2\n let v4_3 = f32_of_i32 i_3\n let v5_0 = f32_add v3_0 v4_0\n let v5_1 = f32_add v3_1 v4_1\n let v5_2 = f32_add v3_2 v4_2\n let v5_3 = f32_add v3_3 v4_3\n store out[i_0] = v5_0\n store out[i_1] = v5_1\n store out[i_2] = v5_2\n store out[i_3] = v5_3\n}\u003c/code>\u003c/pre>\n\u003cp>By making the IR fairly explicit, we’re able to reason about—and therefore optimize—the\ncode effectively.\u003c/p>\n\u003ch3 id=\"validating-the-ir-backend\">Validating the IR backend\u003c/h3>\n\u003cp>Like with the previous backend implementation, Sai put in a lot of work to validate the\ncorrectness of the new compilation path. He added the new backend to the existing\ncross-validation logic across the test suite, then added expect tests that printed the IR\nand the emitted OxCaml for various examples, which helped us confirm that the behavior was\nexactly as expected.\u003c/p>\n\u003cp>Once we were confident that the new IR-based path was correct, Sai deleted the previous\nbackend.\u003c/p>\n\u003ch2 id=\"how-fast-is-the-new-backend\">How fast is the new backend?\u003c/h2>\n\u003cp>With the current implementation, the IR backend generates essentially the same code as the\nfirst JIT, so the two perform about the same.\u003c/p>\n\u003cp>\u003ca href=\"https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-ir-jit.png\" rel=\"nofollow ugc noopener\">\u003cimg src=\"https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-ir-jit.png\" alt=\"Bar chart of plain OxCaml, the first JIT, and the IR JIT for four kernels, as time relative to C with AVX2; the two JIT backend bars are nearly the same length for every kernel\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" />\u003c/a>\u003c/p>\n\u003cp>However, optimizations are now significantly easier to add. We’re currently working on\nadding vectorization and constant hoisting to the compiler. Preliminary benchmarks have found\nthat these changes result in code that is on-par with our C AVX2 implementation.\u003c/p>\n\u003cp>\u003ca href=\"https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-vectorized.png\" rel=\"nofollow ugc noopener\">\u003cimg src=\"https://blog.janestreet.com/writing-a-dsl-for-high-performance-parallel-programming-in-oxcaml/benchmark-vectorized.png\" alt=\"Bar chart of the vectorized JIT and plain OxCaml for four kernels at 65,536 elements, as time relative to C with AVX2; the vectorized JIT is within 1.4x of C for every kernel and matches C on newton sqrt\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" />\u003c/a>\u003c/p>\n\u003cp>We’re also working on adding scheduling. Scheduling lets users customize how the kernel\nloops over the code with a sophisticated set of transformations like “split this loop into 8\npiece chunks, vectorize these chunks, then unroll by 4”. Intelligent scheduling is important\nfor getting the maximum possible performance out of the kernel. Eventually these schedules\ncould also be auto-generated and benchmarked, so that the compiler can find the optimal\none for your kernel.\u003c/p>","headings":[{"level":2,"text":"Single Program, Multiple Data","id":"single-program-multiple-data"},{"level":2,"text":"A quick overview of the DSL","id":"a-quick-overview-of-the-dsl"},{"level":2,"text":"Where runtime metaprogramming comes in","id":"where-runtime-metaprogramming-comes-in"},{"level":2,"text":"Implementing the front end","id":"implementing-the-front-end"},{"level":2,"text":"Writing the backend","id":"writing-the-backend"},{"level":2,"text":"Cross-checking and benchmarking every program and implementation","id":"cross-checking-and-benchmarking-every-program-and-implementation"},{"level":3,"text":"How did the JIT do?","id":"how-did-the-jit-do"},{"level":2,"text":"Optimizing using an intermediate representation","id":"optimizing-using-an-intermediate-representation"},{"level":3,"text":"Designing the IR to make code generation trivial","id":"designing-the-ir-to-make-code-generation-trivial"},{"level":3,"text":"Validating the IR backend","id":"validating-the-ir-backend"},{"level":2,"text":"How fast is the new backend?","id":"how-fast-is-the-new-backend"}]}}