From: Elliott S. <ell...@gm...> - 2011-04-03 16:45:31
|
Hi there, 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)))) (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))))) And an example warning: ; in: DEFUN DOT-SA ; (* (AREF A 0) (AREF B 0)) ; ; note: forced to do GENERIC-* (cost 30) ; unable to do inline fixnum arithmetic (cost 4) because: ; The result is a (VALUES ; (INTEGER -1329227995784915871750885555673497600 ; 1329227995784915872903807060280344576) ; &OPTIONAL), not a (VALUES FIXNUM &REST T). ; unable to do inline (signed-byte 64) arithmetic (cost 5) because: ; The result is a (VALUES ; (INTEGER -1329227995784915871750885555673497600 ; 1329227995784915872903807060280344576) ; &OPTIONAL), not a (VALUES (SIGNED-BYTE 64) &REST T). ; etc. Thanks. -- 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 |
From: Christophe R. <cs...@ca...> - 2011-04-03 17:10:32
|
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))) > (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. Cheers, Christophe |
From: Elliott S. <ell...@gm...> - 2011-04-04 02:11:49
|
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 |
From: Elliott S. <ell...@gm...> - 2011-04-04 02:52:39
|
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 |
From: Christophe R. <cs...@ca...> - 2011-04-04 04:46:26
|
Elliott Slaughter <ell...@gm...> writes: > 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. simple-vector and (simple-array * (*)) are the same type. Cheers, Christophe |
From: Stas B. <sta...@gm...> - 2011-04-04 09:03:06
|
Christophe Rhodes <cs...@ca...> writes: > Elliott Slaughter <ell...@gm...> writes: > >> 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. > > simple-vector and (simple-array * (*)) are the same type. > Not really, simple-vector is (simple-array t (*)), which isn't the same thing as (simple-array * (*)), T type describes only non-specialized arrays, i.e. whose upgraded-array-element-type is T. >From http://www.lispworks.com/documentation/HyperSpec/Body/t_vector.htm "If element-type is the symbol *, vectors are not excluded on the basis of their element type. Otherwise, only those vectors are included whose actual array element type is the result of upgrading element-type" -- With best regards, Stas. |
From: Elliott S. <ell...@gm...> - 2011-04-04 06:01:46
|
On Sun, Apr 3, 2011 at 9:46 PM, Christophe Rhodes <cs...@ca...> wrote: > Elliott Slaughter <ell...@gm...> writes: > > > 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. > > simple-vector and (simple-array * (*)) are the same type. > Ok, how do you explain this 7x slowdown in the simple-array version? * (test-dot-sv) Evaluation took: 1.071 seconds of real time 1.069586 seconds of total run time (1.068155 user, 0.001431 system) 99.91% CPU 2,129,745,315 processor cycles 0 bytes consed NIL * (test-dot-sa) Evaluation took: 7.447 seconds of real time 7.443920 seconds of total run time (7.442668 user, 0.001252 system) 99.96% CPU 14,819,741,175 processor cycles 0 bytes consed -- 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 |
From: Christophe R. <cs...@ca...> - 2011-04-04 06:15:05
|
Elliott Slaughter <ell...@gm...> writes: > On Sun, Apr 3, 2011 at 9:46 PM, Christophe Rhodes <cs...@ca...> wrote: > >> Elliott Slaughter <ell...@gm...> writes: >> >> > 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. >> >> simple-vector and (simple-array * (*)) are the same type. >> > > Ok, how do you explain this 7x slowdown in the simple-array version? Oh, sorry, simple-array on its own means (simple-array * *) -- i.e. it is not known to be a vector. There is then an extra memory indirection, and probably (unless you're compiling under low safety) a check that the array is in fact a vector. Cheers, Christophe |