Hi David, David Kastrup <d...@gnu.org> writes: > Mark H Weaver <m...@netris.org> 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
(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 <growable-vector> (%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! <growable-vector> (lambda (gv port) (format port "#<growable-vector ~S>" (growable-vector->list gv))))