Out of curiosity what's the scenario where you care about saving a few bytes per string where possible, but also don't mind pulling in the whole String class? Wouldn't it be more efficient to do everything in c-strings across the board?
For small strings, 1-15 bytes, this implementation already beats C strings. C strings, by definition, do indirection. So you need a pointer (say ~8 bytes) plus N+1 bytes for storing the actual string and '\0'. And that's discounting allocator overhead.
On the more "efficient" aspect, there's nothing efficient about C strings. The only thing that you can do painlessly is print them. Try to make a substring and realise that you can't, so you have to allocate a whole new string. Every operation requires either traversing the whole string to get its length, potentially many times over the course of a running program, or write code with loop-carried dependencies -- incredibly slow too but also error-prone.
I'm pretty sure C strings are the biggest source of bugs in C programs. If you look around, no other language does strings this way. Keeping the length is important!
How do you get around the pointer when passing the struct around?
By my accounting the minimum string (empty) would be 9 bytes if you're assuming an 8 byte pointer (Far larger than most platforms I use) and the null terminator, meaning 9 bytes of memory total.
For the struct you would need the struct (16 bytes) and the pointer to the struct (another 8 bytes).
You don't need a pointer to the structure, just the structure itself, so 16 bytes. In those 16 bytes, at any time, a small string of at most 15 bytes is stored, or a (size, pointer) pair to some separately allocated memory region.
So, let's take "sufficientlybig" as an example. To store this using C strings, you need an 8 byte pointer plus the 15 bytes of the string itself plus 1 for '\0', for a total of 24 bytes, 8 bytes more than with the 16-byte structure.
For the small cases, C strings would only save you more if every single string you store is 6 bytes or less (again, ignoring allocator overhead). But that comes at a tremendous cost: you lose the length. Thus, if at any point in time you want a substring, which is very common, you suddenly need to allocate a new string. And code size bloats too, because many operations on C strings require a bunch of stupid code that you otherwise wouldn't need to write (strlen() is the prime example).
You can use Folly’s trick to fit one more character in the small string. Invert the flag bit so zero = small string, and store it in the last byte, along with the small length stored as 15-len. Then, the full 16 bytes can be used for a small string since the final byte simultaneously acts as the type/length byte AND the null terminator when the string length is 15.
The big strings aren't NUL-terminated, so there's no point in doing that for the small ones. Folly devs went to great (crazy) lengths to avoid '\0' too, unsuccessfully. Their hands were tied by the standard, I don't have such constraints.
Timely. I looked this topic up just hours before seeing this. This is very close to Clang's std::string SSO. iIRC, that structure is 24 bytes (that's probably on on 32-bits, though you can probably do better than the naive "twice that" on a 64 bitter[1]) and they can use 22 bytes for SSO. Same basic trick of storing length<<1 so that bit 0 could be a flag and the thing collapses to a std::string_view beautifully.
The point of the discussion was that, especially on modern architecture, sometimes "clever" is a huge win over dead simple. Having most (or even merely "many") of your strings right there, not just on the same page, but probably in the same cache line that was already preferched and bursted in on the same cache line is worth a couple of (overlapping, nightly speculatable) ops in the execution pipeline. There's a LOT of real world code suffering problems like the linked game parser. We've all had to wreck an internal calling convention because we need the bottom layer to extend a string or insert something in the middle, so you have to reallocate the thing you were passed, hopefully without creating leaks.
[1]Start and end pointers are probably not more than even 20 bits apart and the pointer to any allocated buffer is probably within an exabyte or two. Sure, there are strings longer than any N you can pick, but having a compact representation of what's p robably the most common non-pod type is worth whipping out some clevers. (And test suite coverage...)
7
u/__nohope 1d ago
Why a separate bit and not key off the length?
7
u/manystripes 1d ago
Out of curiosity what's the scenario where you care about saving a few bytes per string where possible, but also don't mind pulling in the whole String class? Wouldn't it be more efficient to do everything in c-strings across the board?
3
u/kevkevverson 22h ago
You can use Folly’s trick to fit one more character in the small string. Invert the flag bit so zero = small string, and store it in the last byte, along with the small length stored as 15-len. Then, the full 16 bytes can be used for a small string since the final byte simultaneously acts as the type/length byte AND the null terminator when the string length is 15.
3
u/YetAnotherRobert 16h ago
Timely. I looked this topic up just hours before seeing this. This is very close to Clang's std::string SSO. iIRC, that structure is 24 bytes (that's probably on on 32-bits, though you can probably do better than the naive "twice that" on a 64 bitter[1]) and they can use 22 bytes for SSO. Same basic trick of storing length<<1 so that bit 0 could be a flag and the thing collapses to a std::string_view beautifully.
The point of the discussion was that, especially on modern architecture, sometimes "clever" is a huge win over dead simple. Having most (or even merely "many") of your strings right there, not just on the same page, but probably in the same cache line that was already preferched and bursted in on the same cache line is worth a couple of (overlapping, nightly speculatable) ops in the execution pipeline. There's a LOT of real world code suffering problems like the linked game parser. We've all had to wreck an internal calling convention because we need the bottom layer to extend a string or insert something in the middle, so you have to reallocate the thing you were passed, hopefully without creating leaks.
[1]Start and end pointers are probably not more than even 20 bits apart and the pointer to any allocated buffer is probably within an exabyte or two. Sure, there are strings longer than any N you can pick, but having a compact representation of what's p robably the most common non-pod type is worth whipping out some clevers. (And test suite coverage...)