From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Thien-Thi Nguyen Newsgroups: gmane.lisp.guile.devel Subject: Re: Growable arrays? Date: Mon, 11 Jun 2012 10:14:00 +0200 Message-ID: <87txyi465z.fsf@gnuvola.org> References: <87hauku0mb.fsf@fencepost.gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: dough.gmane.org 1339402540 13973 80.91.229.3 (11 Jun 2012 08:15:40 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 11 Jun 2012 08:15:40 +0000 (UTC) Cc: guile-devel@gnu.org To: David Kastrup Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Jun 11 10:15:39 2012 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Sdzml-00061O-1u for guile-devel@m.gmane.org; Mon, 11 Jun 2012 10:15:39 +0200 Original-Received: from localhost ([::1]:39084 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Sdzmk-0006y5-HS for guile-devel@m.gmane.org; Mon, 11 Jun 2012 04:15:38 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:58521) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Sdzmh-0006y0-VL for guile-devel@gnu.org; Mon, 11 Jun 2012 04:15:37 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Sdzmb-0001Hw-KG for guile-devel@gnu.org; Mon, 11 Jun 2012 04:15:35 -0400 Original-Received: from smtp209.alice.it ([82.57.200.105]:59230) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SdzmU-0001Gn-A4; Mon, 11 Jun 2012 04:15:22 -0400 Original-Received: from ambire (79.21.51.59) by smtp209.alice.it (8.6.023.02) id 4EF08A631357D6F2; Mon, 11 Jun 2012 10:15:18 +0200 Original-Received: from ttn by ambire with local (Exim 4.72) (envelope-from ) id 1SdzlB-0000fK-AB; Mon, 11 Jun 2012 10:14:01 +0200 In-Reply-To: <87hauku0mb.fsf@fencepost.gnu.org> (David Kastrup's message of "Sat, 09 Jun 2012 14:32:28 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.92 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 82.57.200.105 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:14579 Archived-At: () David Kastrup () Sat, 09 Jun 2012 14:32:28 +0200 Suggestions? Guile-SDL implements (in C) collections of "enums" using both a C array (static, used also for init) and a Scheme hash table for backing store: http://git.savannah.gnu.org/cgit/guile-sdl.git/tree/src/sdlenums.c#n66 This is not dynamic (growable) as you specified, but i figure it might be useful as an example building block. The modifications are straightforward. You would have to add a container for the set of arrays, and two (more) indirections to =E2=80=98lookup=E2=80=99 (lin= e 97), the first to distinguish between integer/otherwise =E2=80=98key=E2=80=99, t= he second to index into the outer container. Alternatively, keep track of collection size and add entries to the hash table under both the user-given key and the monotonic =E2=80=98size - 1=E2=80=99 (two entries). Extremely wasteful spacewise. Less wasteful spacewise but more wasteful timewise would be to combine the above approaches, where the initial (static, before growth) set does not get a double entry, but in turn requires another check (branch) in =E2=80=98lookup=E2=80=99. Actually the cut-off i= ndex need not be the initial set; it need only correspond to the initial array allocation (possibly greater than the initial set). I suspect some of these considerations have gone into the vlist implementation (though not all since IIRC vlists alloc doubling "on overflow"; there is not a single threshold), so another idea is to use that, back-porting as necessary. Tangential: I think vlists should be aggressively exercised, debugged and then back-ported to 1.8 and before. It's a nice self-contained design. This requires a change of policy, though.