attempt at array cleanup

[Daniel Llorens]

Hello,

a few weeks ago, a few bugs and some peculiar performance behavior prompted me 
to start looking at the array code in Guile.

I have put what I've done on branch ra0 here:

https://gitorious.org/guile-stable-2-0-array-cleanup/guile-stable-2-0-array-cleanup/commits/ra0

This is ~50 commits on top of stable-2.0.

I'm doing a few different things in these patches.

-----------------------------
A. The following bugs are fixed, compared with stable-2.0.

A1. strict flag for array-contents doesn't work properly.

In stable-2.0:

(define (every-two x) (make-shared-array x (lambda (i) (list (* i 2))) 2))
(define a (every-two #f64(1 2 3 4)))
(array-contents a #t)
=> #f64(1.0 3.0)

This should be #f.

A2. transpose-array doesn't work on 0-rank arrays.

In stable-2.0:

(transpose-array #0(99))
=> bad argument list

This should be #0(99).

A3. bad access with array ops when the array is empty but the last axis is not.

In stable-2.0:

(array-index-map! (make-typed-array 'f64 0 0 2) (const 0))
=> value out of range
(array-index-map! (make-typed-array #t 0 0 2) (const 0))
=> segfault/nop, according to luck (this is a second bug, friends with the 
first).

Both should be nops.

-----------------------------
B. Implementation changes.

There are (loosely speaking) 4 types in Guile that can be used as array roots: 
bytevectors, bitvectors, strings and vectors. However, of these, bitvectors and 
vectors also accept array arguments, which results in a lot of back and forth 
between the array procedures and the bitvector and vector procedures. Following 
the 1st column of 
http://lists.gnu.org/archive/html/guile-devel/2013-04/msg00176.html, 
vector-ref/set!/length and uniform-vector-ref/set!/length are no longer type 
generic (they don't accept objects with the Guile array tag).

This removes some logical errors like (vector-ref address@hidden(1 2 3) 1) => 
2. There was some discussion in that thread, and it would be good to have the 
matter settled either way.

-----------------------------
C. Performance.

I don't store the array in the array handle, but the root instead. This removes 
a level of indirection where array-ref/set! had to go first through the array 
'implementation' to get to the root's -ref function. Now it goes there 
directly. I've also fixed a number of cases where the array handle procedures 
were used even on an object that was known to have the array tag, some 
redundant checks, etc.

I have rewritten scm_ramapc (used by array-map!, array-for-each, array-copy!). 
The previous version attempt full unrolling, and if it failed, it only unrolled 
the last axis. The new version is simpler and may unroll any number of axes 
from the end, so e.g. the last one, the last two, etc. This gives a big speed 
up in some cases. Obvious next steps would be 1) to grade the axes by stride, 
to allow unrolling from other than the last axis; and 2) to do all type 
dispatch outside the loops. This would bloat array-map.c though.

I have been tracking a small benchmark, which is attached at the end.

-----------------------------
D. Test cases.

I've added test cases for the array functions, beyond the bugs above. These are 
all in test-suite/tests/ramap.test. There're some other tests. All the tests in 
stable-2.0 pass unchanged.


-----------------------------
E. Unfixed bugs and new.

In stable-2.0, this fails at the REPL:

scheme@(guile-user)> address@hidden(#\a #\b)
While compiling expression:
ERROR: Wrong type (expecting uniform array): address@hidden(#\a #\b)

The error is in uniform-array->bytevector: CHAR arrays don't have an 'elements' 
pointer.

In the ra0 branch, that still fails, and this also fails:

scheme@(guile-user)> address@hidden(#t #t)
While compiling expression:
ERROR: In procedure uniform-array->bytevector: Wrong type (expecting uniform 
contiguous array): address@hidden(#t #t)

In both stable-2.0 and ra0,

(bitvector? (make-typed-array 'b 10))
=> #f

This is different from what happens with other types, where make-typed-array 
always tries to return the root (not sure I agree with this, but at least is 
semi-consistent). Maybe the compiler should use the actual array procedures 
here instead of uniform-array->bytevector, since those are safe wrt 'arrayness'.

Regards,

        Daniel


-----------------------------
The benchmark. I'd listen to recommendations on proper benchmarking setups. I 
hope it's ok to post the figure here; the abscissas are commits between 
stable-2.0 and ra0.
--%-------

(define-syntax time
  (syntax-rules ()
    ((_ e0 ...)
      (let ((start (tms:clock (times))))
        e0 ...
        (exact->inexact (/ (- (tms:clock (times)) start)
                           internal-time-units-per-second))))))

(define-syntax repeat
  (syntax-rules ()
    ((_ n e0 ...) (do ((i 0 (+ i 1))) ((= i n)) e0 ...))))

(define (vector-index-map-1! q f)
  (let ((n (vector-length q)))
    (do ((i 0 (+ i 1))) ((= i n))
      (vector-set! q i (f i)))))

(define (array-index-map-1! q f)
  (let ((n (array-length q)))
    (do ((i 0 (+ i 1))) ((= i n))
      (array-set! q (f i) i))))

(define (array-index-map-2! q f)
  (let* ((n (array-dimensions q))
         (n0 (car n))
         (n1 (cadr n)))
    (do ((i 0 (+ i 1))) ((= i n0))
      (do ((j 0 (+ j 1))) ((= j n1))
        (array-set! q (f i j) i j)))))

(define a (make-array 0. 100000 10))
(define b (make-array 0. 100000 10))
(define c (make-array *unspecified* 100000 10))
(define d (transpose-array (make-array *unspecified* 10 100000) 1 0))

(define aa (make-typed-array 'a *unspecified* 1000000 10))

(define s "1234567890")
(define t (make-shared-array s (lambda (i j) (list j)) 1000000 10))
(define x (make-typed-array 'a *unspecified* 1000000 10))
(define y (make-typed-array 'a *unspecified* 1000000 10))

(define i (make-typed-array #t *unspecified* 1000000))
(define j (make-typed-array #t *unspecified* 1000000 10))
(define k (make-vector 1000000 *unspecified*))

(define u #2((1 2 3) (4 5 6) (7 8 9)))
(define v (make-shared-array u (lambda (i j k) (list j k)) 1000000 3 3))
(define w (make-array 0 1000000 3 3))

(define o (make-shared-array #0(99) (lambda x '()) 2000 2000 10))
(define p (make-array 0 2000 2000 10))

(define a0 (make-array 1. 1000000 100))
(define b0 (make-array *unspecified* 1000000 100))
(define c0 (transpose-array (make-array *unspecified* 100 1000000) 1 0))

(define a1 (make-array 1. 100 1000000))
(define b1 (make-array *unspecified* 100 1000000))
(define c1 (transpose-array (make-array *unspecified* 1000000 100) 1 0))

(define out (string-append (cadr (program-arguments)) ".bench"))
(define (wout name t) (format #t "~a ~a\n" name t))
(with-output-to-file out
  (lambda ()
    (wout "map0" (time (repeat 20 (array-map! c (const 0.)))))
    (wout "map1a" (time (repeat 20 (array-map! c (lambda (x) x) a))))
    (wout "map1b" (time (repeat 20 (array-map! c (lambda (x) x) d))))
    (wout "map2" (time (repeat 5 (array-map! c (lambda (a b) (+ a b)) a b))))

    (wout "fill-char1" (time (repeat 3 (array-fill! aa #\v))))

    (wout "cp-char2a" (time (repeat 3 (array-copy! t x))))
    (wout "cp-char2b" (time (repeat 3 (array-copy! x y))))

    (wout "aim1" (time (repeat 20 (array-index-map! i (lambda (i) i)))))
    (wout "aim2" (time (repeat 2 (array-index-map! j (lambda (i j) i)))))
    (wout "vset1" (time (repeat 30 (vector-index-map-1! k (lambda (i) i)))))
    (wout "aset1" (time (repeat 10 (array-index-map-1! i (lambda (i) i)))))
    (wout "aset2" (time (repeat 1 (array-index-map-2! j (lambda (i j) i)))))

    (wout "cp3a" (time (repeat 30 (array-copy! v w))))
    (wout "cp3b" (time (repeat 30 (array-copy! o p))))

    (wout "cp2a" (time (repeat 10 (array-copy! a0 b0))))
    (wout "cp2b" (time (repeat 3 (array-copy! a0 c0))))

    (wout "cp2c" (time (repeat 10 (array-copy! a1 b1))))
    (wout "cp2d" (time (repeat 1 (array-copy! a1 c1))))))

bench.pdf
Description: Adobe PDF document