5 ms·

On the note of small strings, Compact String[1] was i believed released after this article and has a nifty trick. Where Smol and Smart can fit 22 and 23 bytes,

On the note of small strings, Compact String[1] was i believed released after this article and has a nifty trick. Where Smol and Smart can fit 22 and 23 bytes, CompactStr can fit 24! Which is kinda nutty imo, that's the full size of the normal String on the stack.. but packed with actual string data. There's a nice explanation on their readme[2]. Love tricks like this. [1]: https://github.com/ParkMyCar/compact_str https://github.com/ParkMyCar/compact_str [2]: https://github.com/ParkMyCar/compact_str?tab=readme-ov-file#how-it-works https://github.com/ParkMyCar/compact_str?tab=readme-ov-file#...

dataflow 2y ago
Note for C++ developers: Their trick is only possible because the strings are UTF-8 and not null-terminated. It wouldn't work as a drop-in for standard strings in C++.
- kloop 2y ago
  std::string isn't null terminated (or at least it isn't guaranteed to be, I don't think it's forbidden for an implementation to do that). That's why the c_str method exists, so you can get a pointer to a null terminated character array
  - searealist 2y ago
    I think std::string is actually required to be null terminated now in the latest standards. But even before it was basically required as that was the only way to make c_str() constant time.
    - dataflow 2y ago
      > But even before it was basically required as that was the only way to make c_str() constant time. 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.
  - unclad5968 2y ago
    std::string is guaranteed to be null terminated since c++11. std::string::c_str returns the same address as &string[0]
    - dataflow 2y ago
      > 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.
      - masspro 2y ago
        Why downvotes? Ignoring C++11 changes for a minute, c_str is absolutely able to cause a reallocation if it needs to, such that after it returns, its return value and the value of data() are the same. Ergo no, the GP statement alone doesn’t imply anything.
        dpassens 2y ago
        But the return value guarantee is, as far as I can see, a C++11 change, so you can't ignore those. And as of C++11, c_str is noexcept, so it cannot allocate anything.
        dataflow 2y ago
        Please see my edit.
      - dietr1ch 2y ago
        Shouldn't c_str() be null terminated? 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.
  - dataflow 2y ago
    > std::string isn't null terminated It is as of C++11. The constness of c_str() threw a wrench into that as soon as C++ got a threading model.
- neonsunset 2y ago
  Null-terminated strings really are a mistake. Make vectorized algorithms problematic by forcing them to account for page size and paged memory in general as well as always scan for NUL, cannot be easily sliced without re-allocation, are opposite to how languages with better string primitives define them and in general don't save much by passing a single pointer over ptr + length.
  - andersa 2y ago
    It's not really possible to get rid of them in C++ however, given a staggering amount of legacy APIs that require them. Constantly converting every time you have to call a system API with your string is even worse.
    - anp 2y ago
      FWIW Rust also has null-terminated strings available under its std::ffi module. I’m not sure it would be feasible to migrate C++ to the approach of multiple string types now, and I’m not sure it would have been the right approach for C++11 given C++’s approach to interop, but it’s definitely possible to support interoperability with those legacy APIs without constraining a default string type to null-termination.
- mananaysiempre 2y ago
  More of a knock against C than C++, seeing as today’s C++ tends to prefer `string_view`s or at worst iterator pairs, neither of which use null-termination. (Saying that as someone who prefers C to C++ and avoids Rust exactly because of “better C++” vibes—I don’t want a better version of C++, if anything I want a much much simpler one that’s worse at some things.) 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.
  - dataflow 2y ago
    > That said, I don’t see why it wouldn’t be possible to cram in 24 bytes of null-terminated payload 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.)
    - Dylan16807 2y ago
      Think that through again. An inline string needs a fixed 0 byte at the end. A heap string does not. Therefore if the last byte is anything other than 0 you have a heap string. Inline strings only use 0.4% of your possible values.
      - dataflow 2y ago
        Oof, you're right, thank you. In my mind the last byte was obviously zero for a heap string too, since the pointer or sizes would've had a zero upper byte. Somehow I never accounted for the fact that on 64-bit there's no need to represent it that way. Fantastic point!
silisili 2y ago
This is interesting, thanks. > 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?
- tialaramex 2y ago
  Probably this isn't helpful anyway - what's actually going on is more complicated and is explained later at a high level or I'll try now: 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>
  - parkmycar 2y ago
    Author of compact_str here, you hit the nail on the head, great explanation! > ... 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. [1]: https://doc.rust-lang.org/std/primitive.str.html https://doc.rust-lang.org/std/primitive.str.html
parkmycar 2y ago
Hey I'm the author of compact_str, thanks for the kind words! 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.
- conaclos 2y ago
  compact_str is a fantastic crate, used by many projects. Do you know the byteyarn crate [0]? This could be nice to add this to the `Similar Crates` section if it makes sense. [0] https://docs.rs/byteyarn/latest/byteyarn/ https://docs.rs/byteyarn/latest/byteyarn/
  - parkmycar 2y ago
    I do, mcyoung wrote a great blogpost[1] about it! Good idea, I’m AFK at the moment but will add it to the ‘Similar Crates’ section once I’m back [1] https://mcyoung.xyz/2023/08/09/yarns/ https://mcyoung.xyz/2023/08/09/yarns/
