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: Tue, 12 Jun 2012 16:34:14 -0400 Message-ID: <87haug1d89.fsf@netris.org> References: <87hauku0mb.fsf@fencepost.gnu.org> <873962sbu0.fsf@fencepost.gnu.org> <87y5nuqpii.fsf@fencepost.gnu.org> <871ulmqbhj.fsf@fencepost.gnu.org> <87pq951k80.fsf@netris.org> <87mx48ooua.fsf@fencepost.gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: dough.gmane.org 1339533389 11762 80.91.229.3 (12 Jun 2012 20:36:29 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Tue, 12 Jun 2012 20:36:29 +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 22:36:28 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 1SeXpB-0000M8-NP for guile-devel@m.gmane.org; Tue, 12 Jun 2012 22:36:25 +0200 Original-Received: from localhost ([::1]:54601 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SeXpB-0007EK-In for guile-devel@m.gmane.org; Tue, 12 Jun 2012 16:36:25 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:33385) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SeXp8-0007ED-OA for guile-devel@gnu.org; Tue, 12 Jun 2012 16:36:24 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SeXp6-0000HN-KT for guile-devel@gnu.org; Tue, 12 Jun 2012 16:36:22 -0400 Original-Received: from world.peace.net ([96.39.62.75]:60352) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SeXp6-0000H4-Ef; Tue, 12 Jun 2012 16:36:20 -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 1SeXow-0003Xa-DC; Tue, 12 Jun 2012 16:36:10 -0400 In-Reply-To: <87mx48ooua.fsf@fencepost.gnu.org> (David Kastrup's message of "Tue, 12 Jun 2012 11:34:53 +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:14609 Archived-At: --=-=-= Content-Type: text/plain Hi David, David Kastrup writes: > Mark H Weaver writes: >> 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. > > I have a really hard time swallowing an efficiency argument for Scheme > that is weak enough in comparison with the associated drawbacks not to > find consideration in the C++ standard template library. C++, like Scheme, already supports fixed-size vectors in the core language, so it would be redundant to include them in a library. > What kind of performance gains are we talking about in a typical > vector-heavy application? If C++ supported _only_ resizable vectors, such that there was no way to avoid the additional level of pointer indirection, and all derived data structures had to be built upon these doubly-indirected vectors, then I'd expect that the efficiency impact would be quite significant in both time and space. I acknowledge that the added cost of resizable vectors would not be noticable in the current implementation of Guile, that might very well change in a few years when we have native compilation. Therefore, I continue to believe that our primitive vector type should be fixed-size. On the other hand, I agree that Guile needs a more extensive library of data structures (including resizable vectors) out of the box. I've attached a preliminary implementation of resizable vectors. Hopefully it works on Guile 1.8 as well, though I haven't tested that. Comments and suggestions welcome. Best, Mark --=-=-= Content-Type: text/plain Content-Disposition: inline; filename=growable-vector.scm Content-Description: Preliminary growable vector implementation (define-module (growable-vector) #:use-module (srfi srfi-9) #:use-module (srfi srfi-9 gnu) #:export (growable-vector make-growable-vector growable-vector-ref growable-vector-set! growable-vector-resize! list->growable-vector growable-vector->list)) (define-record-type (%make-growable-vector length vector) growable-vector? (length growable-vector-length %set-growable-vector-length!) (vector growable-vector-vector %set-growable-vector-vector!)) (define (alloc-size len) (expt 2 (integer-length (- len 1)))) (define (make-growable-vector len . maybe-init) (let ((v (apply make-vector (alloc-size len) maybe-init))) (%make-growable-vector len v))) (define (list->growable-vector lst) (let* ((len (length lst)) (v (make-vector (alloc-size len)))) (do ((i 0 (+ i 1)) (lst lst (cdr lst))) ((null? lst)) (vector-set! v i (car lst))) (%make-growable-vector len v))) (define (growable-vector->list gv) (let ((len (growable-vector-length gv)) (v (growable-vector-vector gv))) (do ((i (- len 1) (- i 1)) (lst '() (cons (vector-ref v i) lst))) ((negative? i) lst)))) (define (growable-vector . elems) (list->growable-vector elems)) (define (growable-vector-ref gv idx) (if (< -1 idx (growable-vector-length gv)) (vector-ref (growable-vector-vector gv) idx) (error "growable-vector-ref: index out of range" idx gv))) (define (growable-vector-set! gv idx val) (if (< -1 idx (growable-vector-length gv)) (vector-set! (growable-vector-vector gv) idx val) (error "growable-vector-set!: index out of range" idx gv))) (define (growable-vector-resize! gv new-len) (let* ((old-len (growable-vector-length gv)) (old-v (growable-vector-vector gv)) (old-alloc (vector-length old-v)) (new-alloc (alloc-size new-len))) (if (not (= old-alloc new-alloc)) (let ((new-v (make-vector new-alloc))) (vector-move-left! old-v 0 (min old-len new-len) new-v 0) (%set-growable-vector-vector! gv new-v))) (%set-growable-vector-length! gv new-len))) (set-record-type-printer! (lambda (gv port) (format port "#" (growable-vector->list gv)))) --=-=-=--