Gap Buffer based AbstractStringBuilder implementation

[Goktug Gokdogan]

I think, we can overcome the slowdown. The point of my prototype is to check
the general performance characteristics. Slowdown is more likely due to the
poorly optimized extra method call to keep all logic in one place. Normally
the gap buffer algorithm should add only one comparison overhead to the
common case which will not to be observable in benchmarks.

I have previously thought about implementing a similar behavior in other
array-based growing structures, but it is not worth it. You can easily use
your previous data structures for pre-appending algorithms - just by
appending to end and iterating from reverse. But you can't do that in a
StringBuilder because StringBuilder itself is the composed data. So, in my
opinion, ArrayList is not a good analogy for this case.

StringBuilder, as its name suggests, is for building strings and building
string by appending to end is only one of the ways of doing it.
I think we should go for this if we can do it without an observable
slowdown.


On Thu, Nov 26, 2009 at 1:02 AM, Martin Buchholz <martinrb at google.com>wrote:

> On Wed, Nov 25, 2009 at 21:24, Martin Buchholz <martinrb at google.com>
> wrote:
> > On Mon, Nov 23, 2009 at 22:51, Goktug Gokdogan <gokdogan at gmail.com>
> wrote:
> >> Nobody is interested or everybody is busy?
> >
> > I think there's a place for a StringBuilder-like
> > abstraction that uses a gap buffer,
> > but it shouldn't replace StringBuilder.
>
> Let me qualify that.
>
> It is hard to sell the small slowdown in the common case
> to make other (rare?) operations much faster.
> ArrayList should have been implemented to allow
> O(1) insert at both ends, like ArrayDeque,
> but it is hard to persuade the maintainers
> that such a change is worth making today,
> when the benchmarks all exercise only the common case.
> Similarily for a hypothetical GapArrayList.
> On the other hand, on modern cpus
> arithmetic is ever closer to being "free",
> so it is easier to justify the extra computation.
>
> Martin
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20091126/97593999/attachment.html>