OxCaml Basics

Checked control over allocation, representation, and parallelism

A three-hour technical course for OCaml engineers learning OxCaml's performance-oriented type system.

OxCaml Basics mark

The route

  1. 00Why OxCaml existssafe, convenient, predictable control over performance-critical aspects of program behavior
  2. 01Allocationlocality, stack_, exclave_
  3. 02Representationlayouts, unboxing, or_null
  4. 03Parallelismcontention and portability

What makes OCaml great?

Safety

The type system catches many mistakes at compile time before your code runs.

Agility

Algebraic data types, first-class functions, and modules make OCaml expressive and scalable.

Speed

Native-code compilation gives OCaml strong and predictable performance.

Limitations of OCaml

GC pauses

Low-latency code needs to avoid GC pauses.

Value representation

Uniform value representation can force inefficient layouts.

Unsafe parallelism

OCaml 5 parallelism can introduce subtle data races.

Where OxCaml fits

High-level runtimeruntime handles lifetimes and layout
Systems controlprogrammer controls lifetimes and layout
Unsafemistakes crash program
JavaScript high-level runtime, unchecked
C++ systems control, unchecked
Safecompiler catches mistakes
OCaml safe high-level runtime
Rust safe systems control
OxCaml expands OCaml into safe systems control

How OxCaml addresses these limitations

Stack allocation

Avoid heap allocation without creating dangling stack pointers.

Data layout

Remove boxes and pointer hops without representation mismatches.

Safe parallelism

Use more cores without introducing data races.

Module 1 today

Module 2 today

Module 3 today

Module 01

Locality and stack allocation

  • Understand why heap allocation can be problematic.
  • Use stack allocation safely with locality modes.
  • Understand and fix locality errors.
  • Use modalities to preserve global fields inside local containers.

Why stack allocation matters

OxCaml allocation is cheap, but GC is high latency.

Solution

stack allocation

Where values can live

GC heap

ordinary OCaml allocations

the heap fills up

the GC scans and marks live objects

the GC removes unreachable objects

GC pauses can be slow

Allocation stack

new in OxCaml

empty allocation stack

separate from the call stack

start a region

allocate into the current region

allocate into the current region

start a new region

allocate into the current region

allocate into the current region

start a new region

allocate into the current region

allocate into the current region

deallocation drops region C

then deallocation drops region B

A small stack allocation example

Stack allocate values with stack_.

OxCaml can often infer stack allocation; stack_ makes it a requirement.

The current allocation region is cleared before the function returns.

Ex01_stack_sum.ml
(* Stack allocation example. *) let rec sum xs = match xs with | [] -> 0 | x::xs' -> x + sum xs' let sum3 a b c = let xs = stack_ [a;b;c] in let n = sum xs in (* xs gets deallocated here *) n let () = let n = sum3 1 2 3 in print_endline (string_of_int n)

Stack allocated values cannot escape their region

A callee cannot secretly keep a stack-allocated value after the caller region is gone.

Expected outcome: the call to sum is rejected.

Ex01_stack_sum_escape.ml
(* Stack allocation example. *) let saved = ref [] let rec sum xs = match xs with | [] -> 0 | x::xs' -> saved := xs :: !saved; x + sum xs' let sum3 a b c = let xs = stack_ [a;b;c] in let n = sum xs in (* xs gets deallocated here *) n let () = let n = sum3 1 2 3 in print_endline (string_of_int n)

Returning stack allocated values cannot escape their region

The integer result can return, but the stack-allocated list cannot.

Expected outcome: returning xs is rejected.

Ex01_stack_sum_return_escape.ml
(* Stack allocation example. *) let rec sum xs = match xs with | [] -> 0 | x::xs' -> x + sum xs' let sum3 a b c = let xs = stack_ [a;b;c] in let n = sum xs in (* xs gets deallocated here *) n, xs let () = let n, _xs = sum3 1 2 3 in print_endline (string_of_int n)

But sometimes we want to return stack allocated values

