Gap Buffer based AbstractStringBuilder implementation

[Martin Buchholz]

On Thu, Nov 26, 2009 at 00:57, Goktug Gokdogan <gokdogan at gmail.com> wrote:
> 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 am coming to like the gap buffer idea.

You can optimize for append mode - append methods do not have to
check for the existence or length of an internal gap.

An extra comparison overhead is likely to be cheap, but it is nevertheless
likely to be a measurable slowdown.
But as I said, it more and more seems to me the right thing to do.

If done right, StringBuilder can start to strongly resemble an Emacs buffer,
and be useful for largish amounts of data with internal modifications.

> 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.

I didn't understand this argument. StringBuilder and ArrayList still
seem to me conceptually similar.

Martin


>
> 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
>
>