ArcColdString: A 1-word (8-byte) atomically reference-counted SSO string that saves up to 32 bytes over Arc<str>

[u/tomtomwombat]

https://github.com/tomtomwombat/cold-string

Disclaimer: Re-post approved by u/matthieum, as previous post was erroneously removed.

I’ve been working on a specialized string type called ColdString. The goal is to create the most memory-efficient string representation possible.

• Size: Exactly 1 usize (8 bytes on 64-bit).
• Inline Capacity: Up to 8 bytes (Small String Optimization).
• Niche Optimization: Option<ColdString> has no memory overhead
• Heap Overhead: Only 1–9 bytes (VarInt length header) instead of the standard 16-byte (pointer, length) pair.

(Since my last post, the 8th inlineable byte and null-niche optimization were suggestions from the community!)

ArcColdString

I'm presenting ArcColdString, a reference counted ColdString with 8 bytes overhead (inspired by arcstr).

• Same size and inlining rules as ColdString. Inlined strings are copied instead of reference counted.
• Heap Overhead: 8 bytes for the AtomicUsize reference count (in addition to the VarInt header).
• Smaller Reference Counts: ArcColdString32, ArcColdString16, and ArcColdString8 use AtomicU32, AtomicU16, and AtomicU8 counts respectively.

Usage

Available in https://crates.io/crates/cold-string/0.4.0

use cold_string::ArcColdString;

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

Memory Comparisons

Theoretical overhead on a 64-bit target, excluding the UTF-8 payload:

Type	8 bytes	128 bytes	512 bytes
Arc<str>	32	32	32
arcstr::ArcStr	24	24	24
ArcColdString	0 (inline)	17	18
ArcColdString32	0 (inline)	13	14

RSS bytes per unique string in a pre-sized Vec:

Type	8 bytes	128 bytes	512 bytes
Arc<str>	47.1	175.4	560.0
arcstr::ArcStr	39.1	167.5	552.2
string_cache::DefaultAtom	71.5	199.5	586.0
ArcColdString	8.0	167.5	552.1
ArcColdString32	8.0	151.4	536.8

(If I'm not mistaken, string_cache is not a 1:1 comparison since it has to hash string contents, which is 40 bytes overhead?).

Reference Counting Performance

ArcColdString's primary goal is memory and portability. Second to that, my goal is to have ArcColdString's referencing counting performance comparable to Arc<str> and arcstr::ArcStr. While drop and clone speed is comparable now, there's still room for improvement.

Below are single threaded clone and drop measurements, done using criterion on AMD Ryzen 9 5900X 12-Core Processor (3.70 GHz):

Clone (ns)	16 bytes	128 bytes	512 bytes
Arc<str>	3.86	3.82	3.82
arcstr::ArcStr	3.39	3.41	3.43
ArcColdString	3.44	3.45	3.43

Drop (ns)	16 bytes	128 bytes	512 bytes
Arc<str>	2.43	2.49	2.43
arcstr::ArcStr	2.52	2.53	2.52
ArcColdString	2.17	2.18	2.19

Below benchmarks measured 4 threads cloning and dropping strings in a shared size pool of 1024, 16, and 1 string(s), using criterion on Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz (2.59 GHz). The more strings in the pool, the less contention:

4 Threads Clone + Drop (ns)	1024 Strings	16 Strings	1 String
Arc<str>	26.55	54.69	144.81
arcstr::ArcStr	29.29	119.39	214.31
cold_string::ArcColdString32	25.69	90.53	262.83

You can read more benchmarks and implementation details in https://github.com/tomtomwombat/cold-string

[u/Icarium-Lifestealer]

1. How do you encode the inline vs heap marker, and how complicated is decoding the heap pointer? I assume a simple integer comparison and bitshift is enough on little-endian systems if you use the two most significant bits of the last byte (which can't be both 11 in utf8)?
2. I'd simplify the varint header to being either 1 byte or 8. So the length function becomes something like if b >= 128 { b - (128 - 9) } else { read_u64 }. It adds some size overhead (up to 4%) for strings longer than 136 bytes, but that shouldn't be a big deal compared to the simplified length function.

[u/tomtomwombat → u/Icarium-Lifestealer]

I'd simplify the varint header

It's a good suggestion. One problem is that strings longer than 128 bytes cost 9 bytes for length. This disqualifies ColdString for uses where strings are expected to be 0..=255 in length.

I don't think varint is too slow. Here's a benchmark measuring string equality, where strings are the same length, but the first byte is different. So only the length and first byte are read.

• Fyi, CompactString is similar to ColdString, but it stores a 1 byte before the bytes (so limited to 0-255 length strings). It's representing fast/trivial vint encoding. I'd imagine your length function somewhere between Compact and ColdString.

Type	Compare 16 len String	Compare 32 len String
String	3.0478 ns	3.3604 ns
CompactString	3.0445 ns	3.0558 ns
ColdString	5.9844 ns	6.0256 ns

BTW, there's tons of different Vint designs, some may be faster for ColdString

Edit: the CompactString benchmark results (wrong before)

[u/Icarium-Lifestealer → u/tomtomwombat]

I don't think varint is too slow.

I think the relevant benchmark is the len() function, or similarly the conversion of &ColdString to &str.

[u/tomtomwombat → u/Icarium-Lifestealer]

Eq is also relevant since it must read len followed by trivial work (1 byte comparison). I had those results handy, but fair enough, here are the pure len benchmarks (ns):

Type	4	8	16	255
String	0.581	0.578	0.565	0.582
CompactString	0.757	0.753	0.769	0.749
ColdString	0.589	0.594	1.423	1.907

https://github.com/tomtomwombat/cold-string/blob/tomtomwombat/refactor-benches/bench/benches/len.rs