exclave_ builds the returned value in the caller's region.

The caller can use the returned list as a local value.

Ex01_stack_sum_exclave_return.ml
(* Stack allocation example. *) let rec sum (xs : int list @ local) = match xs with | [] -> 0 | x::xs' -> x + sum xs' let sum3 a b c = exclave_ let xs = stack_ [a;b;c] in let n = sum xs in n, xs let () = let n, xs = sum3 1 2 3 in print_endline (string_of_int n); print_endline (string_of_int (sum xs))

How OxCaml manages the allocation stack

Normal functions get their own region.

Normal function

let f x =
  ...
  result
compiles to
let f x =
  let region = start_region () in
  ...
  end_region region;
  result

start_region () returns the current allocation stack pointer.

end_region region resets the allocation stack pointer to that saved pointer.

exclave_ uses the parent region.

exclave_ result

let f x =
  exclave_
  ...
  result
compiles to
let f x =
  ...
  result

How OxCaml manages the allocation stack: tail calls

Region ends before tail calls.

Tail-call function

let rec loop x =
  ...
  loop next_x
compiles to
let rec loop x =
  let region = start_region () in
  ...
  end_region region;
  tail call loop next_x

[@nontail] keeps the region open, so stack values can be passed to the call.

Non-tail call

let f x =
  ...
  g x [@nontail]
compiles to
let f x =
  let region = start_region () in
  ...
  let result = g x in
  end_region region;
  result

How OxCaml manages the allocation stack: mid-function exclave_

Middle exclave_

let f x =
  let xs = compute_list x in
  let n = sum xs in
  exclave_
  build_result n
compiles to
let f x =
  let region = start_region () in
  let xs = compute_list x in
  let n = sum xs in
  end_region region;
  build_result n

If exclave_ is at the beginning, OxCaml starts the region and ends it immediately.

That has the same effect as not starting a region.

How OxCaml checks stack allocation safety: the locality axis

lives on the GC heap
x @ global
  • safe to store or return
  • ordinary heap values have this mode
→
may live in the current region
x @ local
  • may point into current region
  • cannot escape this region

Locality answers: how long does this value live?

How OxCaml tracks locality

Every value

x : a @ global
x : a @ local

Values have locality, just as they have types. OxCaml tracks the locality of every variable and expression.

Functions

f : a @ global -> b @ global
f : a @ global -> b @ local
f : a @ local  -> b @ global
f : a @ local  -> b @ local

Function signatures specify locality.

Locality is deep

type r = { field : a }

x : r @ global
x.field : a @ global

x : r @ local
x.field : a @ local

Projection uses the locality of the record value.

OxCaml has other mode axes besides locality. We will see that later.

Locality rules for stack_ and exclave_

stack_ expr

The result is at @ local.

let xs = stack_ [1; 2; 3]
(* xs : int list @ local *)

exclave_ expr

Allows @ local return.

let f () : int list @ local =
  exclave_
  stack_ [1; 2; 3]

after exclave_

Deletes @ local variables.

let f () =
  let y = stack_ [1] in
  exclave_
  let z = stack_ [2] in
  (* z ok *)
  (* y bad *)

Locality in action

Ex01_locality_in_action.ml
(* Stack allocation example. *) let rec sum xs = match xs with | [] -> 0 | x::xs' -> x + sum xs' let sum3 a b c = let xs = stack_ [a;b;c] in let n = sum xs in (* xs gets deallocated here *) n, xs let () = let n, _xs = sum3 1 2 3 in print_endline (string_of_int n)

How OxCaml checks stack allocation safety:
functions and exclave_

Source

let f (x : int list @ local) =
let y = stack_ [1; 2; 3] in
ignore (sum y);
exclave_
let z = stack_ [4; 5; 6] in
sum x + sum z
(* not allowed here: sum y *)
compiles to

Region view

let f x =
let region = start_region () in
let y = stack_ [1; 2; 3] in
ignore (sum y);
end_region region;
(* y dies here *)
let z = stack_ [4; 5; 6] in
sum x + sum z
(* x came from caller *)

