From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Andy Wingo Newsgroups: gmane.lisp.guile.devel Subject: Re: O(1) accessors for UTF-8 backed strings Date: Wed, 30 Mar 2011 11:20:52 +0200 Message-ID: References: <486722.32491.qm@web37905.mail.mud.yahoo.com> <87aah1qoc4.fsf@netris.org> <87zkp1p84m.fsf@netris.org> <87ei6csb85.fsf@gnu.org> <87tyf7oebc.fsf_-_@netris.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: dough.gmane.org 1301483676 14601 80.91.229.12 (30 Mar 2011 11:14:36 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Wed, 30 Mar 2011 11:14:36 +0000 (UTC) Cc: Ludovic =?utf-8?Q?Court=C3=A8s?= , guile-devel@gnu.org To: Mark H Weaver Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Wed Mar 30 13:14:31 2011 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Q4tM6-0004qd-DD for guile-devel@m.gmane.org; Wed, 30 Mar 2011 13:14:30 +0200 Original-Received: from localhost ([127.0.0.1]:40302 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Q4tM5-0000Gv-IA for guile-devel@m.gmane.org; Wed, 30 Mar 2011 07:14:29 -0400 Original-Received: from [140.186.70.92] (port=34213 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Q4tLQ-0008Mx-Cg for guile-devel@gnu.org; Wed, 30 Mar 2011 07:13:50 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Q4tLP-0003D7-BM for guile-devel@gnu.org; Wed, 30 Mar 2011 07:13:48 -0400 Original-Received: from a-pb-sasl-sd.pobox.com ([64.74.157.62]:51877 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Q4tLP-0003Cx-98; Wed, 30 Mar 2011 07:13:47 -0400 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id 8A5E2465D; Wed, 30 Mar 2011 07:15:35 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; s=sasl; bh=+Ud85a7KcPEG NE3I0VLN6ZqlMiE=; b=qYFH58ypBAFUq6DIoDIHMCA1EtZyvBmvqoV43IokqmnO VV5SWYJrw3OunUBo/Ae9ryr7D2xZoZeWYoWi3HDvL5cCF+52zsGhNd9b6PcYB3bA VlzGRF32PpdCpQ4Nx7U41vITAefVi0bN3EsB1JrdkNmA6PnpsivA2iLXENeuzUw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; q=dns; s=sasl; b=syCkrr 2UIL4MAOiv6UW+mMwO0cTEO+aTN98o3suSqEtgbvL0NimlQGnE1PTzVuA1aMsc1W DBSsJilOgmc60BjLPHi9fWcsKY/ykss4iPT9AH1pborzJYxLHYTdFEcteHfWg+r6 yHIhRPxY4oWFjRziC741Nzbyw28h9KtI3+NC0= Original-Received: from a-pb-sasl-sd.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id 6788A465B; Wed, 30 Mar 2011 07:15:33 -0400 (EDT) Original-Received: from unquote.localdomain (unknown [90.164.198.39]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTPSA id 6D2364659; Wed, 30 Mar 2011 07:15:30 -0400 (EDT) In-Reply-To: <87tyf7oebc.fsf_-_@netris.org> (Mark H. Weaver's message of "Sat, 12 Mar 2011 23:05:27 -0500") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux) X-Pobox-Relay-ID: 07883742-5ABF-11E0-9E45-E8AB60295C12-02397024!a-pb-sasl-sd.pobox.com X-detected-operating-system: by eggs.gnu.org: Solaris 10 (beta) X-Received-From: 64.74.157.62 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:12082 Archived-At: On Sun 13 Mar 2011 05:05, Mark H Weaver writes: > ludo@gnu.org (Ludovic Court=C3=A8s) writes: >> I also think strings should remain what they currently are, with O(1) >> random access. > > I just realized that it is possible to implement O(1) accessors for > UTF-8 backed strings. If we switch to UTF-8, I like this proposal, generally. It would be good if it continued to support cheap, shared substrings, but without the mutexen we have now. Perhaps it would also be good to do away with stringbuf objects entirely; dunno. O(log N) accessors would also fine be with me, e.g. via skip lists or tries or something. A tricky problem! Regards, Andy --=20 http://wingolog.org/