4 ms·

> “short string optimization”: A short enough string can be stored “in place” [...] An optimization that’s impossible in Rust, by the way ;). Author is not awa

by Rygian 2y ago

> “short string optimization”: A short enough string can be stored “in place” [...] An optimization that’s impossible in Rust, by the way ;). Author is not aware of https://docs.rs/compact_str/latest/compact_str/ https://docs.rs/compact_str/latest/compact_str/ or https://github.com/bodil/smartstring https://github.com/bodil/smartstring

diggan 2y ago
That documentation talks about all the benefits and "can mostly be used as a drop in replacement for String", but what are the tradeoffs? When cannot it be used?
- tialaramex 2y ago
  It looks like there's a bunch of "garbage collection" type activity where you may have some bytes which were once part of a string but aren't now used, and you're always paying for the overhead of this optimisation even if it's useless for your problem. Suppose you work only with 500-4000 byte strings, maybe they're short reviews, and each ends with a rating in star emoji, ***** is the best * is the worst. [[HN ate my star emoji of course]] So your reviews never fit in the "optimised" string slot, but also the prefix is just opening words from a review, which in some review styles will be the start of seemingly unrelated anecdotes. "My grandfather used to tell me" it'll get to the review eventually, and you'll see why they're connected, but the suffix is useful and that's not stored in a "German string" data structure. Or maybe you have a high turnover of somewhat related medium size strings, so then that garbage collection step costs quite a lot of overhead.
- LegionMammal978 2y ago
  Any code built closely around String's power-of-2 reallocation pattern may have to be reworked. I don't think there's any case when it cannot be used as a String replacement at all, except maybe when interfacing with an API that expects a &mut String as an output parameter.
- runeblaze 2y ago
  My uninformed guess is that at least it will cost you the branching because you need to check if it is inlined or not, and you pay that for every string. Branch prediction is likely very good for this case though.
charliermarsh 2y ago
Was this section removed? I'm not seeing it in the linked post.
- tialaramex 2y ago
  It seems to be a quote from https://cedardb.com/blog/german_strings/ https://cedardb.com/blog/german_strings/ which is about this German Strings type (implemented in Polars) But yeah, it's pretty ignorant to assume Rust can't do this since the best available examples (as with many things) are in Rust. CompactString is really nice. On a typical modern (64-bit) computer CompactString takes 24 bytes and holds up to 24 bytes of UTF-8 text inline, while also having a niche. I guess the confusion arises because C++ people tend to assume that anywhere Rust differs from the practice in the C++ community it's a mistake, even though that's often because C++ made the wrong choice? Rust's &str is "just" &[u8] plus a rule about the meaning of these bytes, and Rust's String is correspondingly "just" Vec<u8> plus a rule about the meaning of those bytes. C++ couldn't have done the former because it only belatedly got the fat pointer slice reference (as the troubled std::span) years after having a string data type. Rust didn't do this in the stdlib, but not because it's impossible, because it's a trade off and they wanted the provided stdlib type to be straightforward. If you need or even just want the trade off, you can just cargo add compact_str
  - throwaway48540 2y ago
    I remember some C++ colleagues raving on about the standard library having anything and everything they might ever need. Makes sense in a world without sane package managers and package registries, but that mindset just doesn't carry over.
    - adrianN 2y ago
      That development is quite recent. The stdlib used to be very barebones. It still is compared to for example the Python one.
    - kalaksi 2y ago
      A decent standard library very much makes sense even with sane package managers and registries. Just look at JS. It's awful that you need to hunt for packages for simple stuff (or implement yourself). Stdlib is usually straightforward to use, good quality, trustworthy and good and lasting support
ladyanita22 2y ago
Why is it impossible in Rust? Do you have any source for that?
- steveklabnik 2y ago
  It is not. It is not implemented in std::string::String, but (as pointed out elsewhere in this thread) there are other string implementations that have it. It was decided explicitly against for the standard library, because not every optimization is universally good, and keeping String as a thin wrapper over Vec<T> is a good default.
  - mhh__ 2y ago
    When are small strings bad? Parallelism?
    - workingjubilee 2y ago
      The "small string optimization" makes the strings harder to manipulate with `unsafe` code. However, being easy to manipulate with `unsafe` code is in fact a priority for most std types, so that they are easily understood, extended, rearranged, passed over FFI and then later reconstituted, etc. You can tear apart these types and reassemble them very easily. For many C++ std types, you cannot do this.
    - n_plus_1_acc 2y ago
      You'll need to branch on most operations to check "am i small?". This may cause issues with the Branche predictor.
    - kibwen 2y ago
      Rust APIs use string slices (&str) extensively. With its current design, converting from a String to a &str is a no-op; if String instead did small string optimization, converting to &str wouldn't be free. Furthermore, thanks to the borrow checker, Rust code tends to avoid copying strings around, so the benefit of SSO is reduced. C++ does more string copying and didn't have a standard string_view for a long time, so considering the tradeoffs both languages made reasonable decisions.
jtrueb 2y ago
This is false. The polars api has used smart string for a long time. https://github.com/pola-rs/polars/blob/32a2325b55f9bce81d0193eef26591aeba713efd/Cargo.toml#L82 https://github.com/pola-rs/polars/blob/32a2325b55f9bce81d019...

by Rygian 2y ago

diggan 2y ago

That documentation talks about all the benefits and "can mostly be used as a drop in replacement for String", but what are the tradeoffs? When cannot it be used?

tialaramex 2y ago
It looks like there's a bunch of "garbage collection" type activity where you may have some bytes which were once part of a string but aren't now used, and you're always paying for the overhead of this optimisation even if it's useless for your problem. Suppose you work only with 500-4000 byte strings, maybe they're short reviews, and each ends with a rating in star emoji, ***** is the best * is the worst. [[HN ate my star emoji of course]] So your reviews never fit in the "optimised" string slot, but also the prefix is just opening words from a review, which in some review styles will be the start of seemingly unrelated anecdotes. "My grandfather used to tell me" it'll get to the review eventually, and you'll see why they're connected, but the suffix is useful and that's not stored in a "German string" data structure. Or maybe you have a high turnover of somewhat related medium size strings, so then that garbage collection step costs quite a lot of overhead.
LegionMammal978 2y ago
Any code built closely around String's power-of-2 reallocation pattern may have to be reworked. I don't think there's any case when it cannot be used as a String replacement at all, except maybe when interfacing with an API that expects a &mut String as an output parameter.
runeblaze 2y ago
My uninformed guess is that at least it will cost you the branching because you need to check if it is inlined or not, and you pay that for every string. Branch prediction is likely very good for this case though.

charliermarsh 2y ago

Was this section removed? I'm not seeing it in the linked post.

tialaramex 2y ago
It seems to be a quote from https://cedardb.com/blog/german_strings/ https://cedardb.com/blog/german_strings/ which is about this German Strings type (implemented in Polars) But yeah, it's pretty ignorant to assume Rust can't do this since the best available examples (as with many things) are in Rust. CompactString is really nice. On a typical modern (64-bit) computer CompactString takes 24 bytes and holds up to 24 bytes of UTF-8 text inline, while also having a niche. I guess the confusion arises because C++ people tend to assume that anywhere Rust differs from the practice in the C++ community it's a mistake, even though that's often because C++ made the wrong choice? Rust's &str is "just" &[u8] plus a rule about the meaning of these bytes, and Rust's String is correspondingly "just" Vec<u8> plus a rule about the meaning of those bytes. C++ couldn't have done the former because it only belatedly got the fat pointer slice reference (as the troubled std::span) years after having a string data type. Rust didn't do this in the stdlib, but not because it's impossible, because it's a trade off and they wanted the provided stdlib type to be straightforward. If you need or even just want the trade off, you can just cargo add compact_str
- throwaway48540 2y ago
  I remember some C++ colleagues raving on about the standard library having anything and everything they might ever need. Makes sense in a world without sane package managers and package registries, but that mindset just doesn't carry over.
  - adrianN 2y ago
    That development is quite recent. The stdlib used to be very barebones. It still is compared to for example the Python one.
  - kalaksi 2y ago
    A decent standard library very much makes sense even with sane package managers and registries. Just look at JS. It's awful that you need to hunt for packages for simple stuff (or implement yourself). Stdlib is usually straightforward to use, good quality, trustworthy and good and lasting support

ladyanita22 2y ago

Why is it impossible in Rust? Do you have any source for that?

steveklabnik 2y ago
It is not. It is not implemented in std::string::String, but (as pointed out elsewhere in this thread) there are other string implementations that have it. It was decided explicitly against for the standard library, because not every optimization is universally good, and keeping String as a thin wrapper over Vec<T> is a good default.
- mhh__ 2y ago
  When are small strings bad? Parallelism?
  - workingjubilee 2y ago
    The "small string optimization" makes the strings harder to manipulate with `unsafe` code. However, being easy to manipulate with `unsafe` code is in fact a priority for most std types, so that they are easily understood, extended, rearranged, passed over FFI and then later reconstituted, etc. You can tear apart these types and reassemble them very easily. For many C++ std types, you cannot do this.
  - n_plus_1_acc 2y ago
    You'll need to branch on most operations to check "am i small?". This may cause issues with the Branche predictor.
  - kibwen 2y ago
    Rust APIs use string slices (&str) extensively. With its current design, converting from a String to a &str is a no-op; if String instead did small string optimization, converting to &str wouldn't be free. Furthermore, thanks to the borrow checker, Rust code tends to avoid copying strings around, so the benefit of SSO is reduced. C++ does more string copying and didn't have a standard string_view for a long time, so considering the tradeoffs both languages made reasonable decisions.

jtrueb 2y ago

This is false. The polars api has used smart string for a long time. https://github.com/pola-rs/polars/blob/32a2325b55f9bce81d0193eef26591aeba713efd/Cargo.toml#L82 https://github.com/pola-rs/polars/blob/32a2325b55f9bce81d019...