Re: [Sbcl-devel] Optimization of array accesses

[Elliott S. <ell...@gm...>]

Here's a follow up question:

I noticed that simple-vector and an unspecialized simple-array have wildly
different performance. As far as I can tell though, both are unspecialized
with respect to fixnums. I could expect that an unspecialized simple-array
would get worse performance, but I'm not sure why simple-vector is doing so
well when the type won't even let me specify the element-type.

Thanks.

The code, in case you are interested:

(defun dot-sv (a b)
  (declare (type (simple-vector 4) a b))
  (the fixnum (+ (the fixnum (* (the fixnum (svref a 0)) (the fixnum (svref
b 0))))
                 (the fixnum (* (the fixnum (svref a 1)) (the fixnum (svref
b 1))))
                 (the fixnum (* (the fixnum (svref a 2)) (the fixnum (svref
b 2))))
                 (the fixnum (* (the fixnum (svref a 3)) (the fixnum (svref
b 3)))))))

(defun dot-sa (a b)
  (declare (type simple-array a b))
  (the fixnum (+ (the fixnum (* (the fixnum (aref a 0)) (the fixnum (aref b
0))))
                 (the fixnum (* (the fixnum (aref a 1)) (the fixnum (aref b
1))))
                 (the fixnum (* (the fixnum (aref a 2)) (the fixnum (aref b
2))))
                 (the fixnum (* (the fixnum (aref a 3)) (the fixnum (aref b
3)))))))

(defun test-dot-sv-f ()
  (let ((a (vector 1 2 3 4))
        (b (vector 4 3 2 1)))
    (time (loop for i from 1 to 100000000 do (dot-sv-f a b)))))

(defun test-dot-sa-g ()
  (let ((a (make-array '(4) :initial-contents '(1 2 3 4)))
        (b (make-array '(4) :initial-contents '(4 3 2 1))))
    (time (loop for i from 1 to 100000000 do (dot-sa-g a b)))))

On Sun, Apr 3, 2011 at 7:11 PM, Elliott Slaughter <
ell...@gm...> wrote:

> On Sun, Apr 3, 2011 at 10:10 AM, Christophe Rhodes <cs...@ca...>wrote:
>
>> Elliott Slaughter <ell...@gm...> writes:
>>
>> > I'm wondering why in the following code SBCL complains about being
>> unable to
>> > optimize the arithmetic despite my type declarations? I am on 1.0.46 on
>> Mac
>> > OS X (64-bit, threaded).
>> >
>> > The code:
>> >
>> > (declaim (optimize (speed 3) (safety 0)))
>> >
>> > (defun dot-sa (a b)
>> >   (declare (type (simple-array fixnum (4)) a b))
>> >   (+ (* (aref a 0) (aref b 0))
>> >      (* (aref a 1) (aref b 1))
>> >      (* (aref a 2) (aref b 2))
>> >      (* (aref a 3) (aref b 3))))
>>
>> The compiler note that you gave, about generic-* rather than inline
>> fixnum arithmetic, is emitted because in doing an efficient
>> multiplication not only must the arguments in (* x y) be fixnums, so
>> also must the result -- and there's no way the compiler can guarantee
>> that from your type declaration.  (It could if either the arguments were
>> known to be smaller than the square root of MOST-POSITIVE-FIXNUM, or if
>> you make the promise that it will using (THE FIXNUM (* X Y)))
>>
>
> That makes sense. (It also makes the code uglier, but I suppose that is to
> be expected.)
>
> > (defun test-dot-sa ()
>> >   (let ((a (vector 1 2 3 4))
>> >         (b (vector 4 3 2 1)))
>> >     (time (loop for i from 1 to 100000000 do (dot-sa a b)))))
>>
>> Note that (vector 1 2 3 4) does not return an object of type
>> (simple-array fixnum (4)) -- just because all the elements are a vector
>> are of type fixnum at a given time does not make the vector specialized
>> only to hold fixnums.
>>
>
> Doh! That should have been (make-array '(4) :element-type 'fixnum
> :initial-contents '(1 2 3 4)) .
>
> Cheers,
>>
>> Christophe
>>
>
>
>
> --
> Elliott Slaughter
>
> "Don't worry about what anybody else is going to do. The best way to
> predict the future is to invent it." - Alan Kay
>



-- 
Elliott Slaughter

"Don't worry about what anybody else is going to do. The best way to predict
the future is to invent it." - Alan Kay