← Back to context

Comment by chrismorgan

20 hours ago

> 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)).

11 comments

chrismorgan

Reply
masklinn  17 hours ago

> 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.

  • emil-lp  17 hours ago

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

masklinn  15 hours ago

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).

  • chrismorgan  14 hours ago

    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

shawn_w  9 hours ago

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)

  • Dylan16807  7 hours ago

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

  • danhau  9 hours ago

    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.

bruce343434  14 hours ago

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()?

  • chrismorgan  13 hours ago

    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().

miki123211  19 hours ago

> 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.