Re: StringBuffer/StringBuilder efficiency
On Fri, 25 Sep 2009, Roedy Green wrote:
On Fri, 25 Sep 2009 11:45:55 -0700, "Peter Duniho"
<NpOeStPeAdM@nnowslpianmk.com> wrote, quoted or indirectly quoted
someone who said :
Do you mean the "ArrayList" class? How do you think that class is
implemented? The JDK documentation doesn't promise a particular
implementation, but in reality, it's basically the same thing
StringBuffer and StringBuilder do: allocate new storage, copy the
existing data over.
I am thinking of an ArrayList<char[]>. As you run out of space to
append chars, you create another char[8096], and tack it on the end of
the ArrayList.
Ah, i thought you meant that the ArrayList would hold all the individual
things appended. So doing:
RoedyBuffer buf = new RoedyBuffer();
buf.append("Hello ");
buf.append(someExpression);
buf.append(" world!");
Would leave you with an ArrayList like:
["Hello ", someExpression.toString(), " world!"]
Building this list would involve no copying of characters at all, beyond
that involved in the toString calls. The only copying done would be at the
end, where the number of characters copied would be exactly the length of
the final string. It doesn't get any better than that!
The list would of course be bigger than in your scheme, but i suspect
there would be a net saving. Plus, it avoids wasting space when the final
string is small.
LinkedList might be better than ArrayList, as it doesn't do any copying,
although it uses about five times more memory per element than the
ArrayList. You could use a BlockList (which you'd have to write - a
linked-list of fixed-size blocks), which would give you memory efficiency
and no copying, with (1) appending and O(n) iteration.
Oh, and you could make it a List<CharSequence>, and only toString things
if they aren't instanceof CharSequence. The main effect of that is that
you can append things like StringBuffers and CharBuffers directly, without
having to toString them.
It would be pretty straightforward for us to all write implementations of
our ideas behind a common interface, and also wrap StringBuilder with it,
then do some micro benchmarking. Anyone interested? I might have a crack
at this on sunday if i'm bored!
tom
--
It's a surprising finding, but that's science all over: the results
are often counterintuitive. And that's exactly why you do scientific
research, to check your assumptions. Otherwise it wouldn't be called
"science", it would be called "assuming", or "guessing", or "making it
up as you go along". -- Ben Goldacre