exclave_ ends the function's current region. Arguments from the caller can still be used; values allocated before exclave_ cannot.

Local parameters prevent escape

The with_scratch body can use the temporary state during the call, but cannot retain it, and this is forced by the @ local parameter.

Ex01_with_scratch_local_function.ml
type scratch = { mutable total : int } let with_scratch (f : scratch @ local -> 'a) = let s = stack_ { total = 0 } in f s [@nontail] let add_with_scratch x y = with_scratch (fun s -> s.total <- x + y; s.total)

Submoding: use global data locally

escape s type-checks because s already has global mode.

length s then uses the same value at the more restrictive @ local mode.


@ local data is not always on the allocation stack. Heap data can be used locally too. Stack data cannot be used as global.

Ex01_submoding_global_string_used_locally.ml
let saved : string list ref = ref [] let escape (s : string @ global) = saved := s :: !saved let length (s : string @ local) = String.length s let global_string @ global = "hello" (* the string is global *) let demo () = escape global_string; (* allowed because global_string is global *) length global_string (* global_string is submoded to local *) let () = print_endline (string_of_int (demo ()))

Problem: plain local containers lose the global mode

The top-level string starts at @ global.

After matching through outer : string list @ local, the extracted inner is only local.


An ordinary list node does not remember that its element was global. Using the outer list at local mode also uses everything reached through it at local mode.

Ex01_plain_local_container_forgets_global_string.ml
let saved : string list ref = ref [] let escape (s : string @ global) = saved := s :: !saved let length (s : string @ local) = String.length s let global_string @ global = "hello" (* the string is global *) let demo () = escape global_string; (* allowed because global_string is global *) let outer = stack_ [global_string] in (* global_string is submoded to local *) match outer with | [] -> () | inner :: _ -> escape inner (* we lost the information that the list elements are @ global *)

Solution: modalities

Default: locality is deep

type 'a box = { field : 'a }

r : 'a box @ global
r.field : 'a @ global

r : 'a box @ local
r.field : 'a @ local

Ordinary field projection uses the locality of the record value.

@@ global field

