OCaml strings

November 2026

As part of my ZINC project and miniml language, I've been carefully reading The ZINC Experiment paper by Xavier Leroy.

In Section 4.3.1, he outlines a scheme for encoding strings developed by Damien Doligez, which is quite clever and solves several problems at once.

We would like our encoding to have the following 3 properties.

  1. the data should be be 8-byte aligned,
  2. finding the length should be possible in constant time, and
  3. the string to be a valid, null-terminated C string.

In OCaml, heap-allocated objects are all stored in words, and all have a 1-word header that records their size (in words). A 64-bit word can hold 8 bytes. Since we already store the number of words, the length in bytes is 8 * size - r where r is (- length) mod 8. So we could get property 2 if we could just store this difference r. But where?

What if we just store r in the very last byte?

Suppose we have a string of 47 bytes. Then 47 = 8 * 6 - 1, so we just store a 1 in the last byte. But that means our string nearly fits in exactly 6 words, with only 1 byte to spare, so we can't add a null byte, and we lose property 3.

               ! No room for null byte
               ▼
────┬──────────┬──────────┐
... │ -------- │ 00000001 │
────┴──────────┴──────────┘

What if we found r in the range 2 to 9 instead of 0 to 7? These are equivalent mod 8, so it should work. This always gives us room for at least 1 null byte, so now both properties 2 and 3 are satisfied. We just have to pad the end of the string. So we pad with r - 1 null bytes, and end with the number r itself. This satisfies all 3 properties and is the scheme outlined in the original paper.

I was surprised to find that OCaml uses basically this method to this day. But there's a small issue, or at least inefficiency, with this scheme.

For our string of 47 bytes, since 47 = 8 * 7 - 9, our size is 7 and the last two words of the string look like

                 1            2          3-7   8          9
────┬──────────┬──────────┐ ┌──────────┬─────┬──────────┬──────────┐
... │ -------- │ 00000000 │ │ 00000000 │ ... │ 00000000 │ 00001001 │
────┴──────────┴──────────┘ └──────────┴─────┴──────────┴──────────┘

We have an entire word of padding. That alone isn't too bad. But we get an entire word of padding whenever the length of the string is 0 or -1 mod 8, a full 1/4 of the time.

Instead, we could shrink everything by 1, and compensate when we need to compute the length of the string. That is, find r in the range 1 to 8, and store r - 1 in the last byte.

The last word of our string of 47 bytes would now just have a single null byte.

                 1
────┬──────────┬──────────┐
... │ -------- │ 00000000 │
────┴──────────┴──────────┘

Now we only have 1 case where a full word is for padding, and we can still easily compute the length as 8 * size - r where r = last byte + 1.

In summary, we can work out the padding needed directly from the length.

(-length) mod 8    length mod 8    old scheme                 new scheme
8                  0             | 00 00 00 00 00 00 00 08    00 00 00 00 00 00 00 07
7                  1             |    00 00 00 00 00 00 07       00 00 00 00 00 00 06
6                  2             |       00 00 00 00 00 06          00 00 00 00 00 05
5                  3             |          00 00 00 00 05             00 00 00 00 04
4                  4             |             00 00 00 04                00 00 00 03
3                  5             |                00 00 03                   00 00 02
2                  6             |                   00 02                      00 01
9 = 1              7          00 | 00 00 00 00 00 00 00 09                         00

Example

Let's see how this works with "hello world". The length is 11 = 8 * 2 - 5, so we have a size of 2, and we pad with four null bytes and a 4, for a total of 3 words, including the header.

header word
  size                                                     GC   tag
┌────────────────────────────────────────────────────────┬────┬──────────┐
│ 000000000000000000000000000000000000000000000000000010 │ 00 │ 11111100 │
└────────────────────────────────────────────────────────┴────┴──────────┘
  h          e          l          l          o          <space>    w          o
┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│ 01101000 │ 01100101 │ 01101100 │ 01101100 │ 01101111 │ 00100000 │ 01110111 │ 01101111 │
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
  r          l          d
┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│ 01110010 │ 01101100 │ 01100100 │ 00000000 │ 00000000 │ 00000000 │ 00000000 │ 00000100 │
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