From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.lisp.guile.devel Subject: Re: Growable arrays? Date: Thu, 14 Jun 2012 17:34:55 +0200 Organization: Organization?!? Message-ID: <87k3z9vrds.fsf@fencepost.gnu.org> References: <87hauku0mb.fsf@fencepost.gnu.org> <87sjdyyncv.fsf@netris.org> <87vciuuf12.fsf@fencepost.gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: dough.gmane.org 1339688134 16846 80.91.229.3 (14 Jun 2012 15:35:34 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 14 Jun 2012 15:35:34 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Thu Jun 14 17:35:33 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 1SfC56-0000Ul-Gd for guile-devel@m.gmane.org; Thu, 14 Jun 2012 17:35:32 +0200 Original-Received: from localhost ([::1]:38026 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SfC56-0007Ot-Ex for guile-devel@m.gmane.org; Thu, 14 Jun 2012 11:35:32 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:53508) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SfC4y-0007HO-OZ for guile-devel@gnu.org; Thu, 14 Jun 2012 11:35:30 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SfC4u-0006Wo-Nx for guile-devel@gnu.org; Thu, 14 Jun 2012 11:35:24 -0400 Original-Received: from plane.gmane.org ([80.91.229.3]:36136) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SfC4u-0006WV-Hc for guile-devel@gnu.org; Thu, 14 Jun 2012 11:35:20 -0400 Original-Received: from list by plane.gmane.org with local (Exim 4.69) (envelope-from ) id 1SfC4p-0008AV-Jc for guile-devel@gnu.org; Thu, 14 Jun 2012 17:35:15 +0200 Original-Received: from p508eb9b7.dip.t-dialin.net ([80.142.185.183]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 14 Jun 2012 17:35:15 +0200 Original-Received: from dak by p508eb9b7.dip.t-dialin.net with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 14 Jun 2012 17:35:15 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 58 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: p508eb9b7.dip.t-dialin.net X-Face: 2FEFf>]>q>2iw=B6, xrUubRI>pR&Ml9=ao@P@i)L:\urd*t9M~y1^:+Y]'C0~{mAl`oQuAl \!3KEIp?*w`|bL5qr,H)LFO6Q=qx~iH4DN; i"; /yuIsqbLLCh/!U#X[S~(5eZ41to5f%E@'ELIi$t^ Vc\LWP@J5p^rst0+('>Er0=^1{]M9!p?&:\z]|;&=NP3AhB!B_bi^]Pfkw User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.1.50 (gnu/linux) Cancel-Lock: sha1:Z2jvZEl5uo5zUnNgY2nwq86OiiI= X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 80.91.229.3 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:14622 Archived-At: Daniel Hartwig writes: > On 14 June 2012 22:47, David Kastrup wrote: >> Mark H Weaver writes: >> >>> David Kastrup writes: >>>> Scheme/Guile vectors are fixed size.  [...]  It is a bit of a nuisance >>>> that one can grow a hashtable efficiently and on-demand, but not so an >>>> array. >>> >>> Although Scheme vectors should remain fixed-size for reasons I have >>> given elsewhere in this thread, Guile also includes a more complex >>> 'array' type that includes features such as arbitrary rank (i.e. number >>> of dimensions), arbitrary lower bounds (not just 0), and shared views on >>> the same underlying array with arbitrary affine mappings of indices. >>> >>> Guile 'arrays' cannot currently be resized, but I see no good reason for >>> this limitation.  They are already quite complex, and already require a >>> second level of pointer indirection. >>> >>> What do other people think? > > Perhaps drop a basic resizable type in the guile-lib? Any > implementation is going to be less-than-ideal in some situations. The > guile core provides already a solid set of fundamental types which are > very easy to compose to produce *exactly* the type required for any > particular situation. Except when they don't. Which is what started this thread. >> Another complex type, this time with quite more serious memory and >> performance impact, that can't be implemented on top of a simple >> resizable common primitive and has an almost, but not quite, overlapping >> underlying feature set? >> >> It's almost as if you _like_ not being able to reuse code. > > I don't see how either hash table or multi-dimensional array type > could benefit from a shared, resizable primitive – they are quite > different algorithms, and both different again to the basic resizable > vector already discussed. > > It is moot that hash table internally manages a vector and allocates a > /new/ vector when needed. This is not a simple resizing operation. Huh? When resizing a hash table by doubling, you need to recoalesce each bucket to two buckets, one of which is the original. Doubling the size of the underlying vector is a reasonable start to do this operation as a half-in-place rather than a three-address variant. > Are there any data types in the guile core which would benefit from > sharing a resizable vector primitive? Hash tables. Apparently vlists. I am not convinced that this does not make sense for normal and uniform vectors as an option as well. -- David Kastrup