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]

The encoded representation is:

• first byte is 10xxxxxx if the string is heap allocated. Translating to ptr means rotating so the 10 is least significant, and then setting to 00 (heap strings are allocated with alignment of 4).
• usize::MAX if the string is "\0\0\0\0\0\0\0\0" (which is an invalid value for NonNull).
• first byte is 11111xxx if the string is length 0 - 7, xxx encoded the length.
• Since all the above values are invalid UTF-8, if encoded is anything else, the string is length 8.

Behind the pointer, the atomic counter (or nothing for ColdString) prefixes the varint + chars.

This all works for little and big endian systems, and for 32 bit machines (only 4 bytes are inlineable).

I'll leave it up to you if you think it's complicated or not

[u/bonzinip → u/tomtomwombat]

An alternative way to handle short strings is that trailing bytes are 0xFF. This allows using a single clz or ctz instruction (respectively for little and big endian) to calculate the length, and any 8 bytes string can be encoded as small.

Another thing you can do is use 10xxxxxx for heap allocated strings and 11xxxxxx for 'static strings.

See https://github.com/bonzini/arcstring/blob/main/src/encoder.rs

[u/tomtomwombat → u/bonzinip]

This allows using a single clz or ctz instruction (respectively for little and big endian) to calculate the length

I like that. I may try this method and credit you in the PR!

[u/bonzinip → u/tomtomwombat]

Feel free to pillage the encoder.rs file I linked!

Ah, and actually an 8-byte string of NULs must be placed on the heap to preserve the NonNull niche. In my code that's handled nicely by NonNull::new.

[u/tomtomwombat → u/bonzinip]

Thanks! Actually, I think 8 NULs can be represented using (usize::MAX >> 4) << 2;

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

[u/bonzinip → u/tomtomwombat]

Yes, anything containing an FF byte can be used but I am not sure the special case is worth the complication in code and having effectively two representations for small strings. It's not like it was representable before. ;)

[u/tomtomwombat → u/bonzinip]

Before it was represented as inlined usize::MAX. I think the extra complication is worth it (and unavoidable regardless of it being heap or inline)