There's a nice explanation on their readme[2]. Love tricks like this.
[1]: https://github.com/ParkMyCar/compact_str
[2]: https://github.com/ParkMyCar/compact_str?tab=readme-ov-file#...
Fun fact, it was this fasterthanlime post that originally inspired me to play around with small strings and led to the creation of compact_str.
The goal would be to compare two strings using only the 24-byte values, without touching the allocated part (if it points into a string larger than 24 bytes)
The first thing that makes me think this is impossible is that you only define an owned variant for your string type. But your can cleverly wrap a &'static str rather than allocate on heap, so if the interner can give a &'static str I think this could work, with some boilerplate. Namely: for strings smaller than 24 bytes don't intern and build a CompactString inline, for larger strings, intern, get a &'static str, then build a CompactString out of it. Then, two check if two strings are equal, you just compare its 24 bytes, and don't need to touch the interner for this at all.
However this only works if the interner actually leaks memory. If it returns you a &'a str that isn't 'static, then you can't store it on CompactString, unless your lib also provided a borrowed variant.
Also, to think about it, since interned strings are immutable (they are not a "string builder" like String is), you don't really need the capacity value for them, just the length. So it suggests a 16 bytes size, not 24. (but one could imagine an application where it's optimal to store 24 bytes inline rather than 16 anyway)
I think that this could be achieved with an 16 bytes &str wrapper, maybe something like &CompactStr, that works just like your CompactString, but wraps a &str instead (and offers no owned variant). Maybe such a thing could conceivably be included in the compact_string crate?
(Maybe make it 24 bytes even if it "wastes" some bytes, just to make it bitwise compatible with CompactString, so that borrowing CompactString into &CompactStr is zero cost - and then just zero out the remaining 8 bytes when a &CompactStr is stored on the heap)
[0] I was reading this post https://dev.to/cad97/string-interners-in-rust-797 that was written in response to this fasterthanlime post, but it contrasts interner with small string optimization, when you actually could have both!
... well except it stores up to 15 bytes inline rather than using the UTF-8 trick to cram an extra byte. (But maybe it can't; or at least, ByteYarn really can only store 15 bytes, even though Yarn could store 16 bytes maybe, but this would pose problems when converting between those types because I suppose this conversion is zero cost)
The optimal size will depend on the application. It's certainly reasonable that in some applications, many/most strings would be under 24 bytes and thus the small string optimization in many of these implementations would be beneficial. Perhaps in some other application strings are closer to 32 bytes (or something else) and then a larger stack size would be warranted. And in yet other applications, strings are large and no small string optimizations will make any difference, and if anything will slow the application down with unnecessary bookkeeping.
I do find it surprising that none of the implementations in the various comments linked in this thread seem to provide user-tunable sizes; or at least I haven't seen it. Because I can certainly imagine cases where the optimal size is > 24.
It's quite possible to make the small string buffer larger, but that comes at the cost of the large string representation taking up more space than necessary on the stack. IIRC libstdc++ does this, which makes its std::string take up 32 bytes on the stack.
Though to follow through on that, 24 bytes is also more than necessary. You don't have to be very clever to shrink your string size to 16 bytes (6 for the pointer, 6 for the size, 4 to store either capacity or spare capacity as floating point).
Why is Rust's String 24 bytes? Well, this is a growable string type. So we need to store 1) where on the heap our growable buffer is and 2) how big that heap space is ("Capacity"), and 3) how much of it we're using already to store the string ("Size" or "Length"). On modern 64-bit computers it's reasonable to use a 64-bit (8 byte) value for all three of these facts, 3 times 8 = 24.
In fact Rust (unlike C++) insists on doing this the simplest and fastest way possible so the String type is more or less literally Vec<u8> - a growable array of bytes, plus a guarantee that those bytes are UTF-8 encoded text. Vec<u8> is likewise 24-bytes.
The rationale is that being simple is a good fundamental design, and (as CompactString illustrates) people can build more sophisticated types if they want to unlock specific optimisations which may suit their application.
That's why the c_str method exists, so you can get a pointer to a null terminated character array
It is as of C++11. The constness of c_str() threw a wrench into that as soon as C++ got a threading model.
std::string::c_str returns the same address as &string[0]
Note that this by itself doesn't imply null-termination, though as you say strings are indeed null-terminated now.
Edit: This is not particularly obvious, but the reason this has nothing to do with allocation or the return value is that the implementation could still leave space for the null terminator, but avoid actually setting it to zero until c_str() is invoked. That would neither affect the returned pointer nor the constant-time guarantee.
Yes, by definition.
> Then if it must point to the actual backing store, then that must also be a valid null terminated C string as there's no other way to use them.
No, this doesn't follow. The buffer could leave room for the terminator but not actually write the terminator until c_str() is called. That's why the C++11 standard had to explicitly require that the string always be null-terminated regardless of whether c_str() is called.
Thanks for the explanation!
Note that c_str() could've inserted the terminator in constant time, as long as the string kept space reserved for that. So this wouldn't have violated constant-time-ness, and it's not an insane thing to do considering it would save some instructions elsewhere. But yeah, the flexibility wasn't all that useful even in the beginning, and became even more useless as soon as C++ incorporated threading, due to the constness of the function.
That said, I don’t see why it wouldn’t be possible to cram in 24 bytes of null-terminated payload (so 23 useful ones, the best you could hope for with null termination) into the same structure the same way by storing the compact version with null termination and ensuring the last byte is also always zero. For extra style points, define the last byte to be 24 minus payload length instead so you don’t need to recompute the length in the inline case.
To be clear: none of this makes null termination not dumb.
I want to say libc++ and maybe MSVC do something along those lines in their std::string implementations.
> For extra style points, define the last byte to be 24 minus payload length instead so you don’t need to recompute the length in the inline case.
IIRC Facebook's FBString from Folly does (did?) that?
Here's Raymond Chen on this topic earlier this same year. As a bonus since you're looking at this in August it's more or less correct now, whereas when it was published it had numerous serious errors. Whether the standard library implementation of such an important type should be so complicated that an expert makes numerous errors is another question...
https://devblogs.microsoft.com/oldnewthing/20240510-00/?p=10...
So, libc++ gets closest, 1 flag byte + 22 bytes of text + 1 byte of ASCII NUL = 24 bytes
The others are much worse, larger (32 bytes on modern computers) yet with lower SSO capacity (15 bytes of text).
Note that I didn't say this is impossible, just that the given trick wouldn't work.
However, this is impossible for general strings. The only way could possibly make this work is if you constrain the inline string somehow (e.g., to UTF-8), so that some shorter strings failing that constraint are forced to go on the heap too. Otherwise you have 1 fixed zero byte at the end, and 23 fully flexible bytes, leaving you no way to represent an out-of-line string.
(Well, you could do it if you use the address as a key into some static map or such where you shove the real data, but that's cheating and beside the point here.)
Inline strings only use 0.4% of your possible values.
> 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
I stared at this for too long, as it allows collision. Then I realized you'd never set the third bit, it should probably have been written 0b110XXXXX and recorded that 5 bits are used for length. Right or did I understand it wrong?
Rust has "niches" - bit patterns which are never used by that type and thus can be occupied by something else in a sum type (Rust's enum) which adds to that type. But stable Rust doesn't allow third parties to promise arbitrary niches exist for a type they made.
However, if you make a simple enumeration of N possibilities that automatically has a niche of all the M-N bit patterns which weren't needed by your enumeration in the M value machine integer that was chosen to store this enumerated type (M will typically be 256 or 65536 depending on how many things you enumerated)
So, CompactString has a custom enum type LastUtf8Char which it uses for the last byte in its data structure - this has values V0 through V191 corresponding to the 192 possible last bytes of a UTF-8 string. That leaves 64 bit patterns unused. Then L0 through L23 represent lengths - inline strings of length 0 to 23 inclusive which didn't need this last byte (if it was 24 then that's V0 through V191). Now we've got 40 bit patterns left.
Then one bit pattern (the pattern equivalent to the unsigned integer 216) signifies that this string data lives on the heap, the rest should be interpreted accordingly, and another (217) signifies that it's a weird static allocation (I do not know why you'd do this)
That leaves 38 bit patterns unused when the type is finished using any it wanted so there's still a niche for Option<CompactString> or MyCustomType<CompactString>
> ... and another (217) signifies that it's a weird static allocation (I do not know why you'd do this)
In addition to String Rust also has str[1], which is an entirely different type. It's common to represent string literals known at compile time as `&'static str`, but they can't be used in all of the same places that a String can. For example, you can't put a &'static str into a Vec<String> unless you first heap allocate and create a String. We added the additional variant of 217 so users of CompactString could abstract over both string literals and strings created at runtime to solve cases like the example.
Since I have you here, wouldn't it be better to name that type "LastByte" or something? It's not a (Rust) char, and it's not necessarily UTF-8 whereas it is definitely the last byte.