<br><br><div class="gmail_quote">On Tue, Dec 1, 2009 at 2:16 AM, Martin Buchholz <span dir="ltr"><<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left:1px solid rgb(204, 204, 204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex">

<div>On Thu, Nov 26, 2009 at 00:57, Goktug Gokdogan <<a href="mailto:gokdogan@gmail.com" target="_blank">gokdogan@gmail.com</a>> wrote:<br>
> I think, we can overcome the slowdown. The point of my prototype is to check<br>
> the general performance characteristics. Slowdown is more likely due to the<br>
> poorly optimized extra method call to keep all logic in one place. Normally<br>
> the gap buffer algorithm should add only one comparison overhead to the<br>
> common case which will not to be observable in benchmarks.<br>
<br>
</div>I am coming to like the gap buffer idea.<br>
<br>
You can optimize for append mode - append methods do not have to<br>
check for the existence or length of an internal gap.<br>
<br>
An extra comparison overhead is likely to be cheap, but it is nevertheless<br>
likely to be a measurable slowdown.<br>
But as I said, it more and more seems to me the right thing to do.<br>
<br>
If done right, StringBuilder can start to strongly resemble an Emacs buffer,<br>
and be useful for largish amounts of data with internal modifications.<br>
<div><br>
> I have previously thought about implementing a similar behavior in other<br>
> array-based growing structures, but it is not worth it. You can easily use<br>
> your previous data structures for pre-appending algorithms - just by<br>
> appending to end and iterating from reverse. But you can't do that in a<br>
> StringBuilder because StringBuilder itself is the composed data. So, in my<br>
> opinion, ArrayList is not a good analogy for this case.<br>
> StringBuilder, as its name suggests, is for building strings and building<br>
> string by appending to end is only one of the ways of doing it.<br>
> I think we should go for this if we can do it without an observable<br>
> slowdown.<br>
<br>
</div>I didn't understand this argument. StringBuilder and ArrayList still<br>
seem to me conceptually similar.<br><font class="Apple-style-span" color="#888888"><br></font></blockquote><blockquote class="gmail_quote" style="border-left:1px solid rgb(204, 204, 204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex">
<font color="#888888">
Martin<br>
</font><div><div></div><div><br></div></div></blockquote><div><br>Let me try to explain my argument in another way. <br><br>StringBuilder, similar to the other builder pattern implementations, is for constructing an object, not to collect some data. When append/insert/delete etc. called on a StringBuilder object, the goal is to shape the final state of the resulting String. At the end, you call toString method and you are done.</div>
<div>But ArrayList is more flexible in a way that you are able to reinterpret the result. For example, you can iterate the items in reverse order or skip some of them etc.. So, with this point of view, I believe that StringBuilder and ArrayList are conceptually different. </div>
<div><br></div><div>While building a String with StringBuilder, as it is the builder class for String, I expect it to provide good performance for different building scenarios. If I was designing it in the first place, I would start with an implementation that performs well in general (e.g. gap buffer), then I would check the performance for the common case (ie. appending to end) . If it does not perform well and can not be optimized, then I would consider adding another builder class to API that performs well on the common case before replacing the original. </div>
<div>But in our case, as the previous codes already depends on the current performance characteristics of StringBuilder, I totally agree that we are good to replace it, iff it still performs as good as the previous one. This is why I suggested the change in the first place.    </div>
<div><br></div><div><span class="Apple-style-span" style="color: rgb(153, 153, 153); ">Goktug.</span></div><div><br></div><blockquote class="gmail_quote" style="border-left:1px solid rgb(204, 204, 204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex">
<div><div>
<br>
><br>
> On Thu, Nov 26, 2009 at 1:02 AM, Martin Buchholz <<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>><br>
> wrote:<br>
>><br>
>> On Wed, Nov 25, 2009 at 21:24, Martin Buchholz <<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>><br>
>> wrote:<br>
>> > On Mon, Nov 23, 2009 at 22:51, Goktug Gokdogan <<a href="mailto:gokdogan@gmail.com" target="_blank">gokdogan@gmail.com</a>><br>
>> > wrote:<br>
>> >> Nobody is interested or everybody is busy?<br>
>> ><br>
>> > I think there's a place for a StringBuilder-like<br>
>> > abstraction that uses a gap buffer,<br>
>> > but it shouldn't replace StringBuilder.<br>
>><br>
>> Let me qualify that.<br>
>><br>
>> It is hard to sell the small slowdown in the common case<br>
>> to make other (rare?) operations much faster.<br>
>> ArrayList should have been implemented to allow<br>
>> O(1) insert at both ends, like ArrayDeque,<br>
>> but it is hard to persuade the maintainers<br>
>> that such a change is worth making today,<br>
>> when the benchmarks all exercise only the common case.<br>
>> Similarily for a hypothetical GapArrayList.<br>
>> On the other hand, on modern cpus<br>
>> arithmetic is ever closer to being "free",<br>
>> so it is easier to justify the extra computation.<br>
>><br>
>> Martin<br>
><br>
><br>
</div></div></blockquote></div><br>