From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.devel Subject: Re: Growable arrays? Date: Mon, 11 Jun 2012 19:50:55 -0400 Message-ID: <87pq951k80.fsf@netris.org> References: <87hauku0mb.fsf@fencepost.gnu.org> <873962sbu0.fsf@fencepost.gnu.org> <87y5nuqpii.fsf@fencepost.gnu.org> <871ulmqbhj.fsf@fencepost.gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: dough.gmane.org 1339458804 4330 80.91.229.3 (11 Jun 2012 23:53:24 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 11 Jun 2012 23:53:24 +0000 (UTC) Cc: guile-devel@gnu.org To: David Kastrup Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Tue Jun 12 01:53:22 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 1SeEQ8-00032i-Qy for guile-devel@m.gmane.org; Tue, 12 Jun 2012 01:53:16 +0200 Original-Received: from localhost ([::1]:38703 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SeEQ8-0008JW-JK for guile-devel@m.gmane.org; Mon, 11 Jun 2012 19:53:16 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:41601) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SeEQ5-0008JN-Is for guile-devel@gnu.org; Mon, 11 Jun 2012 19:53:15 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SeEQ3-0001ed-M8 for guile-devel@gnu.org; Mon, 11 Jun 2012 19:53:13 -0400 Original-Received: from world.peace.net ([96.39.62.75]:59097) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SeEQ3-0001b6-Hf; Mon, 11 Jun 2012 19:53:11 -0400 Original-Received: from 209-6-91-212.c3-0.smr-ubr1.sbo-smr.ma.cable.rcn.com ([209.6.91.212] helo=yeeloong) by world.peace.net with esmtpsa (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from ) id 1SeEPj-0000My-0M; Mon, 11 Jun 2012 19:52:51 -0400 In-Reply-To: <871ulmqbhj.fsf@fencepost.gnu.org> (David Kastrup's message of "Mon, 11 Jun 2012 14:28:08 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.92 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 96.39.62.75 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:14606 Archived-At: Hi David, David Kastrup writes: > I don't think I need yet another data structure deficient in some > respects. We have vectors that can't grow, hashtables that can grow but > only index through a hash function, vlists that can grow but have > immutable content... [...] > Why not just have a superset without arbitrary restriction and implement > the other structures based on that? Then each one just needs to enforce > its personal restrictions in its accessor functions, and otherwise just > use what is there in the general mechanism. Simpler data structures can usually be implemented with less memory, shorter code sequences with fewer conditional branches and less space in the instruction cache, which in turn means they can be implemented more efficiently. Therefore, to allow efficient compilation, primitive data structures should be very simple, with more complex structures built on simpler ones instead of the other way around. For example, consider resizable vectors vs fixed-size vectors. A fixed-size vector can be represented as a single memory block that contains both the length and the elements together. A resizable vector requires an additional level of pointer indirection, which inevitably means slower accesses and greater code size. Furthermore, fixed-size vectors allow the possibility of compiling in an unsafe mode where out-of-bounds checks can be skipped. Even if one is willing to pay the price of a relatively heavyweight primitive data structure, Lua's tables are not always a good fit. What if you need a table keyed on large, sparsely distributed integer keys? What if you need a linked list with O(1) insertions? What if you need a doubly-linked list with O(1) deletions? Data structure design involves many tradeoffs, and unfortunately there is no complex "one-size-fits-all" data structure that is a good universal primitive upon which to build all others. Regards, Mark