From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Daniel Hartwig Newsgroups: gmane.lisp.guile.devel Subject: Re: Growable arrays? Date: Mon, 11 Jun 2012 13:00:55 +0800 Message-ID: References: <87hauku0mb.fsf@fencepost.gnu.org> <873962sbu0.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 1339390868 4941 80.91.229.3 (11 Jun 2012 05:01:08 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 11 Jun 2012 05:01:08 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Jun 11 07:01:07 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 1SdwkS-0002nh-3p for guile-devel@m.gmane.org; Mon, 11 Jun 2012 07:01:04 +0200 Original-Received: from localhost ([::1]:48591 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SdwkP-00052A-NS for guile-devel@m.gmane.org; Mon, 11 Jun 2012 01:01:01 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:60017) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SdwkN-000524-I4 for guile-devel@gnu.org; Mon, 11 Jun 2012 01:01:00 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SdwkL-0006iO-NW for guile-devel@gnu.org; Mon, 11 Jun 2012 01:00:59 -0400 Original-Received: from mail-gg0-f169.google.com ([209.85.161.169]:52045) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SdwkL-0006iD-Gk for guile-devel@gnu.org; Mon, 11 Jun 2012 01:00:57 -0400 Original-Received: by ggm4 with SMTP id 4so2604505ggm.0 for ; Sun, 10 Jun 2012 22:00:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; bh=Ebam+ixAL6YmLodKF7k/y+V7HQ6ZGiZSWQ9Zy6/GjKg=; b=mct/CV6EwrWGV5tiSb/V6IIG08rL4tTmcuGDtU4nHJ5jBuPtghv0SAQBYYSA9pkyt8 yWrgUahqNgu5QFJS3Fto5tE/R6UkOp7ox5VaPKCb1neoHvQqsPZTdNwLKHHoB66ZXbdp kRLljnXykMgMIUUP7FXZ7E0w7m5/WF6LN2/dQeVEAE5UEmBKyz94I7zIBq+i6NisE9tR RaVK2vQdtOxYsNNENdHYdatqMwqBqav9nL4MduJSuXfIHhIFeaLVZgbvsj2pS1yA5q9a 8+RI2moA4XcWLUbHIexQiSFdCfvmBdRJ1/42Oe3MKVPU6r3Gu08jexMnwsFNdxK6hDs0 wplA== Original-Received: by 10.50.104.167 with SMTP id gf7mr5640142igb.38.1339390855392; Sun, 10 Jun 2012 22:00:55 -0700 (PDT) Original-Received: by 10.231.206.198 with HTTP; Sun, 10 Jun 2012 22:00:55 -0700 (PDT) In-Reply-To: <873962sbu0.fsf@fencepost.gnu.org> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 209.85.161.169 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:14577 Archived-At: On 11 June 2012 12:37, David Kastrup wrote: > What is a vlist? vlist is a data type introduced around guile 2.0. You will find it documented in the Guile Reference under Compound Data Types. They are growable and provide vector-like access performances and memory locality. >>> Now it would be possible when the type lattice gets extended to store >>> the new entries in a hashtable and go from there. >> >> Why not use a hash for everything? =C2=A0Unless your initial lattice is >> very large there would be relatively small loss in performance. > > About double the memory impact (vector->1 cell, hash table->1 cell per > hash bucket+1 additional cons cell per element) and much slower copying. > And quite slower access. > With these concerns your only options are really vlist or implementing growable vector. >>> =C2=A0Or put them into a >>> list, and reallocate on first access beyond the existing element. =C2= =A0That >>> seems rather contorted. >> >> You mean =E2=80=9Cput them into a /vector/=E2=80=9D? > > No, since a vector can't be grown. =C2=A0This would basically switch the = data > structure between "write" and "read" mode, where "write mode" grows the > list of additions, and "read mode" accesses the vector. =C2=A0Switching f= rom > write to read entails creating a newly allocated vector and copying the > new additions from the list as well as the old vector into it. I see, that is rather contorted :-)