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 <[email protected]>wrote: > On Wed, Nov 25, 2009 at 21:24, Martin Buchholz <[email protected]> > wrote: > > On Mon, Nov 23, 2009 at 22:51, Goktug Gokdogan <[email protected]> > 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 >
