Chapter 23: Memory Representation of Values

There’s a need to know the underlying OCaml memory model to be able to use other features like FFIs properly — because of the ways values are exchanged across C libs and the OCaml runtime. Also useful for interfacing with external system tools that operate on OCaml binaries (e.g. profiling tools, debuggers [who don’t have any knowledge of the static OCaml types]). So the learning of memory representation is done with translation between C world and OCaml world in mind.

The OCaml compiler toolchain makes things predictable — we will be able to know precisely where a block of critical OCaml code spends it time in memory.

Ocaml Blocks and Values #

Uniform memory representation: every OCaml variable stored as a value.

• it’s a single memory word that is a) an immediate integer OR b) a pointer to some other memory

  that’s why it need to be able to differentiate between integer and pointer values — pointers need to be followed for scanning since they indirect

• runtime tracks all values to free them when unneeded.

A running program will use blocks of memory (contiguous words in RAM) to represent tuples, records, closures, arrays — allocation implicitly happens at creation of the value

1
2
3
4

(*--- type declarations don't take up any memory*)
type t = { foo: int; bar: int };;
(*--- let binding -- variable init -- 2 words of space: 1 for foo, 1 for bar*)
let x = { foo = 13; bar = 14 };;

Distinguishing Integers and Pointers at Runtime #

Boxing is when we wrap primitives in structs that hold metadata about it. In this case, boxing is helpful to give information to the GC, so the layer of indirection is tolerable.

Not all of the values need to be boxed @ runtime — there’s a tag bit per word to distinguish integers and pointers at runtime.

• integer \(\Leftarrow\) if lowest bit of the block word is non-zero
  • used to represent: bool, int, empty list, unit, sometimes variants may use this also (for constant constructors [i.e. no args like None ])
  • so, integers are unboxed runtime values in OCaml \(\implies\) no need wrappers, can be directly stored \(\implies\) can be loaded to registers easily that’s why they’re the cheapest and fastest values to use in OCaml
• pointer \(\Leftarrow\) if the lowest bit of the block word (i.e. lowest bit) is Zero
  • pointers are always word-aligned

Pointers are seen from the lens of something that does indirection, but not all pointers should be followed.

• A: Pointers to OCaml values \(\implies\) should be followed If pointer is within a heap-chunk that is marked as managed by OCaml runtime \(\implies\) it’s a OCaml value
• B: Pointers to C values \(\implies\) shouldn’t be followed If pointer points to outside the OCaml runtime \(\implies\) it’s an opaque C pointer to some other system resource.

Blocks and Values #

Recall that values can be categorised as: boxed values or immediate values.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

(* ------ [1] Determining whether it's a block or immediate value  *)
(* repr function retrieves the runtime representation:*)
(*  is_block does a bit-check for the bottom bit *)
Obj.is_block (Obj.repr (1,2,3));;
(* - : bool = true *)
Obj.is_block (Obj.repr 1);;
(* - : bool = false *)



(* ------ [2] Finding out tag value  *)
Obj.tag (Obj.repr 1.0);;
(* note: for floating points, the =Double_tag= is set, so the collector knows that the fp value is not to be scanned *)
Obj.tag (Obj.repr 1.0) = Obj.double_tag;;

• Immediate values: have no block at all.

  The value is the word, with the tag-bit set. So there’s no header, no data-segment and nothing on the heap — e.g. (int, char, unit, bool, constant variants)

• Boxed values: block structure has meta fields and a data-segment

  A block is structured like so:

•                                              •                          •
•••••••••••••••• one word header •••••••••••••••• variable data-segment •••
•                                              •                          •

███████████████████████████████████████████████████████████████████████████
█               █                 █            █                          █
█   size field  █  colour (by GC) █  tag byte  █  variable data-segment   █
█               █                 █            █                          █
███████████████████████████████████████████████████████████████████████████

Integers, Characters, Other Basic Types (Atomic Types) #

These atomic types are just stored as unboxed integers at runtime.

• OCaml ints are effectively 63-bit immediates – loss of 1 bit of precision because of the block tag

  for int s, there’s a single bit lost to the tag bit and there’s a loss of a single bit of precision there. So the int representable range is \([ - 2^{62}, 2^{62} - 1 ]\)

Tuples, Records and Arrays #

• all of these are boxed with the tag 0
• tuples and records are fixed sized, arrays are variable - length-ed and homogeneous in their type from OCaml compiler’s POV but the interesting thing is that this homogeneity is not required by the memory representation though.

Floating-Point Numbers and Arrays #

Floats are just doubles – their tag is = Obj.double_tag

Each floating-point value is boxed in a separate memory-block — it’s inefficient to handle large arrays of floats compared to unboxed integers \(\implies\) that’s why OCaml special-cases records / arrays that contain ONLY float types \(\implies\) they’re tagged as Double_array_tag and are stored in a block that contains the floats packed directly in the data-section.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

(* [1]--- tag for float arrays differs from float and differs from float *)
Obj.tag (Obj.repr [| 1.0; 2.0; 3.0 |]);;
(* - : int = 254 *)
Obj.tag (Obj.repr 1.2);;
(* - : int = 253 *)

(* [2]--- tuple of floats are NOT optimised in the same way -- we end up having tuple tags: *)
Obj.tag (Obj.repr (1.0, 2.0, 3.0) );;
(* - : int = 0 *)


(* [3]--- possible to access the array using double_field *)
Obj.double_field (Obj.repr [| 1.1; 2.2; 3.3 |]) 1;;
(* - : float = 2.2 *)
Obj.double_field (Obj.repr 1.234) 0;;
(* - : float = 1.234 *)

Variants and Lists #

Variants:

• Basic variants just stored as 0-indexed numbers.

• Variants with params are complex — they’re stored as blocks, the value tags ascend from 0 (from the leftmost variants with params) and params are stored as words in the block.

• interesting gotcha on variant limits: because of the tagged encoding, there is a limit around 240 variants with parameters that applies to each type definition, but the only limit on the number of variants without parameters is the size of the native integer (either 31 or 63 bits). This limit arises because of the size of the tag byte, and that some of the high-numbered tags are reserved.

Lists:

• representation is exactly same as if the list was written as a variant type with Nil and Cons
• [] is an integer 0
• subsequent blocks have tag 0 and 2 params: block with the current value, pointer to the rest of the list

We can force a type case between any two OCaml types using Obj.magic and we just need to provide a type hint:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

(* ====== [1] basic variant *)
type t = Apple | Orange | Pear;;
(* type t = Apple | Orange | Pear *)
((Obj.magic (Obj.repr Apple)) : int);;
(* - : int = 0 *)
((Obj.magic (Obj.repr Pear)) : int);;
(* - : int = 2 *)

(* --- confirms that the value is not a complex, boxed value*)
Obj.is_block (Obj.repr Apple);;
(* - : bool = false *)

(* ====== [2] parametric variant *)
type t = Apple | Orange of int | Pear of string | Kiwi;;
(* - : type t = Apple | Orange of Base.int | Pear of Base.string | Kiwi *)
Obj.is_block (Obj. repr (Orange 1234));;
(* - : bool = true *)
Obj.tag (Obj. repr (Orange 1234));;
(* - : int = 0 *)
Obj.tag (Obj. repr (Pear "xyz"));;
(* - : int = 1 *)
(Obj.magic (Obj.field (Obj.repr (Orange 1234)) 0) : int);;
(* - : int = 1234 *)
(Obj.magic (Obj.field (Obj.repr (Pear "xyz")) 0) : string);;
(* - : string = "xyz" *)

Obj Module Considered Harmful #

Polymorphic Variants #

Not much compile-time info available to optimise memory layout — so the flexibility of polymorphic variants is at the expense of a slight runtime inefficiency.

• Plain polymorphic variant (no parameters) — unboxed integer so 1 word wide, like a normal variant. Integer value = hash (name of variant). hash function would be the same for both 32 vs 64 bit architectures – so stable memory representation across CPU and host types

  this is how one might inspect the hash:

    #require "ocaml-compiler-libs.common";;
    Btype.hash_variant "Foo";;
  ​  - : int = 3505894
    (Obj.magic (Obj.repr `Foo) : int);;
  ​  - : int = 3505894

  Code Snippet 5: Using ocaml-compiler-libs to calculate hashes

• Inefficiencies:

  1. more mem space than normal variants IF they have params included

     • the normal variants just use the tag byte for encoding the variant value and save the fields for the contents

     • the polymorphic variant needs to allocate a new block (with tag 0) to store the hashed value for the polymorphic variant. So, polymorphic variants with constructors use one word of memory MORE than the normal variant constructors.

  2. when polymorphic variant constructor has more than one param

     • normal variant holds params as a single flat block with multiple fields for each entry

     • polymorphic variants need flexible uniform memory representation because they may be used in different context across compilation units (that’s why theyr’e polymorphic) \(\implies\) allocate a tuple block for params which the argument field of the variant points to

       so for the polymorphic variant, there are 3 additional words: along with an extra memory indirection due to the tuple.

• the CON of the inefficiencies not as bad as the PRO of the flexibility of using polymorphic variants.

  if we’re writing code that demands high performance or must run within tight memory bounds, the runtime layout is at least very predictable.

String (and Byte) Values #

Basically just header then contents then padding. Padding is dynamically determined to make things word-aligned.

Header contains the size of string, defined in number of machine words; String_tag (252) is higher than No_scan_tag which helps indicate that the contents of the block are opaque to the collector.

The string representation is a clever way to ensure that the contents are always zero-terminated by the padding word and to still compute its length efficiently without scanning the whole string.

length_of_string = num_of_words_in_block * sizeof(word) - last_byte_of_block - 1

NULL termination comes in handy when passing a string to C, but is not relied upon to compute the length from OCaml code.

Careful when interoperating with C libs:

• Take care that any C library functions that receive these buffers can also cope with arbitrary bytes within the buffer contents and are not expecting C strings

  e.g. C memcopy or memmove standard library functions can operate on arbitrary data, but strlen or strcpy both require a NULL-terminated buffer, and neither has a mechanism for encoding a NULL value within its contents.

Custom Heap Blocks #

We can define our own operations over OCaml values using Custom_tag – custom blcok lives in the OCaml heap like an ordinary block and can be of user-defined size.

Custom_tag is higher than No_scan_tag so it doesn’t get scanned by the GC.

first word of the data within the custom block points out to C struct of custom operations. Very important point that this is one-way – so the custom block can’t have pointers to OCaml blocks and is always going to be opaque to the GC.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

struct custom_operations {
  char *identifier;
  /* This is a fini routine typically used to invoke C cleanup functions like free, different from ordinary OCaml finalizers: */
  void (*finalize)(value v);
  int (*compare)(value v1, value v2); /*<-- shows how to do polymorphic comparison */
  intnat (*hash)(value v);

  /*---- Marshalling logic: ----*/
  void (*serialize)(value v,
                    /*out*/ uintnat * wsize_32 /*size in bytes*/,
                    /*out*/ uintnat * wsize_64 /*size in bytes*/);
  uintnat (*deserialize)(void * dst);
  int (*compare_ext)(value v1, value v2);
};

Managing external memory with Bigarray #

Custom blocks are useful for interfacing with external system memory directly from within OCaml — for FFI interoperability.

E.g. BigArray interface created for data-exchange with Fortran code — mapped a block of system memory as a multi-dimensional array that can be accessed from OCaml

Bigarray operations work directly on the external memory without requiring it to be copied into the OCaml heap (which is a potentially expensive operation for large arrays). Can avoid copying it over to OCaml heap.