Re: Growable arrays?

[Mark H Weaver]

Hi David,

David Kastrup <address@hidden> writes:
> Mark H Weaver <address@hidden> 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))))