A memory efficient string type that can store up to 24* bytes on the stack.
* 12 bytes for 32-bit architectures
A CompactStr
is a more memory efficient string type, that can store smaller strings on the stack, and transparently stores longer strings on the heap (aka a small string optimization).
They can mostly be used as a drop in replacement for String
and are particularly useful in parsing, deserializing, or any other application where you may
have smaller strings.
A CompactStr
specifically has the following properties:
size_of::<CompactStr>() == size_of::<String>()
- Stores up to 24 bytes on the stack
- 12 bytes if running on a 32 bit architecture
- Strings longer than 24 bytes are stored on the heap
Clone
isO(n)
- Conversion
From<String>
orFrom<Box<str>>
isO(1)
- Heap based string grows at a rate of 1.5x
- The std library
String
grows at a rate of 2x
- The std library
compact_str
has the following features:
serde
, which implementsDeserialize
andSerialize
from the popularserde
crate, forCompactStr
.bytes
, which provides two methodsfrom_utf8_buf<B: Buf>(buf: &mut B)
andfrom_utf8_buf_unchecked<B: Buf>(buf: &mut B)
, which allows for the creation of aCompactStr
from abytes::Buf
Note: this explanation assumes a 64-bit architecture, for 32-bit architectures generally divide any number by 2.
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 stringlen
is the length of the stringcap
is the total capacity of the buffer being pointed to
This results in 24 bytes being stored on the stack, 8 bytes for each field. Then the actual string is stored on the heap, usually with additional memory allocated to prevent re-allocating if the string is mutated.
The idea of CompactStr
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 CompactStr
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 CompactStr
looks something like:
CompactStr: [ buffer<23> | len<1> ]
Internally a CompactStr
has two variants:
- Inline, a string <= 24 bytes long
- Heap allocated, a string > 24 bytes long
To maximize memory usage, we use a union
instead of an enum
. In Rust an enum
requires at least 1 byte
for the discriminant (tracking what variant we are), instead we use a union
which allows us to manually define the discriminant. CompactStr
defines the
discriminant within the last byte, using any extra bits for metadata. Specifically the discriminant has two variants:
0b11111111
- All 1s, indicates heap allocated0b11XXXXXX
- Two leading 1s, indicates inline, with the trailing 6 bits used to store the length
and specifically the overall memory layout of a CompactStr
is:
heap: { ptr: NonNull<u8>, len: usize, cap: Capacity }
inline: { buffer: [u8; 24] }
Both variants are 24 bytes long
For heap allocated strings we use a custom BoxString
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 CompactStr
, if the text is larger than 16MB then we move the capacity onto the heap.
We handle the capacity in this way for two reaons:
- 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>
inO(1)
time, by taking the parts of aString
(e.g.ptr
,len
, andcap
) and using those to create aCompactStr
, without having to do any heap allocations. This is important when usingCompactStr
in large codebases where you might haveCompactStr
working alongside ofString
.
For inline strings we only have a 24 byte buffer on the stack. This might make you wonder how can we store a 24 byte long string, inline? Don't we also need to store the length somewhere?
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 CompactStr
has the following uses:
[0, 192)
- Is the last byte of a UTF-8 char, theCompactStr
is stored on the stack and implicitly has a length of24
[192, 215]
- Denotes a length in the range of[0, 23]
, thisCompactStr
is stored on the stack.[215, 255)
- Unused255
- Denotes thisCompactStr
is stored on the heap
Strings and unicode can be quite messy, even further, we're working with things at the bit level. compact_str
has an extensive test suite comprised of unit testing, property testing, and fuzz testing, to ensure our invariants are upheld. We test across all major OSes (Windows, macOS, and Linux), architectures (64-bit and 32-bit), and endian-ness (big endian and little endian).
Fuzz testing is run with libFuzzer
and AFL++
with AFL++
running on both x86_64
and ARMv7
architectures. We test with miri
to catch cases of undefined behavior, and run all tests on every rust compiler since v1.49
to ensure support for our minimum supported Rust version (MSRV).
CompactStr
uses a bit of unsafe code because accessing fields from a union
is inherently unsafe, the compiler can't guarantee what value is actually stored.
We also have some manually implemented heap data structures, i.e. BoxString
, and mess with bytes at a bit level.
That being said, uses of unsafe code in this library are quite limited and constrained to only where absolutely necessary, and always documented with
// SAFETY: <reason>
.
Storing strings on the stack is not a new idea, in fact there are a few other crates in the Rust ecosystem that do similar things, an incomplete list:
smol_str
- Can inline 22 bytes,Clone
isO(1)
, doesn't adjust for 32-bit archssmartstring
- Can inline 23 bytes,Clone
isO(n)
, is mutable
Thanks for readingme!