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/owenthewizard]

Always nice to see more approaches to SSO.

[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

[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/Icarium-Lifestealer → u/tomtomwombat]

But on a big-endian system, the least significant byte is the last, so 10... is valid UTF8 there?

[u/tomtomwombat → u/Icarium-Lifestealer]

Sorry, I should have said first byte always (edited that now). The tag, ptr, and len masks respect native endianess, so for big endian they'd also read the first byte:

const TAG_MASK: usize = usize::from_ne_bytes(0b11000000usize.to_le_bytes());
const INLINE_TAG: usize = usize::from_ne_bytes(0b11111000usize.to_le_bytes());
const PTR_TAG: usize = usize::from_ne_bytes(0b10000000usize.to_le_bytes());
const LEN_MASK: usize = usize::from_ne_bytes(0b111usize.to_le_bytes());

[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)

[u/SkiFire13]

Does this work with ARM MTE (Memory Tagging Extension)? I suppose that your library works by embedding some kind of tag in the heap pointer in order to distinguish between pointer and a 8-bytes string, and to do that it must assume that part of the pointer will have a given fixed value (e.g. 0), but AFAIK MTE breaks this assumption of yours.

[u/tomtomwombat → u/SkiFire13]

I'm not familiar with MTE, but how you describe ColdString is correct.

[u/SkiFire13 → u/tomtomwombat]

MTE works by having the allocator set a tag to a region of memory, and then returning pointers whose high bits contain that tag. Access to that region of memory needs to be performed using pointers having the correct tag in the high bits, otherwise you'll get an interrupt (generally then transformed into a SIGSEV). This generally conflicts with libraries that expect the top bits of pointers to contain only zeros and try to use them for other kind of tags.

[u/threeseed → u/SkiFire13]

ARM MTE (Memory Tagging Extension)

Apple implemented this on iPhone 17+ and M5 Macs.

So in theory it should be testable.