Scheme language standardization process
On 01/24/2012 04:25 PM, Alex Shinn wrote: > On Wed, Jan 25, 2012 at 5:45 AM, Per Bothner<per@x> 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@x http://per.bothner.com/ _______________________________________________ Scheme-reports mailing list Scheme-reports@x http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports