compact_str

How it works

Normally strings are stored on the heap since they're dynamically sized. In Rust a String consists of three fields, each of which are the size of a usize. e.g. its layout is something like the following:

String: [ ptr<8> | len<8> | cap<8> ]

• ptr is a pointer to a location on the heap that stores the string
• len is the length of the string
• cap is the total capacity of the buffer being pointed to

The idea of CompactString is instead of storing metadata on the stack, just store the string itself. This way for smaller strings we save a bit of memory, and we don't have to heap allocate so it's more performant. A CompactString is limited to 24 bytes (aka size_of::<String>()) so it won't ever use more memory than a String would.

The memory layout of a CompactString looks something like:

CompactString: [ buffer<23> | len<1> ]

Memory Layout

• Inline, a string <= 24 bytes long
• Heap allocated, a string > 24 bytes long

• 0b11111110 - All 1s with a trailing 0, indicates heap allocated
• 0b11XXXXXX - Two leading 1s, indicates inline, with the trailing 6 bits used to store the length

• heap: { ptr: NonNull<u8>, len: usize, cap: Capacity }
• inline: { buffer: [u8; 24] }

For heap allocated strings we use a custom HeapBuffer which normally stores the capacity of the string on the stack, but also optionally allows us to store it on the heap. Since we use the last byte to track our discriminant, we only have 7 bytes to store the capacity, or 3 bytes on a 32-bit architecture. 7 bytes allows us to store a value up to 2^56, aka 64 petabytes, while 3 bytes only allows us to store a value up to 2^24, aka 16 megabytes.

For 64-bit architectures we always inline the capacity, because we can safely assume our strings will never be larger than 64 petabytes, but on 32-bit architectures, when creating or growing a CompactString, if the text is larger than 16MB then we move the capacity onto the heap.

We handle the capacity in this way for two reasons:

• Users shouldn't have to pay for what they don't use. Meaning, in the majority of cases the capacity of the buffer could easily fit into 7 or 3 bytes, so the user shouldn't have to pay the memory cost of storing the capacity on the heap, if they don't need to.
• Allows us to convert From<String> in O(1) time, by taking the parts of a String (e.g. ptr, len, and cap) and using those to create a CompactString, without having to do any heap allocations. This is important when using CompactString in large codebases where you might have CompactString working alongside of String.

To do this, we utilize the fact that the last byte of our string could only ever have a value in the range 0, 192). We know this because all strings in Rust are valid [UTF-8, and the only valid byte pattern for the last byte of a UTF-8 character (and thus the possible last byte of a string) is 0b0XXXXXXX aka [0, 128) or 0b10XXXXXX aka [128, 192). This leaves all values in [192, 255] as unused in our last byte. Therefore, we can use values in the range of [192, 215] to represent a length in the range of [0, 23], and if our last byte has a value < 192, we know that's a UTF-8 character, and can interpret the length of our string as 24.

Specifically, the last byte on the stack for a CompactString has the following uses:

• [0, 191] - Is the last byte of a UTF-8 char, the CompactString is stored on the stack and implicitly has a length of 24
• [192, 215] - Denotes a length in the range of [0, 23], this CompactString is stored on the stack.
• 216 - Denotes this CompactString is stored on the heap
• 217 - Denotes this CompactString stores a &'static str.
• [218, 255] - Unused, denotes e.g. the None variant for Option<CompactString>

Testing

Fuzz testing is run with libFuzzer, AFL++, and honggfuzz, with AFL++ running on both x8664 and ARMv7 architectures. We test with miri to catch cases of undefined behavior, and run all tests on every Rust compiler since v1.60 to ensure support for our minimum supported Rust version (MSRV).