cold-string

A 1-word (8-byte) sized representation of immutable UTF-8 strings that in-lines up to 8 bytes.

Overview

ColdString minimizes per-string overhead for both short and large strings.

• Strings ≤ 8 bytes: 8 bytes total
• Larger strings: ~9–10 bytes overhead (other string libraries have 24 bytes per value)

This leads to substantial memory savings over both String and other short-string crates (see Memory Comparison (System RSS)):

• 35% – 67% smaller than String in HashSet
• 35% – 64% smaller than other short-string crates in HashSet
• 30% – 75% smaller than String in BTreeSet
• 13% – 63% smaller than other short-string crates in BTreeSet

---

Portability

ColdString's MSRV is 1.60, is no_std compatible, and is a drop in replacement for immutable Strings.

Usage

Use it like a String:

use cold_string::ColdString;

let s = ColdString::new("qwerty");
assert_eq!(s.as_str(), "qwerty");

Use ArcColdString when clones should share long-string storage:

use cold_string::ArcColdString;

let first = ArcColdString::new("a string longer than one machine word");
let second = first.clone();
assert_eq!(first, second);

ArcColdString uses a native-width reference count. ArcColdString8, ArcColdString16, and ArcColdString32 use 1-, 2-, and 4-byte counts when a smaller heap header is preferable. All variants remain one word in size.

Both types keep strings up to one machine word inline. For longer strings, ArcColdString stores [atomic reference count][variable-length length][UTF-8 bytes] in one allocation and does not support weak references.

Packs well with other types:

use cold_string::ColdString;
use std::mem::size_of;

assert_eq!(size_of::<ColdString>(), size_of::<usize>());
// ColdString has a null-niche:
assert_eq!(size_of::<Option<ColdString>>(), size_of::<ColdString>());

How It Works

ColdString is an 8-byte tagged pointer (4 bytes on 32-bit machines):

Internally, both string types use a one-word tagged pointer representation. ColdString points to a [variable-length (length - inline capacity)][UTF-8 bytes] allocation, while ArcColdString adds an atomic reference count before the same payload. The 8 bytes encode one of three representations indicated by the 1st byte:

• 10xxxxxx: encoded contains a tagged heap pointer. To decode the address, clear the tag bits (10 → 00) and rotate so the 00 bits become the least-significant bits. The heap allocation uses 4-byte alignment, guaranteeing the least-significant 2 bits of the address are 00. On the heap, the UTF-8 characters are preceded by a variable-length encoding of length - size_of::<usize>(), since strings up to one word are stored inline. Encoded values 1–127 use one byte, 128–16,383 use two bytes, and so on. On a 64-bit target, those ranges correspond to actual string lengths 9–135 and 136–16,391.
• 11111xxx: xxx is the length and the remaining 0-7 bytes are UTF-8 characters.
• xxxxxxxx: All 8 bytes are UTF-8.

The exception is if encoded is usize::MAX, which represents one word of NUL bytes.

10xxxxxx and 11111xxx are chosen because they cannot be valid first bytes of UTF-8.

Why "Cold"?

The heap representation stores the length on the heap, not inline in the struct. This saves memory in the struct itself but slightly increases the cost of len() since it requires a heap read. In practice, the len() cost is only marginally slower than inline storage and is typically negligible compared to memory savings, cache density improvements, and 3x faster operations on inlined strings.

Safety

ColdString uses unsafe to implement its packed representation and pointer tagging. Usage of unsafe is narrowly scoped to where layout control is required, and each instance is documented with // SAFETY: <invariant>. To further ensure soundness, ColdString is written using Rust's strict provenance API, handles unaligned access internally, maintains explicit heap alignment guarantees, and is validated with property testing and MIRI.

Benchmarks

Memory Comparisons (Allocator)

Memory usage per string, measured by tracking the memory requested by the allocator:

Memory Comparison (System RSS)

Resident set size in bytes per insertion of various collections. Insertions are strings with random length 0..=N:

Speed

Construction: Variable Length (0..=N) [ns/op]

Construction: Fixed Length (N..=N) [ns/op]

Reference Counting Memory Comparison

Theoretical overhead on a 64-bit target, excluding one pointer and the UTF-8 payload. Inline values have no pointer or heap allocation, so their overhead is shown relative to the string bytes alone. Allocator rounding is not included.

RSS bytes per unique string in a pre-sized Vec, measured on 64-bit Windows with 1,000,000 strings per subprocess. Each cell is the median of three isolated release-mode runs and includes the Vec element, heap allocation, and allocator rounding. RSS results will vary by operating system and allocator.

Reference Counting Speed Comparison

Criterion point estimates in nanoseconds per operation on 64-bit Windows (release mode, 100 samples). Lower is better. Allocation and clone outputs are dropped outside the timed region; drop measures a non-final reference-count decrement.

Fresh allocation and string copy:

Clone/reference-count increment:

String access:

Non-final drop/reference-count decrement:

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.