If substrings are the issue, then you can have your cake and eat it too.

Make every string a structure with a length, offset, and a pointer to a string storage structure. Make the string storage structure have a maximum length and a pointer to the start of the actual string data. The string data is just an array of bytes.

The space is allocated in powers of 2. If you go to append and you still have room, you just insert the data. Otherwise you reallocate room, move the existing string, free the old space and allocate at the new place. This makes incremental appends perform just fine. Taking substrings is just as fast. The overhead is seen from following one extra pointer when finding the string.

This is not entirely dissimilar to what you find in, say, Perl or Ruby. (Neither is exactly like this. though I think that Ruby is closer. A lot closer.) It makes building up large strings incrementally perform just fine. Substrings can be taken efficiently (well not in Perl - but look at how Ruby implements backreferences lazily for instance).

But even so in Ruby the += operator is *still* slow, for exactly the technical reason given above. You are creating lots of new objects. Why? Well, very simple. += has defined semantic effects. You can't get those semantic effects without creating new objects. If you want an efficient string append you have to use the special << operator because the semantic effects are visible. Observe:

# Create 2 strings
init_a = "Hello";
init_b = "Hello";
# Duplicate them.
dup_a = init_a;
dup_b = init_b;
# Append to the dups
dup_a += ", World";
dup_b << ", World";
# What do we have?
puts "init_a is '#{init_a}'"; #-> "Hello"
puts "init_b is '#{init_b}'"; #-> "Hello, World"
puts "dup_a is '#{dup_a}'"; #-> "Hello, World"
puts "dup_b is '#{dup_a}'"; #-> "Hello, World"

And there we see why, even with smart data structures where efficiency is achievable, the += operator still has to be slow.

Cheers,
Ben

It is, of course, a compromise between issues. You wind up wasting about a third of your space. (Much less if you just apply the simple heuristic of only creating a string with as little memory as you can, then using the power of 2 trick if someone starts appending to it.) If you want to share objects you either need to do some fancy footwork, or else define semantics in which programmers choose what happens. (Ruby does this, see the code example I gave.)

That algorithmic efficiency and memory usage conflict is no surprise. That is usually true. Scalable algorithms tend to use buffering. Buffering costs memory. Vice versa contortions to avoid using extra memory take excess operations.

As for your suggestion, mine is to not use Java. In other languages you get reasonable default behaviour without having to know language trivia about available types with precise promised tradeoffs. Besides which, string manipulation is not exactly one of Java's strengths.

Cheers,
Ben

When someone says there is a single right answer.

Particularly when it is an answer that makes a set of tradeoffs which doesn't fit some common situations.

Immutable strings can have a simpler structure and are faster to access (to allow resizing you need to allow moving the string). However if you are incrementally building up a large string using strings, immutable strings require recopying, and recopying forces you into an n*n algorithm.

Now, you say, just use a StringBuffer (or whatever the current flavour is) object. Well yes. That works. If you try to implement it in code, though, you will eventually hit other bottlenecks as the garbage collector tries to garbage collect on a huge number of little strings. This happens much later, but I have been there, done that. Collecting lots of little objects eventually becomes its own problem. If it is not natively implemented, then it becomes important to do some sort of naive scaling operation. (Having done this in JavaScript I can report that a good heuristic is that when you push a StringBuffer onto a StringBuffer, you resolve the smaller one. Now create one buffer per row, push those onto the ones per table, scalability is now acceptable.)

You know, this is really a headache. I have been there, done that, and don't like it.

Back to the mutable string. OK, it is an immediate significant overhead. Hrm. But go to incrementally build up a string and it bloody works! The first time. The first thing you try. No need to show how good of a programmer you are, how smart you are. You can go off and be smart about something else.

If that initial overhead is acceptable, you don't ever get into having to waste your time worrying about this cr*p. Been there, done that as well. And given current CPU power, I really prefer always wasting some computer time and not having to take out a day or 3 doing performance profiling so I can figure out how to rewrite code that should work the first time.

So I would say that there is no truly "right answer". There are cases where mutable strings make sense. Cases where immutable strings make sense. For me, most of the time, I prefer having mutable strings that work out reasonably well for any access problem, that is good enough. If it isn't good enough some time, then I will make the hard decisions.

Cheers,
Ben