type 'a box =
  { field : 'a @@ global }

r : 'a box @ global
r.field : 'a @ global

r : 'a box @ local
r.field : 'a @ global

The field stays global even when the record value is local.

Construction

type 'a box =
  { field : 'a @@ global }

let r =
  stack_ { field = inner }

r : 'a box @ local
inner : 'a @ global

Even a local record requires the field value at @ global.

A field modality is an exception to ordinary deep mode propagation.

Modalities preserve the global mode for inner data

The outer list is local, while the inner string is global.

A local list of global strings: the field modality preserves the global mode.

Ex01_global_wrapper_preserves_inner_string_globality.ml
type 'a global = { global : 'a @@ global } let saved : string list ref = ref [] let escape (s : string @ global) = saved := s :: !saved let demo () = let inner @ global = "hello" in escape inner; (* allowed because inner @ global *) let outer = stack_ [{ global = inner }] in (* modality preserves @ global *) match outer with | [] -> () | inner :: _ -> escape inner.global (* allowed because inner.global @ global *)

Locality: the heap and stack picture with modalities

Runtime stack and GC heap regions with compile-time braces for local modes, submoded heap data, and global data preserved by an @@ global modality.

Some types do not care about locality: mode crossing

Immediate

let id_local_int (x : int @ local) : int @ global =
  x

No lifetime-sensitive heap block.

Pointer

let id_local_string
  (x : string @ local) : string @ global =
  x

Rejected: the string may point into a local region.

Quiz: which field modality is allowed?

Locality

record r @ global
field r.x @ local

record r @ local
field r.x @ global

Which one is allowed?

Portability

record r @ nonportable
field r.x @ portable

record r @ portable
field r.x @ nonportable

Which one is allowed?

Contention

record r @ uncontended
field r.x @ contended

record r @ contended
field r.x @ uncontended

Which one is allowed?

Allocation recap

local/global controls lifetime and escape.

stack_ forces the next allocation onto the allocation stack.

exclave_ builds a local result in the caller region.

Module 02

Value layouts and unboxing

  • Understand immediate words vs heap-block pointers.
  • Understand run-time heap structure.
  • Spot allocation and indirection in OxCaml types.
  • Use unboxed layouts to avoid pointer indirection and allocation.

Uniform value representation:
every ordinary OCaml value is one word

Immediate value

63 bits of immediate data1

int, char, bool, unit, etc. use this shape.

Pointer value

aligned heap address0
heap block
header wordtag, size, scan info
payload 0value or raw data
...
payload Nvalue or raw data

Records, tuples, arrays, etc. use this shape.

Uniform value representation is powerful

Source

let duplicate x = (x, x)

let plain_value_integer =
  duplicate 5

let plain_value_tuple =
  duplicate (1, 2, 3)

type quote =
  { symbol : string
  ; price : int
  ; mutable size : int
  }

let plain_value_record =
  duplicate { symbol = "ABC"; price = 10; size = 100 }

Runtime model

The runtime, GC, and compiler all agree on one value representation. Polymorphic functions are only compiled once.

Plain values: immediate word or pointer word

Integer source

let plain_value_integer =
  5

Run-time layout

Tuple source

let plain_value_tuple =
  (1, 2, 3)

Run-time layout

A tuple is still one OCaml value, but that value word points to a heap block.

Records have the same heap-block shape

Source

type quote =
  { symbol : string
  ; price : int
  ; mutable size : int
  }

let plain_value_record =
  { symbol = "OxCaml rocks"
  ; price = 101
  ; size = 7
  }

Run-time layout

Variant constructors use header tags

Source

type tree =
  | Zero
  | One of tree
  | Two of tree * tree

let simple_tree =
  Two
    (One (One Zero),
     Zero)

Run-time layout

Constructors with payload allocate blocks; the header tag distinguishes the constructor.

Boxed numeric values add allocation

Source

let boxed_numeric_values =
  (3.5, 456L)

Run-time layout

The tuple points to separate blocks for the boxed numeric payloads.

Unboxed types remove specific boxes

Source

let unboxed_numeric_values =
  #(#3.5, #456L)

Run-time layout

The product components are carried directly as raw words.

Unboxed records can inline their fields

Source

type unboxed_point =
  #{ x : float#
   ; y : float# }

type sample =
  { label : string
  ; point : unboxed_point
  ; count : int
  }

let outer_record_with_unboxed_point =
  { label = "p"
  ; point =
      #{ x = #1.0
       ; y = #2.5 }
  ; count = 7
  }

Run-time layout

Kinds: the compiler tracks the shape of every type

The new unboxed types do not have the classic one-word shape, so the compiler must know which shape each type has.

For that, OxCaml has kinds: types of types. The kind of a type describes the shape of its values.

The kind value describes the classic OCaml shape. New kinds such as float64 and product kinds describe the new shapes.

kind_examples.ml
(* The classic one-word shape. *) type t1 : value = string type t2 : value = int (* The new shapes. *) type t3 : float64 = float# type t4 : value & bits64 = #(string * int64#)

The wrong kind is a type error

Kind annotations are checked, not decorative.


A string is a one-word value, so it cannot be declared with kind float64.

kind_mismatch.ml
type ok : float64 = float# type bad : float64 = string

or_null uses null or the payload representation

Missing ordinary option

let ordinary_none_int_option = (None : int option)

Present ordinary option

let ordinary_some_int_option = Some 7

Missing or_null

let or_null_null_value = (Null : int or_null)

Present or_null

let or_null_this_int = (This 7 : int or_null)

Each diagram is one root value. Some 7 allocates a wrapper block; This 7 is represented like the integer payload.

or_null cannot be nested

Null already uses the all-zero word.


If the inner type is string or_null, it already may be null. The outer or_null would need the same null word for a second missing case.


The layout tracks this: or_null needs a non-null value payload, but string or_null has layout value_or_null.

or_null_cannot_be_nested.ml
type nested = string or_null or_null

Ordinary polymorphic functions expect values

duplicate is inferred for ordinary one-word values: its type parameter defaults to kind value.


An unboxed point has layout float64 & float64, so it is not accepted as that argument.

ordinary_duplicate_rejects_unboxed_point.ml
type point = #{ x : float#; y : float# } let duplicate x = (x, x) let bad = duplicate #{ x = #1.0; y = #2.0 }

Kinds on type parameters

The same kind annotations also go on type parameters. Here they say the argument may have the unboxed point layout.


(The result is still a boxed record in this example.)

kinded_duplicate_accepts_unboxed_point.ml
type point = #{ x : float#; y : float# } type ('a : float64 & float64) duplicated = { first : 'a ; second : 'a } let duplicate_unboxed : ('a : float64 & float64). 'a -> 'a duplicated = fun x -> { first = x; second = x } let ok = duplicate_unboxed #{ x = #1.0; y = #2.0 }

Templates reduce repetition

Template source

let%template[@kind k = (value, value & value)] id
  : ('a : k). 'a -> 'a =
  fun x -> x

Schematic expansion

let id
  : ('a : value). 'a -> 'a =
  fun x -> x

let id__'value_value'
  : ('a : value & value). 'a -> 'a =
  fun x -> x

Calls in source

let a = id 5

let b = (id [@kind value & value]) #(1, 2)

Expanded calls

let a = id 5

let b = id__'value_value' #(1, 2)

One source pattern can generate multiple checked definitions with different calling conventions.

OxCaml is a work in progress. Future layout-polymorphic definitions are intended to reduce this template pattern.

Representation recap

Ordinary values

One word: immediate data or pointer to a heap block.

Unboxed layouts

Remove selected product or record boxes where the layout is used.

or_null

Like option, but does not allocate.

Module 03

Parallelism: contention and portability

  • Run structured fork/join and detached spawn.
  • Understand what a data race is.
  • Understand how OxCaml prevents data races with modes.
  • See how fork/join and spawn express their requirements in types.

Two Ways to Run Work in Parallel

fork_join2

let (left, right) =
  Toy.fork_join2
    (fun () -> left_work ())
    (fun () -> right_work ())
in
combine left right

Children run in parallel; parent resumes after both finish.

spawn

let _ =
  Toy.spawn (fun () -> worker ())
in
parent_side_effect ()

Spawned worker runs in parallel; parent continues immediately.

Example: Doing work in parallel

fork_join_fresh_buffer.ml
let bits_to_string bits = let buf = Buffer.create 0 in List.iter (fun bit -> Buffer.add_char buf (if bit then '1' else '0')) bits; Buffer.contents buf let strings_in_parallel () = let (left, right) = Toy.fork_join2 (fun () -> bits_to_string [true; false; true]) (fun () -> bits_to_string [false; true; false]) in left ^ "\n" ^ right let () = print_endline "The output is:"; print_endline (strings_in_parallel ())
Separate workspaces for fresh buffers

Unsafe optimization: pull the buffer allocation to the top level

fork_join_shared_buffer.ml
let buf = Buffer.create 0 let bits_to_string bits = Buffer.clear buf; List.iter (fun bit -> Buffer.add_char buf (if bit then '1' else '0')) bits; Buffer.contents buf let strings_in_parallel () = let (left, right) = Toy.fork_join2 (fun () -> bits_to_string [true; false; true]) (fun () -> bits_to_string [false; true; false]) in left ^ "\n" ^ right
Shared workspace for one top-level buffer

Two parallel writes target the same buffer:
The shared buffer creates a data race.

What is a data race?

danger shape 1: two writes

let r = ref 0

Toy.fork_join2
  (fun _ -> incr r)
  (fun _ -> incr r)

danger shape 2: one write and one read

let r = ref 0

Toy.fork_join2
  (fun _ -> incr r)
  (fun _ -> !r)

overlap rule

overlapping operationreadwrite
readsaferace
writeracerace

Two parallel reads are fine. Two racing writes are not allowed. A racing read and write is not allowed either.

The OxCaml compiler checks for data races

danger shape 1: two writes
let bad_two_writes () = let r = ref 0 in Toy.fork_join2 (fun () -> incr r) (fun () -> incr r)
danger shape 2: one write and one read
let bad_read_and_write () = let r = ref 0 in Toy.fork_join2 (fun () -> incr r) (fun () -> !r)

How the OxCaml compiler checks for data races

fork/join

type t = { id : int; mutable hits : int }

Toy.fork_join2
  (fun () ->
     x.id          (* ✓ immutable read *)
     x.hits        (* ✓ mutable read *)
     x.hits <- n   (* ✕ mutable write *))
  (fun () -> right_work ())
  • ✅ immutable read allowed
  • ✅ mutable read allowed
  • ❌ mutable write disallowed

spawn

type t = { id : int; mutable hits : int }

Toy.spawn (fun () ->
        x.id          (* ✓ immutable read *)
        x.hits        (* ✕ mutable read *)
        x.hits <- n   (* ✕ mutable write *))
        ​
  • ✅ immutable read allowed
  • ❌ mutable read disallowed
  • ❌ mutable write disallowed

Contention modes describe mutable access

sequential context
x @ uncontended
  • owned by us
  • read and write mutable fields
  • ordinary single-owner access
→
inside fork/join
x @ shared
  • shared ownership
  • read mutable fields
  • no mutable writes
→
inside spawn
x @ contended
  • owned by another
  • immutable fields only
  • some other user may write

Contention answers: at this use site, what access do I have to mutable components?

Field access has mode requirements

immutable field

x.id

works even when x is contended

mutable read

x.hits

needs x at least shared

mutable write

x.hits <- x.hits + 1

needs x @ uncontended

A direct field operation succeeds or fails according to the variable's contention mode.

How modes propagate

Every value

x : a @ M

Values have modes, just as they have types. OxCaml tracks the mode of every variable and expression.

Functions

f : a @ M -> b @ N
f x : b @ N

Function signatures specify modes.

Modes are deep

type r =
  { field : a }

x : r @ M
r.field : a @ M

Projection uses the mode of the record value.

Function expressions

fun x -> expr

Function values also get modes based on what they capture.

Most mode propagation is simple, but functions is where something more complex happens.

The contention function boundary

fork/join body sees captured x @ shared

type t = { id : int; mutable hits : int }
let x = { id = 1; hits = 0 } x @ uncontended
let _result =
Toy.fork_join2
(
fun () ->x @ shared
let _id = x.id in (* ok *)
let n = x.hits in (* ok *)
x.hits <- n + 1 (* no *)
)
(fun () -> right_work ())
x.hits <- x.hits + 1 x @ uncontended (* ok after join *)

spawn body sees captured x @ contended

type t = { id : int; mutable hits : int }
let x = { id = 1; hits = 0 } x @ uncontended
let _ =
Toy.spawn
(
fun () ->x @ contended
let _id = x.id in (* ok *)
let n = x.hits in (* no *)
x.hits <- n + 1 (* no *)
)
x.hits <- x.hits + 1 x @ uncontended (* ok in parent *)

The boundary weakens captured values inside the function; the original variable keeps its mode outside the function.

Ordinary functions keep ordinary access

List.iter body sees captured x @ uncontended

type t = { id : int; mutable hits : int }
let x = { id = 1; hits = 0 } x @ uncontended
let _ =
List.iter
(
fun _ ->x @ uncontended
let _id = x.id in (* ok *)
let n = x.hits in (* ok *)
x.hits <- n + 1 (* ok *)
)
[1; 2; 3]
x.hits <- x.hits + 1 x @ uncontended (* ok *)

An ordinary function does not need a parallel-safety promise, so the captured variable keeps ordinary write access.

Key point: a variable's type never changes, but a variable's mode can change when it is captured by a function.

Function arguments have modes

Function argument modes record what level of access the function needs.

function_argument_modes.ml
type t = { id : int; mutable hits : int } let get_hits (x @ shared) = x.hits let bump_hits (x @ uncontended) = x.hits <- x.hits + 1 let demo x = Toy.fork_join2 (fun () -> get_hits x) (fun () -> bump_hits x)

Exercise: function calls on parent variable x

Suppose x is defined outside the List.iter/fork_join2/spawn. Which function calls are allowed?

Helpers

type t = { id : int; mutable hits : int }

let get_id (x @ contended) = x.id
let get_hits (x @ shared) = x.hits
let bump_hits (x @ uncontended) =
  x.hits <- x.hits + 1
List.iter (fun _ ->
  ignore (get_id x);
  ignore (get_hits x);
  bump_hits x) [()]

Toy.fork_join2 (fun () ->
  ignore (get_id x);
  ignore (get_hits x);
  bump_hits x) (fun () -> ())

Toy.spawn (fun () ->
  ignore (get_id x);
  ignore (get_hits x);
  bump_hits x)
CallList.iterfork_join2spawn
get_id x
get_hits x
bump_hits x

What about function captures?

function_captures.ml
type t = { id : int; mutable hits : int } let x = { id = 1; hits = 0 } let write_x () = x.hits <- x.hits + 1 let demo () = Toy.fork_join2 (fun () -> write_x ()) (fun () -> write_x ())

OxCaml must track portability of functions.

Schematic types of fork_join2 and spawn

val Toy.fork_join2 :
  (unit -> 'a) @ shareable ->
  (unit -> 'b) @ shareable ->
  'a * 'b

val Toy.spawn :
  (unit -> unit) @ portable ->
  unit

Portability axis

callable in spawn context
portable
  • detached parallel work
  • functions keep no mutable access
→
callable in fork/join context
shareable
  • structured fork/join work
  • functions keep read-only access
→
callable in sequential context
nonportable
  • ordinary use only
  • functions may keep read/write access

Portability answers: can this value be used in this parallel context?

How the compiler knows which function boundary to apply

type t = { id : int; mutable hits : int }
let x = { id = 1; hits = 0 } x @ uncontended
let _result =
Toy.fork_join2
(
fun () ->x @ shared
let _id = x.id in (* ok *)
let n = x.hits in (* ok *)
x.hits <- n + 1 (* no *)
)
(fun () -> right_work ())
x.hits <- x.hits + 1 x @ uncontended (* ok after join *)

x becomes @ shared because fork_join2 takes the worker at @ shareable.

val Toy.fork_join2 :
  (unit -> 'a) @ shareable ->
  (unit -> 'b) @ shareable ->
  'a * 'b
type t = { id : int; mutable hits : int }
let x = { id = 1; hits = 0 } x @ uncontended
let _ =
Toy.spawn
(
fun () ->x @ contended
let _id = x.id in (* ok *)
let n = x.hits in (* no *)
x.hits <- n + 1 (* no *)
)
 
x.hits <- x.hits + 1 x @ uncontended (* ok in parent *)

x becomes @ contended because spawn takes the worker at @ portable.

val Toy.spawn :
  (unit -> unit) @ portable ->
  unit

Exercise: functions that capture a parent variable

Where can each function be used?

Helpers

type t = { id : int; mutable hits : int }
let x = { id = 1; hits = 0 }

let id_x () = x.id
let read_x () = x.hits
let write_x v = x.hits <- v
List.iter (fun _ ->
  ignore (id_x ());
  ignore (read_x ());
  write_x 1) [()]

Toy.fork_join2 (fun () ->
  ignore (id_x ());
  ignore (read_x ());
  write_x 1) (fun () -> ())

Toy.spawn (fun () ->
  ignore (id_x ());
  ignore (read_x ());
  write_x 1)
FunctionList.iterfork_join2spawn
id_x
read_x
write_x

Shared Buffer revisited

bits_to_string now closes over the top-level buf.

Passing that function to fork/join asks whether the function value is @ shareable. It is not, because its hidden capture needs write access.

fork_join_shared_buffer.ml
let buf = Buffer.create 0 let bits_to_string bits = Buffer.clear buf; List.iter (fun bit -> Buffer.add_char buf (if bit then '1' else '0')) bits; Buffer.contents buf let strings_in_parallel () = let (left, right) = Toy.fork_join2 (fun () -> bits_to_string [true; false; true]) (fun () -> bits_to_string [false; true; false]) in left ^ "\n" ^ right

Function Boundaries: Shareable

shareable function

A structured fork/join function may still use captures in shared/read-only mode, but not in uncontended/write-capable mode.

let n = 10 immutable data
let b @ uncontended = (...) uncontended
let a @ shared = (...) shared
let c @ contended = (...) contended
let f : (int -> int) @ portable = (...) portable
let g : (int -> int) @ shareable = (...) shareable
let h : (int -> int) @ nonportable = (...) nonportable
let worker : (unit -> unit) @ shareable =
shareable Function Boundary
fun () ->
let n' = n in stays unchanged
let b' @ shared = b in uncontended becomes shared
let a' @ shared = a in shared stays shared
let c' @ contended = c in contended stays contended
let _ = f 0 in can use portable
let _ = g 0 in can use shareable
let _ = h 0 in cannot use nonportable
...
let (_left, _right) = fork/join
Toy.fork_join2 worker worker
in
let b'' @ uncontended = b outside: still uncontended

Function Boundaries: Portable

portable function

A spawned function is checked more conservatively: shared/read-only mutable access no longer survives the boundary.

let n = 10 immutable data
let b @ uncontended = (...) uncontended
let a @ shared = (...) shared
let c @ contended = (...) contended
let f : (int -> int) @ portable = (...) portable
let g : (int -> int) @ shareable = (...) shareable
let h : (int -> int) @ nonportable = (...) nonportable
let worker : (... -> unit) @ portable =
portable Function Boundary
fun () ->
let n' = n in stays unchanged
let b' @ contended = b in uncontended becomes contended
let a' @ contended = a in shared becomes contended
let c' @ contended = c in contended stays contended
let _ = f 0 in can use portable
let _ = g 0 in cannot use shareable
let _ = h 0 in cannot use nonportable
...
ignore (Toy.spawn worker) spawn
let a'' @ shared = a outside: still shared
let b'' @ uncontended = b outside: still uncontended

Function boundaries summary

@ uncontended
@ shared
@ contended
@ portable
@ shareable
@ nonportable
in portable function
contended
contended
contended
portable
error
error
in shareable function
shared
shared
contended
portable
shareable
error
in nonportable function
uncontended
shared
contended
portable
shareable
nonportable

Parallelism recap

0. Parallel mutation can race.

1. Simple model: functions passed to parallel work are checked.

  • Fork/join can read but not write captured mutable fields.
  • Spawn can neither read nor write captured mutable fields.

2. Reads and writes are checked using the contention axis.

3. Functions are checked using the portability axis.

What makes OxCaml great

  • Ordinary sequential code does not change.
  • Purely functional code can be parallelized without restrictions.
  • Code that uses mutation internally can still be parallelized.
  • Only code that uses shared mutation is restricted.

OxCaml

Safe high-performance programming.

Stack allocation

Avoid heap allocation without creating dangling stack pointers.

Unboxed representation

Remove boxes and pointer hops without representation mismatches.

Parallel work

Use more cores without introducing data races.

OxCaml Basics mark

Presenter controls

  • Press S for speaker view with timer, current slide, and next slide preview.
  • Use arrow keys for slides and fragments.
  • When focus is inside an editor or widget, keyboard events stay with the interactive element.