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.
- the data should be be 8-byte aligned,
- finding the length should be possible in constant time, and
- 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 │ └──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