On 01/24/2012 04:25 PM, Alex Shinn wrote:
> On Wed, Jan 25, 2012 at 5:45 AM, Per Bothner<per@bothner.com>  wrote:
>>
>> I thinking a simple buffer-gap implementation might be cheap enough
>> that it could serve as the standard implementation of mutable strings.
>> This especially makes sense if an implementation uses a variable-length
>> string representation, like UTF-8 or UTF-16, since in that case you
>> kind of need it anyway.
>
> A gap buffer is a pretty inefficient choice for text buffers.

Certainly if there is lots of random-access insertion and deletion.
But for a simple low-overhead mutable string buffer (just plain
text with no styling, no emacs-style positions, etc) it seems a reasonable
choice.  I'm thinking of something similar to Java's
StringBuilder/StringBuffer
(which don't even use a buffer gap).  Most common uses just append to the
end (which is why even buffer-gap may be overkill), but occasionally
people do an insert/replace/delete.

A big advantage of buffer gap is simplicity and low overhead.  Another
advantage is memory locality - no chasing pointers and tree nodes
all over virtual memory.  Sliding bytes back and forth in an array
is likely to be much cheaper than extra cache misses.

That simplicity and low overhead make buffer gap a plausible implementation
of the basic mutable-string type.  Any more complex data structure and
you want want to use a different representation, which becomes a hassle.
--
	--Per Bothner
per@bothner.com   http://per.bothner.com/

_______________________________________________
Scheme-reports mailing list
Scheme-reports@scheme-reports.org
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports