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 19:49:10 +0200 Organization: Organization?!? Message-ID: <87395xvl61.fsf@fencepost.gnu.org> References: <87hauku0mb.fsf@fencepost.gnu.org> <87sjdyyncv.fsf@netris.org> <87vciuuf12.fsf@fencepost.gnu.org> <87k3z9vrds.fsf@fencepost.gnu.org> <87fw9xvmq4.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 1339696184 20957 80.91.229.3 (14 Jun 2012 17:49:44 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 14 Jun 2012 17:49:44 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Thu Jun 14 19:49:44 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 1SfEAw-0001Dk-60 for guile-devel@m.gmane.org; Thu, 14 Jun 2012 19:49:42 +0200 Original-Received: from localhost ([::1]:34746 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SfEAw-0006Xr-6p for guile-devel@m.gmane.org; Thu, 14 Jun 2012 13:49:42 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:59289) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SfEAp-0006XZ-9F for guile-devel@gnu.org; Thu, 14 Jun 2012 13:49:41 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SfEAj-0007as-2s for guile-devel@gnu.org; Thu, 14 Jun 2012 13:49:34 -0400 Original-Received: from plane.gmane.org ([80.91.229.3]:40608) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SfEAi-0007aa-S0 for guile-devel@gnu.org; Thu, 14 Jun 2012 13:49:28 -0400 Original-Received: from list by plane.gmane.org with local (Exim 4.69) (envelope-from ) id 1SfEAd-0000AF-M7 for guile-devel@gnu.org; Thu, 14 Jun 2012 19:49:23 +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 19:49:23 +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 19:49:23 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 40 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:49E8LX4vWAsA6DFQs1xLLQ4MDZI= 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:14626 Archived-At: Daniel Hartwig writes: > On 15 June 2012 01:15, David Kastrup wrote: >> Daniel Hartwig writes: >>> What is this half-in-place algorithm that makes this efficient?  If >>> the table is to remain balanced, all items should be rehashed and >>> reallocated to a new bucket and there is no correlation between an >>> items old and new buckets (hash). >> >> Huh?  Hashing computes a hash value, and the bucket is determined by >> hash % vectorsize.  Double the vector size, and the new bucket locations >> are at bucket and bucket+vectorsize, so you need to coalesce the bucket >> at bucket into the buckets at bucket and bucket+vectorsize. >> >> Why would there be no correlation between old and new buckets when they >> are calculated based on the same hash code? > … > > I see. So starting from the old tail there is little contention for > the new buckets. This seems obvious now in hindsight :-) > > Regarding the data type for your application, this is something which > needs to be accessible from the c side also? No. And we have significant amount of C code of our own, so adding stuff here is not a problem. And we are talking about rather performance-critical stuff. For one thing, it feels ridiculous having to implement a rather basic data type oneself. For another, growing a memory area can sometimes be done in-place when one talks nicely to the garbage management (allocate from the free space following the resizable vector preferably backwards, so that resizing may still be opportunistically possible. Or allocate the vector itself backwards and try growing it backwards in memory). There are various strategies that might be more efficient than the "naive relocator" but that can't be done without actually meddling with Guile internals. -- David Kastrup