A memory efficient string type that can store up to 24* bytes on the stack.
* 12 bytes for 32-bit architectures
A CompactString
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).
It 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 CompactString
specifically has the following properties:
size_of::<CompactString>() == 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)
-
From<String>
orFrom<Box<str>>
re-uses underlying buffer- Eagerly inlines small strings
-
O(1)
creation from&'static str
withCompactString::const_new
- Heap based string grows at a rate of 1.5x
- The std library
String
grows at a rate of 2x
- The std library
- Space optimized for
Option<_>
size_of::<CompactString>() == size_of::<Option<CompactString>>()
- Uses branchless instructions for string accesses
- Supports
no_std
environments
This crate exposes two traits, ToCompactString
and CompactStringExt
.
Provides the to_compact_string(&self)
method for converting types into a CompactString
. This trait is automatically implemented for all types that are std::fmt::Display
, with specialized higher performance impls for:
-
u8
,u16
,u32
,u64
,usize
,u128
-
i8
,i16
,i32
,i64
,isize
,i128
-
f32
,f64
-
bool
,char
-
NonZeroU*
,NonZeroI*
-
String
,CompactString
Provides two methods join_compact(seperator: impl AsRef<str>)
and concat_compact()
. This trait is automatically implemented for all types that can be converted into an iterator and yield types that impl AsRef<str>
. This allows you to join Vec's, slices, and any other collection to form CompactString
s.
This crate exposes one macro format_compact!
that can be used to create CompactString
s from arguments, like you can String
s with the std::format!
macro.
compact_str
has the following optional features:
-
serde
, which implementsDeserialize
andSerialize
from the popularserde
crate, forCompactString
-
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 aCompactString
from abytes::Buf
-
markup
, which implementsRender
trait, soCompactString
s can be used in templates as HTML escaped strings -
diesel
, which allows using CompactStrings indiesel
text columns -
sqlx-mysql
/sqlx-postgres
/sqlx-sqlite
, which allows using CompactStrings insqlx
text columns -
arbitrary
, which implements thearbitrary::Arbitrary
trait for fuzzing -
proptest
, which implements theproptest::arbitrary::Arbitrary
trait for fuzzing -
quickcheck
, which implements thequickcheck::Arbitrary
trait for fuzzing -
rkyv
, which implementsrkyv::Archive
,rkyv::Serialize
andrkyv::Deserialize
for fast zero-copy serialization, interchangable with serialized Strings -
smallvec
, provides theinto_bytes()
method which enables you to convert aCompactString
into a byte vector, usingsmallvec::SmallVec
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 string -
len
is the length of the string -
cap
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 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> ]
Internally a CompactString
has two variants:
- Inline, a string <= 24 bytes long
- Heap allocated, a string > 24 bytes long
We define a discriminant (aka track which variant we are) within the last byte, specifically:
-
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
and the overall memory layout of a CompactString
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 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>
inO(1)
time, by taking the parts of aString
(e.g.ptr
,len
, andcap
) and using those to create aCompactString
, without having to do any heap allocations. This is important when usingCompactString
in large codebases where you might haveCompactString
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 CompactString
has the following uses:
-
[0, 191]
- Is the last byte of a UTF-8 char, theCompactString
is stored on the stack and implicitly has a length of24
-
[192, 215]
- Denotes a length in the range of[0, 23]
, thisCompactString
is stored on the stack. -
216
- Denotes thisCompactString
is stored on the heap -
217
- Denotes thisCompactString
stores a&'static str
. -
[218, 255]
- Unused, denotes e.g. theNone
variant forOption<CompactString>
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
, AFL
, and honggfuzz
, 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.60
to ensure support for our minimum supported Rust version (MSRV).
CompactString
uses a bit of unsafe code because we manually define what variant we are, so unlike an enum, the compiler can't guarantee what value is actually stored.
We also have some manually implemented heap data structures, i.e. HeapBuffer
, and mess with bytes at a bit level, to make the most out of our resources.
That being said, uses of unsafe code in this library are 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 archs -
smartstring
- Can inline 23 bytes,Clone
isO(n)
, is mutable -
kstring
- Can inline 15 or 22 bytes dependent on crate features,Clone
isO(1)
, can also store&'static str
s -
flexstr
- Can inline 22 bytes,Clone
isO(1)
, can also store&'static str
s
Thanks for readingme!