Comment by chrismorgan | Hacker News Reader

Comment by chrismorgan | Hacker News Reader

> In the above example, on every loop, the += operator causes a new string to be allocated, and the content to be copied, which gets exponentially more expensive as the string grows.

But that’s only the theoretical behaviour. In practice, languages tend to end up optimising it in various ways. As noted a paragraph later, the Java compiler is able to detect and “fix” this, by rewriting the code to use a mutable string.

Another solution is to put concatenation into your string type as another possible representation. I believe at least some (no idea if it’s all) JavaScript engines do this. You end up with something like this (expressed in Rust syntax, and much simpler than the real ones are):

  enum String {
      Latin1(Vec<u8>),
      Utf16(Vec<u16>),
      Concatenated(String, String),
  }

Then, when you try to access the string, if it’s Concatenated it’ll flatten it into one of the other representations.

Thus, the += itself becomes cheap, and in typical patterns you only incur the cost of allocating a new string once, when you next try to read from it (including things like JSON.stringify(object_containing_this_string) or element.setAttribute(name, this_string)).

> As noted a paragraph later, the Java compiler is able to detect and “fix” this, by rewriting the code to use a mutable string.

Does it actually do that nowadays? Back in my days it was incapable of lifting the builder out of loops, so for each iteration it would instantiate a builder with the accumulator string, append the concatenation, then stringify and reset the accumulator.

The linked docs don’t say anything about loops.

I agree. If you append to a string in a loop in Java, you will see quadratic behavior.

An option you did not mention, although not generally available to languages with advanced runtime, is that even if you have immutable strings you can realloc them if you know you're the only owner of that string (e.g. because they're refcounted, or can't be shared).

CPython does that, so a trivial concatenation loop is (amortised) linear (causing issues for alternate implementations when they have to run that). Swift might also be able to via COW optimisation.

Rust's string concatenation is a variant of this (though it has mutable strings anyway): `String::add` takes an owned value on the LHS, and the implementation just appends to the LHS before returning it:

    fn add(mut self, other: &str) -> String {
        self.push_str(other);
        self
    }

so repeated concatenation will realloc and amortize as if you were just `push_str`-ing in a loop (which maps directly to appending to the underlying buffer).

For more technical precision in Rust (not because it actually changes anything), += will use AddAssign rather than Add, if it’s implemented, which mutates in-place, whereas `a = a + b` would move twice (though in a way that will always optimise to the same thing). This means you’re actually invoking

  impl AddAssign<&str> for String {
      #[inline]
      fn add_assign(&mut self, other: &str) {
          self.push_str(other);
      }
  }

which the doc comment notes “has the same behavior as the `push_str` method”.

And this shows yet another option: add a separate overload for +=. Python does actually have that in the form of the __iadd__ magic method, and I presume CPython’s optimisation could be implemented that way, though it doesn’t look to be (and this might not have quite the same semantics, I’m not sure):

  class str:
      def __iadd__(self, other):
          if sys.getrefcount(self) == probably 2, it’s fiddly:
              mutate self
          raise NotImplemented

Maybe I'm missing something, but I thought that when you "grow" an array or a string, eventually something under the hood needs to call realloc()? which allocates a bigger chunk of memory and copies the content O(n)? Why would it matter if you manually do alloc() and then memcpy() (replacing an immutable string with its concatenation) vs letting the runtime do it for you with realloc()?

There are two differences.

① A growable string type overallocates, so you only eventually need to reallocate. An immutable string type has an exact-size allocation, so you must make a new allocation every time.

② An immutable string type can’t use realloc() anyway unless you can prove nothing else holds a reference to it, it needs to use a new malloc().

You're basically describing the Rope. Fancier versions use self balancing trees, allowing other string operations to be fairly efficient too.

https://en.wikipedia.org/wiki/Rope_(data_structure)

Wow, if that is true then that‘s the most succinct explanation of Ropes I have seen. Super helpful if you are trying to learn about them, like I am.

It's partway to being a rope, I would say some balancing and the ability to replace substrings are crucial to a real rope.

> Another solution is to put concatenation into your string type

Aah, the Erlang way of handling strings.

On Beam (Erlang's VM), that goes as deep as IO. It's perfectly fine to pass a (possibly nested) list of strings (whether charlists or binaries) to an IO function, and the system just knows how to deal with that.

An iolist isn't a string, you can't pass it to the uppercase function for instance. It's really meant for I/O as the name implies. Regular string concatenation is optimized to avoid copying when possible: https://www.erlang.org/doc/system/binaryhandling.html#constr...

Reply on news.ycombinator.com