From: Andy Wingo <wingo@pobox.com>
To: Mark H Weaver <mhw@netris.org>
Cc: "Ludovic Courtès" <ludo@gnu.org>, guile-devel@gnu.org
Subject: Re: Using libunistring for string comparisons et al
Date: Wed, 30 Mar 2011 11:33:44 +0200 [thread overview]
Message-ID: <m3bp0t54w7.fsf@unquote.localdomain> (raw)
In-Reply-To: <87sjuokniq.fsf@netris.org> (Mark H. Weaver's message of "Tue, 15 Mar 2011 18:49:17 -0400")
On Tue 15 Mar 2011 23:49, Mark H Weaver <mhw@netris.org> 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
otherwise).
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.
Andy
--
http://wingolog.org/
next prev parent reply other threads:[~2011-03-30 9:33 UTC|newest]
Thread overview: 48+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-03-12 21:28 Using libunistring for string comparisons et al Mike Gran
2011-03-15 17:20 ` Mark H Weaver
2011-03-15 20:39 ` Mike Gran
2011-03-15 22:49 ` Mark H Weaver
2011-03-16 0:01 ` Mike Gran
2011-03-16 1:12 ` Mark H Weaver
2011-03-16 11:26 ` Ludovic Courtès
2011-03-17 15:38 ` Mark H Weaver
2011-03-17 15:56 ` Ludovic Courtès
2011-03-17 17:58 ` Mark H Weaver
2011-03-18 0:10 ` Thien-Thi Nguyen
2011-03-18 1:38 ` Mark H Weaver
2011-03-18 8:46 ` Thien-Thi Nguyen
2011-03-18 12:05 ` Mark H Weaver
2011-03-20 22:12 ` Ludovic Courtès
2011-03-30 10:14 ` Andy Wingo
2011-03-17 21:47 ` Ludovic Courtès
2011-03-19 12:31 ` Andy Wingo
2011-03-19 14:06 ` Mark H Weaver
2011-03-19 14:53 ` Noah Lavine
2011-03-19 15:49 ` Mark H Weaver
2011-03-19 15:08 ` Andy Wingo
2011-03-19 19:43 ` Mark H Weaver
2011-03-19 16:37 ` Mark H Weaver
2011-03-20 21:49 ` Ludovic Courtès
2011-03-30 9:50 ` Andy Wingo
2011-03-29 12:39 ` Peter Brett
2011-03-29 13:35 ` Andy Wingo
2011-03-29 21:15 ` Ludovic Courtès
2011-03-31 14:59 ` Peter Brett
2011-03-31 20:12 ` Ludovic Courtès
2011-03-30 9:33 ` Andy Wingo [this message]
2011-03-16 0:22 ` Alex Shinn
-- strict thread matches above, loose matches on Subject: below --
2011-03-17 18:07 Mike Gran
2011-03-16 15:22 Mike Gran
2011-03-16 16:58 ` Ludovic Courtès
2011-03-16 2:03 Mike Gran
2011-03-16 1:30 Mike Gran
2011-03-11 0:54 uc_tolower (uc_toupper (x)) Mike Gran
2011-03-11 22:33 ` Using libunistring for string comparisons et al Mark H Weaver
2011-03-11 22:36 ` Mark H Weaver
2011-03-11 23:09 ` Mark H Weaver
2011-03-12 13:46 ` Ludovic Courtès
2011-03-12 17:28 ` Mark H Weaver
2011-03-13 21:30 ` Ludovic Courtès
2011-03-30 9:05 ` Andy Wingo
2011-03-30 9:03 ` Andy Wingo
2011-03-31 14:19 ` Ludovic Courtès
2011-03-12 13:36 ` Ludovic Courtès
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=m3bp0t54w7.fsf@unquote.localdomain \
--to=wingo@pobox.com \
--cc=guile-devel@gnu.org \
--cc=ludo@gnu.org \
--cc=mhw@netris.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).