Avoiding redundant allocations in OCaml

It's easy to make redudant memory allocations in OCaml. It's common to prioritize correctness over performance and just create a bajillion immutable variables that are equal to each other.

We can't always overlook performance.

Observe this pattern:

match x with
  | None -> Some 0
  | Some n -> Some n  (* <--- CAN BE PROBLEM *)

The last line can be a problem. That branch allocates a new object Some n in memory that is structurally the same as x.

A more-performant, but structurally equal implementation is the following alternative:

match x with
  | None -> Some 0
  | Some n -> x

In this implementation, we reuse the memory allocation of the original Some n, saving one redundant allocation. At scale, making this optimizaiton can reduce overall memory pressure.

Video demo

Hash-consing

Sometimes it's hard to avoid reallocating objects with the same structure.

For example, you might have a pure function f : 'a -> 'b, which will always produce a new allocation.

Instead of avoiding the redundant allocation from happening, you can instead avoid keeping redundant allocations around.

Hash-consing is one technique to do this. Essentially, you keep a hash table that maps each element to itself. When you allocate a new object, you can check if one that is structurally the same already exists, by checking the hash table. If you find one, you use the original allocation instead, allowing the new allocation to be thrown away by the garbage collector.

Below is some code that could be used to implement this.

let table = Hashtbl.create 10 in

let remove_extra_alloc maybe_repeat =
  match Hashtbl.find_opt table maybe_repeat with
    (* was a repeat, use original in the table *)
    | Some original -> original
    (* was not a repeat, add itself to the table *)
    | None -> Hashtbl.add table maybe_repeat 

This does introduce overhead due to hash table checking, but in some programs, it can dramatically reduce memory pressure, leading to improved performance.

If interested, here is a link to the Wikipedia page on hash-consing.