- tomcam 2y ago
  I've been wondering something for ages. Where did you get the 24 byte number, and how does it compare in Unicode terms? That is, did you analyze a large corpus and determine that 24 bytes was right for the largest number of strings? And does it come out to, say, 10 Unicode characters? Whenever I think about designing a new language, this very issue pops up.
  - aw1621107 2y ago
    This style of small string optimization tries to take up the same amount of space on the stack as a "normal" heap-allocated string. On 64-bit platforms that is 24 bytes: 8 bytes for the pointer to the heap allocation, 8 bytes for the number of characters/bytes in the string, and 8 bytes for the allocation capacity. 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.

dataflow 2y ago

Note for C++ developers: Their trick is only possible because the strings are UTF-8 and not null-terminated. It wouldn't work as a drop-in for standard strings in C++.

kloop 2y ago
std::string isn't null terminated (or at least it isn't guaranteed to be, I don't think it's forbidden for an implementation to do that). That's why the c_str method exists, so you can get a pointer to a null terminated character array
- searealist 2y ago
  I think std::string is actually required to be null terminated now in the latest standards. But even before it was basically required as that was the only way to make c_str() constant time.
  - dataflow 2y ago
    > But even before it was basically required as that was the only way to make c_str() constant time. 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.
- unclad5968 2y ago
  std::string is guaranteed to be null terminated since c++11. std::string::c_str returns the same address as &string[0]
  - dataflow 2y ago
    > 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.
    - masspro 2y ago
      Why downvotes? Ignoring C++11 changes for a minute, c_str is absolutely able to cause a reallocation if it needs to, such that after it returns, its return value and the value of data() are the same. Ergo no, the GP statement alone doesn’t imply anything.
      - dpassens 2y ago
        But the return value guarantee is, as far as I can see, a C++11 change, so you can't ignore those. And as of C++11, c_str is noexcept, so it cannot allocate anything.
        dataflow 2y ago
        Please see my edit.
    - dietr1ch 2y ago
      Shouldn't c_str() be null terminated? 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.
- dataflow 2y ago
  > std::string isn't null terminated It is as of C++11. The constness of c_str() threw a wrench into that as soon as C++ got a threading model.
neonsunset 2y ago
Null-terminated strings really are a mistake. Make vectorized algorithms problematic by forcing them to account for page size and paged memory in general as well as always scan for NUL, cannot be easily sliced without re-allocation, are opposite to how languages with better string primitives define them and in general don't save much by passing a single pointer over ptr + length.
- andersa 2y ago
  It's not really possible to get rid of them in C++ however, given a staggering amount of legacy APIs that require them. Constantly converting every time you have to call a system API with your string is even worse.
  - anp 2y ago
    FWIW Rust also has null-terminated strings available under its std::ffi module. I’m not sure it would be feasible to migrate C++ to the approach of multiple string types now, and I’m not sure it would have been the right approach for C++11 given C++’s approach to interop, but it’s definitely possible to support interoperability with those legacy APIs without constraining a default string type to null-termination.
mananaysiempre 2y ago
More of a knock against C than C++, seeing as today’s C++ tends to prefer `string_view`s or at worst iterator pairs, neither of which use null-termination. (Saying that as someone who prefers C to C++ and avoids Rust exactly because of “better C++” vibes—I don’t want a better version of C++, if anything I want a much much simpler one that’s worse at some things.) 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.
- dataflow 2y ago
  > That said, I don’t see why it wouldn’t be possible to cram in 24 bytes of null-terminated payload 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.)
  - Dylan16807 2y ago
    Think that through again. An inline string needs a fixed 0 byte at the end. A heap string does not. Therefore if the last byte is anything other than 0 you have a heap string. Inline strings only use 0.4% of your possible values.
    - dataflow 2y ago
      Oof, you're right, thank you. In my mind the last byte was obviously zero for a heap string too, since the pointer or sizes would've had a zero upper byte. Somehow I never accounted for the fact that on 64-bit there's no need to represent it that way. Fantastic point!

silisili 2y ago

This is interesting, thanks. > 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?

tialaramex 2y ago
Probably this isn't helpful anyway - what's actually going on is more complicated and is explained later at a high level or I'll try now: 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>
- parkmycar 2y ago
  Author of compact_str here, you hit the nail on the head, great explanation! > ... 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. [1]: https://doc.rust-lang.org/std/primitive.str.html https://doc.rust-lang.org/std/primitive.str.html

parkmycar 2y ago

Hey I'm the author of compact_str, thanks for the kind words! 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.

conaclos 2y ago
compact_str is a fantastic crate, used by many projects. Do you know the byteyarn crate [0]? This could be nice to add this to the `Similar Crates` section if it makes sense. [0] https://docs.rs/byteyarn/latest/byteyarn/ https://docs.rs/byteyarn/latest/byteyarn/
- parkmycar 2y ago
  I do, mcyoung wrote a great blogpost[1] about it! Good idea, I’m AFK at the moment but will add it to the ‘Similar Crates’ section once I’m back [1] https://mcyoung.xyz/2023/08/09/yarns/ https://mcyoung.xyz/2023/08/09/yarns/
tomcam 2y ago
I've been wondering something for ages. Where did you get the 24 byte number, and how does it compare in Unicode terms? That is, did you analyze a large corpus and determine that 24 bytes was right for the largest number of strings? And does it come out to, say, 10 Unicode characters? Whenever I think about designing a new language, this very issue pops up.
- aw1621107 2y ago
  This style of small string optimization tries to take up the same amount of space on the stack as a "normal" heap-allocated string. On 64-bit platforms that is 24 bytes: 8 bytes for the pointer to the heap allocation, 8 bytes for the number of characters/bytes in the string, and 8 bytes for the allocation capacity. 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.