[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Using libunistring for string comparisons et al

From: Andy Wingo
Subject: Re: Using libunistring for string comparisons et al
Date: Wed, 30 Mar 2011 11:33:44 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux)

On Tue 15 Mar 2011 23:49, Mark H Weaver <address@hidden> writes:

>> Well, we covered O(1) vs O(n).  To make UTF-8 O(1), you need to store
>> additional indexing information of some sort.  There are various schemes,
>> but, depending the the scheme, you lose some of memory advantage of UTF-8
>> vs UTF-32.  You can likely to better than UTF-32, though.
> I would prefer to either let our accessors be O(n), or else to create
> the index lazily, i.e. on the first usage of string-ref or string-set!
> In such a scheme, very few strings would include indices, and thus the
> overhead would be minimal.
> Anyway, the index overhead can be made arbitrarily small by increasing
> the chunk size.  It is a classic time-space trade-off here.  The chunk
> size could be made larger over the years, as usage of string-ref and
> string-set! become less common, and eventually the index stuff could be
> removed entirely.

Though I agre that string-set! should be discouraged -- as Clinger also
thought back in 1984, it seems -- string-ref is still important.  The
only thing that could replace it would be some sort of string cursor /
iteration protocol, and I would prefer for that to be standard (SRFI or

So let's factor string-ref into the "costs" of a potential switch to
UTF-8, be it in space or in time or whatever.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]