5 ms·

This is explained in the official docs: to avoid too many allocations when repeatedly concatenating strings. > Implements the + operator for concatenating two

by magnio 5y ago

This is explained in the official docs: to avoid too many allocations when repeatedly concatenating strings. > Implements the + operator for concatenating two strings. > This consumes the String on the left-hand side and re-uses its buffer (growing it if necessary). This is done to avoid allocating a new String and copying the entire contents on every operation, which would lead to O(n^2) running time when building an n-byte string by repeated concatenation.

Dylan16807 5y ago
What does that explain? Let's say you did add(add("foo", "bar"), "baz"). The inner add would return a String, and then all subsequent adds would have the exact same optimization you're quoting. There is no downside, performance-wise.
- masklinn 5y ago
  That can not typecheck in Rust, unless you use something really odd like `Into<Cow<‘a, A>> where A: Add<B>` as your input types. And in languages where it does, you need either ubiquitously mutable strings (which everyone’s moved from because it generally screws you up) or refcounting.
  - Dylan16807 5y ago
    > That can not typecheck in Rust, unless you use something really odd like `Into<Cow<‘a, A>> where A: Add<B>` as your input types. I'm not entirely sure what that means, but here I'll just go implement a version: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=140aa13a0ece32a5a333bcea42d07b69 https://play.rust-lang.org/?version=stable&mode=debug&editio... I think this is right. I haven't written Rust before. I copied Add to RAdd because you can't implement traits you don't own on types you don't own. And I didn't bother implementing it for numbers. There's a trait implementation that takes String and &str (directly copied from Add), and there's a version that takes &str and &str. Both of them return String. The generic function is just as generic as it always was, but of course you can't do this with actual Add without changing the standard library. You'd have to make the function less generic instead. > And in languages where it does, you need either ubiquitously mutable strings (which everyone’s moved from because it generally screws you up) or refcounting. It's the same String as ever. Owned and mutated by adding.
  - gpderetta 5y ago
    But mutable string are not an issue when not shared, which can be checked statically in rust, right?
- eklavya 5y ago
  No, they won't in standard implementations we are not exactly allocating, the allocated buffer doubles each time, so it's amortised and not O(n^2). There is a downside for non trivial example code.
  - Dylan16807 5y ago
    Every add except the first one is using the same code in either version. The suggested change does not affect String + &str at all.
    - eklavya 5y ago
      Ok, maybe I misunderstood, I thought you were saying &str + &str with precomputed capacity in call cases, let me read it again.
vintermann 5y ago
Sure, but it would have been a legitimate choice to let + do that, and use other functions to handle those use cases where it matters. After all, I expect to get a brand new value from an addition. If a = 2 b = 3 c = a + b I certainly do not expect "a" to be modified. So why would I expect it with strings? It would be no problem to warn the user about repeated concatenation with +, as I recall Java with its immutable strings does just that.
- Arnavion 5y ago
  >After all, I expect to get a brand new value from an addition. [...] I certainly do not expect "a" to be modified. So why would I expect it with strings? To be clear, your expectations are not betrayed when doing String + &str -> String in Rust. The String addend is consumed by + and attempting to reuse it will produce an error. So it's not like you notice that the String you used to have has implicitly been modified.
  - tialaramex 5y ago
    We call this being consumed, "moving". And in Rust actually your integer 'a' was the special case. Every value gets moved when you add it to something else, but this integer 'a' is still available to be used after it was moved. What happens there is, the integer types implement Copy which is a special Trait that says, "I promise I don't have any meaning beyond my actual pattern of bits in a memory location or a register or whatever". If the type implements Copy then when 'a' gets moved, it is logically still fine to keep 'a' around anyway in case anybody still wanted it, as you can freely make or destroy copies of the bit pattern and this type has no meaning beyond the bit pattern. You can derive Copy (or implement it) on your own types if the Rust compiler can see why that's a reasonable claim to make for your type, otherwise you can't. So String couldn't be Copy, because it clearly has a reference to a vector (of bytes) inside it making it work and so the bit patterns are just pointing at the memory address of that vector of bytes.
  - vintermann 5y ago
    My expectations are betrayed, but I do appreciate that Rust at least stops me if that expectation matters. Really, whenever I concatenate something variable-length like a string, I know there's potential allocation under the hood. There has to be. What I don't get is why that allocation has to be hidden as a mutation of a, rather than just be explicit as yeah, c is a new thing. I expect functions to return new things rather than mutate things via side effects. Isn't it better to let addition stay a function, rather than overload of + being slightly more convenient/efficient for building up strings?

by magnio 5y ago

Dylan16807 5y ago

What does that explain? Let's say you did add(add("foo", "bar"), "baz"). The inner add would return a String, and then all subsequent adds would have the exact same optimization you're quoting. There is no downside, performance-wise.

masklinn 5y ago
That can not typecheck in Rust, unless you use something really odd like `Into<Cow<‘a, A>> where A: Add<B>` as your input types. And in languages where it does, you need either ubiquitously mutable strings (which everyone’s moved from because it generally screws you up) or refcounting.
- Dylan16807 5y ago
  > That can not typecheck in Rust, unless you use something really odd like `Into<Cow<‘a, A>> where A: Add<B>` as your input types. I'm not entirely sure what that means, but here I'll just go implement a version: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=140aa13a0ece32a5a333bcea42d07b69 https://play.rust-lang.org/?version=stable&mode=debug&editio... I think this is right. I haven't written Rust before. I copied Add to RAdd because you can't implement traits you don't own on types you don't own. And I didn't bother implementing it for numbers. There's a trait implementation that takes String and &str (directly copied from Add), and there's a version that takes &str and &str. Both of them return String. The generic function is just as generic as it always was, but of course you can't do this with actual Add without changing the standard library. You'd have to make the function less generic instead. > And in languages where it does, you need either ubiquitously mutable strings (which everyone’s moved from because it generally screws you up) or refcounting. It's the same String as ever. Owned and mutated by adding.
- gpderetta 5y ago
  But mutable string are not an issue when not shared, which can be checked statically in rust, right?
eklavya 5y ago
No, they won't in standard implementations we are not exactly allocating, the allocated buffer doubles each time, so it's amortised and not O(n^2). There is a downside for non trivial example code.
- Dylan16807 5y ago
  Every add except the first one is using the same code in either version. The suggested change does not affect String + &str at all.
  - eklavya 5y ago
    Ok, maybe I misunderstood, I thought you were saying &str + &str with precomputed capacity in call cases, let me read it again.

vintermann 5y ago

Sure, but it would have been a legitimate choice to let + do that, and use other functions to handle those use cases where it matters. After all, I expect to get a brand new value from an addition. If a = 2 b = 3 c = a + b I certainly do not expect "a" to be modified. So why would I expect it with strings? It would be no problem to warn the user about repeated concatenation with +, as I recall Java with its immutable strings does just that.

Arnavion 5y ago
>After all, I expect to get a brand new value from an addition. [...] I certainly do not expect "a" to be modified. So why would I expect it with strings? To be clear, your expectations are not betrayed when doing String + &str -> String in Rust. The String addend is consumed by + and attempting to reuse it will produce an error. So it's not like you notice that the String you used to have has implicitly been modified.
- tialaramex 5y ago
  We call this being consumed, "moving". And in Rust actually your integer 'a' was the special case. Every value gets moved when you add it to something else, but this integer 'a' is still available to be used after it was moved. What happens there is, the integer types implement Copy which is a special Trait that says, "I promise I don't have any meaning beyond my actual pattern of bits in a memory location or a register or whatever". If the type implements Copy then when 'a' gets moved, it is logically still fine to keep 'a' around anyway in case anybody still wanted it, as you can freely make or destroy copies of the bit pattern and this type has no meaning beyond the bit pattern. You can derive Copy (or implement it) on your own types if the Rust compiler can see why that's a reasonable claim to make for your type, otherwise you can't. So String couldn't be Copy, because it clearly has a reference to a vector (of bytes) inside it making it work and so the bit patterns are just pointing at the memory address of that vector of bytes.
- vintermann 5y ago
  My expectations are betrayed, but I do appreciate that Rust at least stops me if that expectation matters. Really, whenever I concatenate something variable-length like a string, I know there's potential allocation under the hood. There has to be. What I don't get is why that allocation has to be hidden as a mutation of a, rather than just be explicit as yeah, c is a new thing. I expect functions to return new things rather than mutate things via side effects. Isn't it better to let addition stay a function, rather than overload of + being slightly more convenient/efficient for building up strings?