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
    }

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);
      }
  }

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