Gap Buffer based AbstractStringBuilder implementation

[Goktug Gokdogan]

Nobody is interested or everybody is busy?

On Tue, Nov 17, 2009 at 3:16 AM, Goktug Gokdogan <gokdogan at gmail.com> wrote:

> 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/20091124/bcfbbecf/attachment.html>