attempt at array cleanup

attempt at array cleanup

[Daniel Llorens]

[-- Attachment #1: Type: text/plain, Size: 7979 bytes --]


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 #@1(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)> #1a@1(#\a #\b)
While compiling expression:
ERROR: Wrong type (expecting uniform array): #1a@1(#\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)> #1b@1(#t #t)
While compiling expression:
ERROR: In procedure uniform-array->bytevector: Wrong type (expecting uniform contiguous array): #1b@1(#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))))))


[-- Attachment #2: bench.pdf --]
[-- Type: application/pdf, Size: 7627 bytes --]

Re: attempt at array cleanup

[Daniel Llorens]

On May 1, 2013, at 01:10, Daniel Llorens wrote:

> In the ra0 branch, that still fails, and this also fails:
> 
> scheme@(guile-user)> #1b@1(#t #t)
> While compiling expression:
> ERROR: In procedure uniform-array->bytevector: Wrong type (expecting uniform contiguous array): #1b@1(#t #t)

I have now fixed this, and also this bug in stable-2.0:

https://gitorious.org/guile-stable-2-0-array-cleanup/guile-stable-2-0-array-cleanup/commit/0a0818d9bf6086cbaa12c53ee3c14029a3934e7b

A4. Compiler fails with some typed arrays.

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

It should be => #2b((#t #f) (#f #t)).

The bug with char arrays is still unfixed.

Regards

	Daniel

Re: attempt at array cleanup

[Daniel Llorens]

Hello,

I've rebased this branch on top of master. It is at 

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

I had conflicts in about 10 of the 50 patches:

* scm_i_print_bytevector(), that I had rewritten and had changed from stable-2.0 to master.
* uses of SCM_IMP and SCM_NIMP that I had removed, had been removed in parallel in master.
* weak vector fixes in vectors.c.
* context mismatches.

I think I have incorporated the changes coming from master as they were, but I didn't test after each patch so the history may be broken in places. The top of the branch should be good though.

Regards,

  Daniel