Gap Buffer based AbstractStringBuilder implementation

[Goktug Gokdogan]

Hi.

As you know, java.lang.StringXXXX classes favor insertion to the end in
terms of performance. Adding to beginning or middle of these sequences
causes most of the array to be shifted toward the end every time. Every ones
in a while I end up changing my algorithms those are based on prefixing
strings (ex. building a fully qualified name from class name to root
direction). Sometimes these kind of changes could result in less readable
code. And I should note that, there are lots of developers out there who
does not know the internal details of these classes.

Anyway, this behavior was frustrating me for a while and I decided to
suggest a gap buffer based modification to AbstractStringBuilder to solve
this problem but never had time before to prototype it.

I tested the original StringBuilder against the prototype. Preliminary
results for the duration of 100000 insertions of a short string:

                      Original | Prototype
           append =>     ~33   |   ~34
 insert beginning =>   ~32000  |   ~38
    insert random =>   ~16000  |  ~10000


A negligible overhead appears for appending (which could be avoided with
shortcuts), but lots of performance gain achieved for other cases.
If we handle insertion at zero as a special case in insert method or if we
add an another method like 'prepend', the insertion at beginning will show
exactly same performance characteristics of insertion at the end.

In my opinion, this is a well-worth modification to string building classes.
If anybody agrees on sponsoring, I can tidy up code and contribute to
OpenJDK.

- Goktug


PS: I've used  following code for rough testing:


private static final int LOOP_COUNT = 100000;

public static void main(String[] args) {
long nanoTime = System.nanoTime();
testStandardAppend();
//testAppendBeginning();
//testAppendRandom();
long span = System.nanoTime() - nanoTime;
System.out.println(span / 1000000);
}

private static void testStandardAppend() {
StringBuilder builder = new StringBuilder("initial");
for (int i = 0; i < LOOP_COUNT; i++) {
builder.append("tryouts");
}
}

private static void testAppendBeginning() {
StringBuilder builder = new StringBuilder("initial");
for (int i = 0; i < LOOP_COUNT; i++) {
builder.insert(0, "tryouts");
}
}

private static void testAppendRandom() {
Random random = new Random();
StringBuilder builder = new StringBuilder("initial");
for (int i = 0; i < LOOP_COUNT; i++) {
builder.insert(random.nextInt(builder.length()), "tryouts");
}
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20091117/1e7406c8/attachment.html>