From: Pascal B. <pj...@in...> - 2003-05-07 10:47:40
|
Christophe Rhodes writes: > Pascal Bourguignon <pj...@in...> writes: >=20 > > For example compiling the following source gives all these notices= . > > Why could not I decide how to build my own data structures? How woul= d > > you do it? > > > > In particular, what type uncertainty is there in being a > > (VECTOR (ARRAY BASE-CHAR)) ? >=20 > There are two kinds of type uncertainty in that type, both of them > fairly fundamental (i.e. common to all CL implementations). >=20 > The first is that it is uncertain whether an object of type=20 > (VECTOR (ARRAY BASE-CHAR)) is a SIMPLE-ARRAY or not. Knowing that an > object is definitely a simple-array can lead to significant > performance improvements; unfortunately, there is no way of > expressing, currently, "I am aware that I may pay a price for the > genericity of having this code work on all vectors, not just simple > arrays of rank 1". So some implementations shut up about it, others > don't. (Maybe we should at default compilation settings, I don't > know). To see why this behavior is obnoxious, try to compile this: (defun test-a (stuff) (declare (type t stuff)) (cond ((simple-vector-p stuff) (aref (the simple-vector stuff) 0)) ((vectorp stuff) (aref (the vector stuff) 0)) (t nil))) It looks like sbcl is incapable of (or at least, can't bear) working with anything else than simple arrays. =20 Well, why stop here? Since it's much more efficient to do additions with fixnums, why not issue notices when we use floating point numbers? And why not when you use a string (even a simple-string) issue a notice remembering that it would be much more efficient to avoid those long arrays and just use fixnums. After all, strings can't be stored in registers while fixnum can. It seems to me that the solution is simple: just believe what the programmer writes! I could have written: =20 (declare (type (simple-array (simple-array standard-char *) *)) pict) but since I've written: (declare (type (array (array character *) *)) pict) it should mean that it has to accept any kind of array of any kind of characters. =20 > The second is significantly worse: since the > UPGRADED-ARRAY-ELEMENT-TYPE of (ARRAY BASE-CHAR) is T, the declaration > (VECTOR (ARRAY BASE-CHAR)) means _precisely_ the same as the > declaration (VECTOR T). In other words, as mandated by ANSI, you can > store absolutely anything in that vector, not just arrays of type > BASE-CHAR. Given this, the compiler is unable to infer how to do the > second dereference [in (AREF (AREF ...) ...)], because the result of > the first AREF could be anything. I understand that UPGRADED-ARRAY-ELEMENT-TYPE is implementation dependant, but why does sbcl upgrade a (ARRAY BASE-CHAR) to T and not to (ARRAY BASE-CHAR) ? Is there a declaration I could add to specify that all the elements of my array are of type (ARRAY BASE-CHAR) ? Why can't sbcl infer from: (DECLARE (TYPE (ARRAY (ARRAY CHARACTER *) *) PICT)) that: (TYPE (ARRAY CHARACTER *) (AREF PICT Y)) (ok, you just said it above, but it seems that the meekest C compiler is able to do that...). Would adding THE (ARRAY CHARACTER *) in the right places do? (SETF (AREF (THE (ARRAY CHARACTER *) (AREF PICT Y)) X) FOREGROUND) ;; etc From the above test-a, I don't feel that this would improve the situation. Besides, that seems to be a lot of low-level details to me. > As an aside: this leads me to suspect that a better implementation > of a PICTURE might be as a two dimensional array? Probably. Two reasons that let me to use an array of array are: - since it's an ascii-art framework, it's quite text line oriented and it could be nice to be able to consider it as an array of lines= . - one of the targets does not support multidimensional arrays. In anycase, thank you for your explaining. --=20 __Pascal_Bourguignon__ http://www.informatimago.com/ ---------------------------------------------------------------------- Do not adjust your mind, there is a fault in reality. |
From: Christophe R. <cs...@ca...> - 2003-05-07 11:14:57
|
Pascal Bourguignon <pj...@in...> writes: > Christophe Rhodes writes: >> Pascal Bourguignon <pj...@in...> writes: >> > In particular, what type uncertainty is there in being a >> > (VECTOR (ARRAY BASE-CHAR)) ? >> >> There are two kinds of type uncertainty in that type, both of them >> fairly fundamental (i.e. common to all CL implementations). >> >> The first is that it is uncertain whether an object of type >> (VECTOR (ARRAY BASE-CHAR)) is a SIMPLE-ARRAY or not. Knowing that an >> object is definitely a simple-array can lead to significant >> performance improvements; unfortunately, there is no way of >> expressing, currently, "I am aware that I may pay a price for the >> genericity of having this code work on all vectors, not just simple >> arrays of rank 1". So some implementations shut up about it, others >> don't. (Maybe we should at default compilation settings, I don't >> know). > > To see why this behavior is obnoxious, try to compile this: > > (defun test-a (stuff) > (declare (type t stuff)) > (cond > ((simple-vector-p stuff) (aref (the simple-vector stuff) 0)) > ((vectorp stuff) (aref (the vector stuff) 0)) > (t nil))) > > It looks like sbcl is incapable of (or at least, can't bear) working > with anything else than simple arrays. This is an unfair test of sbcl's type engine, because SIMPLE-VECTOR means (SIMPLE-ARRAY T (*)), while VECTOR means (ARRAY * (*)). Thus, there are simple array types that are not caught by the first clause. However, it turns out that even a properly adjusted test (defun test-a (stuff) (cond ((typep stuff 'simple-vector) (aref stuff 0)) ((typep stuff '(array t (*))) (aref stuff 0)) (t nil))) raises efficiency notes, when really it shouldn't [because in the second branch STUFF should be known to be (AND (ARRAY T (*)) (NOT SIMPLE-VECTOR))], but isn't. > Well, why stop here? Since it's much more efficient to do additions > with fixnums, why not issue notices when we use floating point > numbers? > > And why not when you use a string (even a simple-string) issue a > notice remembering that it would be much more efficient to avoid those > long arrays and just use fixnums. After all, strings can't be stored > in registers while fixnum can. Good point. Thank you for this suggestion; I'll be implementing it as soon as possible. In all seriousness, the diagnostics that sbcl emits come from a hodgepodge of heuristics that have accumulated over time. Some of them are no longer appropriate at all; others are less important than they once were. I think what there is a need for, really, is some way of selectively ignoring the diagnostics; this would solve not only this specific problem that you are having, but also similar problems elsewhere. > It seems to me that the solution is simple: just believe what the > programmer writes! This might be one of those solutions that is simple in conception but tricky in execution. I don't know; I haven't looked at it. >> The second is significantly worse: since the >> UPGRADED-ARRAY-ELEMENT-TYPE of (ARRAY BASE-CHAR) is T, the declaration >> (VECTOR (ARRAY BASE-CHAR)) means _precisely_ the same as the >> declaration (VECTOR T). In other words, as mandated by ANSI, you can >> store absolutely anything in that vector, not just arrays of type >> BASE-CHAR. Given this, the compiler is unable to infer how to do the >> second dereference [in (AREF (AREF ...) ...)], because the result of >> the first AREF could be anything. > > I understand that UPGRADED-ARRAY-ELEMENT-TYPE is implementation > dependant, but why does sbcl upgrade a (ARRAY BASE-CHAR) to T and not > to (ARRAY BASE-CHAR) ? Because the implementation does not provide a representation of arrays specialized to holding arrays of BASE-CHAR. As an example: consider the type (SINGLE-FLOAT 0.0 1.0). If you ask sbcl to create an array :ELEMENT-TYPE '(SINGLE-FLOAT 0.0 1.0), it will give you back an array specialized to hold general SINGLE-FLOATs, the layout of which looks something like this in memory: [ header | length | element0 | element1 | element2 ] where the element<n>s are unboxed single floats (i.e. they don't have any header; they are just the bare IEEE single float in bits). This is what is meant by a specialized array on some type. You might wish to consider what you would need to do to provide a specialization of array to hold objects of type (ARRAY BASE-CHAR). > Is there a declaration I could add to specify that all the elements of > my array are of type (ARRAY BASE-CHAR) ? No. > Would adding THE (ARRAY CHARACTER *) in the right places do? Yes. Cheers, Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge) |
From: Pascal B. <pj...@in...> - 2003-05-07 13:44:13
|
Christophe Rhodes writes: > > I understand that UPGRADED-ARRAY-ELEMENT-TYPE is implementatio= n > > dependant, but why does sbcl upgrade a (ARRAY BASE-CHAR) to T and no= t > > to (ARRAY BASE-CHAR) ? >=20 > Because the implementation does not provide a representation of arrays > specialized to holding arrays of BASE-CHAR. Further thinking on this point, I believe that there's a confusion between the representation (and UPGRADED-ARRAY-ELEMENT-TYPE seems to speak about that), and the semantic. Type inferences and assertions should be about semantics. That is: of course, I understand that an array containing arrays would be implemented as an array of pointers, so it could as well have elements of any kind. But when the programmer assert that this array is (array (array character *) *), he says that he's only considering arrays of arrays of characters, even if that kind of array could, with the same implementation, hold other things. > As an example: consider the type (SINGLE-FLOAT 0.0 1.0). If you ask > sbcl to create an array :ELEMENT-TYPE '(SINGLE-FLOAT 0.0 1.0), it will > give you back an array specialized to hold general SINGLE-FLOATs, the > layout of which looks something like this in memory: >=20 > [ header | length | element0 | element1 | element2 ] >=20 > where the element<n>s are unboxed single floats (i.e. they don't have > any header; they are just the bare IEEE single float in bits). This > is what is meant by a specialized array on some type. Yes, but the type inference engine should remember that elements of this array are always between 0.0 and 1.0, and could apply this knowledge to (AREF (THE (ARRAY (SINGLE-FLOAT 0.0 1.0) PROBS) 0). > You might wish to consider what you would need to do to provide a > specialization of array to hold objects of type (ARRAY BASE-CHAR). I think that since objects of type (ARRAY BASE-CHAR *) may be of different sizes, an array of such objects needs to be an array of pointers to them. An (ARRAY (ARRAY BASE-CHAR 10) *) could put the BASE-CHAR inline: [ header | length |t|e|n|c|h|a|r|a|c|t|t|e|n|c|h|a|r|a|c|t|...] The point is that while a (ARRAY (ARRAY BASE-CHAR *) *) has to be implemented as an (ARRAY T *), it must not forget that it contains actually (ARRAY BASE-CHAR *). > > Is there a declaration I could add to specify that all the elements o= f > > my array are of type (ARRAY BASE-CHAR) ? >=20 > No. >=20 > > Would adding THE (ARRAY CHARACTER *) in the right places do? >=20 > Yes. --=20 __Pascal_Bourguignon__ http://www.informatimago.com/ ---------------------------------------------------------------------- Do not adjust your mind, there is a fault in reality. |
From: Christophe R. <cs...@ca...> - 2003-05-07 13:48:38
|
Pascal Bourguignon <pj...@in...> writes: > The point is that while a (ARRAY (ARRAY BASE-CHAR *) *) has to be > implemented as an (ARRAY T *), it must not forget that it contains > actually (ARRAY BASE-CHAR *). Yes it must. It is required to by the ANSI standard for the language. See the CLHS page for System Class ARRAY: If element-type is the symbol *, arrays are not excluded on the basis of their element type. Otherwise, only those arrays are included whose actual array element type is the result of upgrading element-type; see Section 15.1.2.1 (Array Upgrading). Cheers, Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge) |
From: Pascal B. <pj...@in...> - 2003-05-07 14:28:16
|
Christophe Rhodes writes: > Pascal Bourguignon <pj...@in...> writes: >=20 > > The point is that while a (ARRAY (ARRAY BASE-CHAR *) *) has to b= e > > implemented as an (ARRAY T *), it must not forget that it contain= s > > actually (ARRAY BASE-CHAR *). >=20 > Yes it must. It is required to by the ANSI standard for the > language. See the CLHS page for System Class ARRAY: >=20 > If element-type is the symbol *, arrays are not excluded on the > basis of their element type. Otherwise, only those arrays are > included whose actual array element type is the result of upgrading > element-type; see Section 15.1.2.1 (Array Upgrading). Beware, I've always specified the type of the elements. I've only used the * wildcard for the dimension. (ARRAY BASE-CHAR *) ^ ^ | | | +---- dimension =3D whatever between 0 and=20 | (1- array-dimension-limit) +---- :element-type =3D BASE-CHAR --=20 __Pascal_Bourguignon__ http://www.informatimago.com/ ---------------------------------------------------------------------- Do not adjust your mind, there is a fault in reality. |
From: Christophe R. <cs...@ca...> - 2003-05-07 14:20:06
|
Pascal Bourguignon <pj...@in...> writes: >> As an example: consider the type (SINGLE-FLOAT 0.0 1.0). If you ask >> sbcl to create an array :ELEMENT-TYPE '(SINGLE-FLOAT 0.0 1.0), it will >> give you back an array specialized to hold general SINGLE-FLOATs, the >> layout of which looks something like this in memory: >> >> [ header | length | element0 | element1 | element2 ] >> >> where the element<n>s are unboxed single floats (i.e. they don't have >> any header; they are just the bare IEEE single float in bits). This >> is what is meant by a specialized array on some type. > > Yes, but the type inference engine should remember that elements of > this array are always between 0.0 and 1.0, and could apply this > knowledge to (AREF (THE (ARRAY (SINGLE-FLOAT 0.0 1.0) PROBS) 0). I don't think that implementation strategy is as inexpensive as you seem to think it is. Consider: (defun foo (x) (declare (type (simple-array (single-float 0.0 1.0) (*)) x)) (bar x) (aref x 0)) Is the "type inference engine" entitled to assume that the return value from FOO will be a single float in the range 0.0 to 1.0? Well, maybe, by some lights, but BAR here is an arbitrary function that could modify the contents of X in an arbitrary way. To provide reasonable diagnostics in the case of violation of this constraint, we have to execute _runtime_ checks in the presence of any modification inside BAR (and remember, we can change BAR's function binding at will, so we have to remember that we have to reinsert runtime checks on recompiling BAR). >> You might wish to consider what you would need to do to provide a >> specialization of array to hold objects of type (ARRAY BASE-CHAR). > > I think that since objects of type (ARRAY BASE-CHAR *) may be of > different sizes, an array of such objects needs to be an array of > pointers to them. An (ARRAY (ARRAY BASE-CHAR 10) *) could put the > BASE-CHAR inline: > > [ header | length |t|e|n|c|h|a|r|a|c|t|t|e|n|c|h|a|r|a|c|t|...] No, you can't do this. Arrays are objects which have identity; in other words, you can use EQL to ask whether two arrays are in fact the same object. With the above implementation scheme, there would be no way of, say, storing the same array twice in one of these arrays of arrays. Cheers, Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge) |
From: Pascal B. <pj...@in...> - 2003-05-07 14:47:30
|
Christophe Rhodes writes: > Pascal Bourguignon <pj...@in...> writes: >=20 > >> As an example: consider the type (SINGLE-FLOAT 0.0 1.0). If you ask > >> sbcl to create an array :ELEMENT-TYPE '(SINGLE-FLOAT 0.0 1.0), it wi= ll > >> give you back an array specialized to hold general SINGLE-FLOATs, th= e > >> layout of which looks something like this in memory: > >>=20 > >> [ header | length | element0 | element1 | element2 ] > >>=20 > >> where the element<n>s are unboxed single floats (i.e. they don't hav= e > >> any header; they are just the bare IEEE single float in bits). This > >> is what is meant by a specialized array on some type. > > > > Yes, but the type inference engine should remember that elements o= f > > this array are always between 0.0 and 1.0, and could apply thi= s > > knowledge to (AREF (THE (ARRAY (SINGLE-FLOAT 0.0 1.0) PROBS) 0). >=20 > I don't think that implementation strategy is as inexpensive as you > seem to think it is. Consider: > (defun foo (x) > (declare (type (simple-array (single-float 0.0 1.0) (*)) x)) > (bar x) > (aref x 0)) >=20 > Is the "type inference engine" entitled to assume that the return > value from FOO will be a single float in the range 0.0 to 1.0? Well, > maybe, by some lights, but BAR here is an arbitrary function that > could modify the contents of X in an arbitrary way. To provide > reasonable diagnostics in the case of violation of this constraint, we > have to execute _runtime_ checks in the presence of any modification > inside BAR (and remember, we can change BAR's function binding at > will, so we have to remember that we have to reinsert runtime checks > on recompiling BAR). I've not said anything about the cost of checking the assertions. But note that it's sbcl who started first to interpret the declarations as assertions. Yes, in foo, I'd expect the result to be between 0.0 and 1.0, and sbcl promize to treat the declaration as an assertion would imply to raise an exception if any element of x is out of these bounds after (bar x). I let it up to the compiler to decide if it's better to check systematically all the elements of x after calling bar, or if it can prove that bar does not invalidate this invariant of x (for whatever value bar may have at run time, if it can determine them). It's similar to: (defun foofix (x) (declare (type (fixnum 0 10) x)) (setq x (bar x)) x) There too you'd expect the result of foofix to be between 0 and 10. That x be a scalar here, or an array there does not change anything. > >> You might wish to consider what you would need to do to provide a > >> specialization of array to hold objects of type (ARRAY BASE-CHAR). > > > > I think that since objects of type (ARRAY BASE-CHAR *) may be o= f > > different sizes, an array of such objects needs to be an array o= f > > pointers to them. An (ARRAY (ARRAY BASE-CHAR 10) *) could put th= e > > BASE-CHAR inline: > > > > [ header | length |t|e|n|c|h|a|r|a|c|t|t|e|n|c|h|a|r|a|c|t|...] >=20 > No, you can't do this. Arrays are objects which have identity; in > other words, you can use EQL to ask whether two arrays are in fact the > same object. With the above implementation scheme, there would be no > way of, say, storing the same array twice in one of these arrays of > arrays. I agree, I may have gone a little too far. But I give more liberty to the compiler to do whatever it wants as long as it preserves the semantics. (It may have noticed that the system contains no references to these 10-char arrays, or it may have determined that it's more efficient to make them displaced arrays given the usage pattern). --=20 __Pascal_Bourguignon__ http://www.informatimago.com/ ---------------------------------------------------------------------- Do not adjust your mind, there is a fault in reality. |
From: Pascal B. <pj...@in...> - 2003-05-07 15:01:04
|
Christophe Rhodes writes: > [ off-list to give you a chance to reflect. ] Thank you :-)=20 > Pascal Bourguignon <pj...@in...> writes: >=20 > > Christophe Rhodes writes: > >> Pascal Bourguignon <pj...@in...> writes: > >>=20 > >> > The point is that while a (ARRAY (ARRAY BASE-CHAR *) *) has t= o be > >> > implemented as an (ARRAY T *), it must not forget that it cont= ains > >> > actually (ARRAY BASE-CHAR *). > >>=20 > >> Yes it must. It is required to by the ANSI standard for the > >> language. See the CLHS page for System Class ARRAY: > >>=20 > >> If element-type is the symbol *, arrays are not excluded on the > >> basis of their element type. Otherwise, only those arrays are > >> included whose actual array element type is the result of upgradin= g > >> element-type; see Section 15.1.2.1 (Array Upgrading). > > > > Beware, I've always specified the type of the elements. I've only use= d > > the * wildcard for the dimension. >=20 > Perhaps you failed to read the second sentence of the quote? Yes. You're right. That's unfortunate. They link such a high level expression as: (ARRAY (ARRAY BASE-CHAR *) *) to an implementation detail such as UPGRADED-ARRAY-ELEMENT-TYPE. This is without much consequence until you treat type declarations as assertions. So the standard imposes for arrays something like if we said: (declare (fixnum 0 10) x) but because x would be implemented as a signed short anyway, it should be treated as: (declare (fixnum -32768 32767) x) and: (incf x 30000) should not raise any exception. It feels wrong (particularly given that I have today a computer that's 100 times more powerful than 10 years ago when the standard was fixed, and that there are enough free cycles in it to do all the inferences needed to do the right thing), and I'd move to ignore that second sentence. (In the meantime, I'll ignore all notices from sbcl, but I don't like doing that). --=20 __Pascal_Bourguignon__ http://www.informatimago.com/ ---------------------------------------------------------------------- Do not adjust your mind, there is a fault in reality. |
From: Christophe R. <cs...@ca...> - 2003-05-07 15:13:34
|
Pascal Bourguignon <pj...@in...> writes: > (In the meantime, I'll ignore all notices from sbcl, but I don't like > doing that). Well, I do hope eventually that there will be some framework for selectively ignoring optimization notes, independent of what the default annoyance level should be. But until we either get copious free time or patches, I wouldn't hold your breath. :-/ Cheers, Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge) |
From: Todd S. <ts...@op...> - 2003-05-07 15:37:43
|
Pascal Bourguignon <pj...@in...> writes: > Christophe Rhodes writes: > > [ off-list to give you a chance to reflect. ] > > Thank you :-) > > > Pascal Bourguignon <pj...@in...> writes: > > > > > Christophe Rhodes writes: > > >> Pascal Bourguignon <pj...@in...> writes: > > >> > > >> > The point is that while a (ARRAY (ARRAY BASE-CHAR *) *) has to be > > >> > implemented as an (ARRAY T *), it must not forget that it contains > > >> > actually (ARRAY BASE-CHAR *). > > >> > > >> Yes it must. It is required to by the ANSI standard for the > > >> language. See the CLHS page for System Class ARRAY: > > >> > > >> If element-type is the symbol *, arrays are not excluded on the > > >> basis of their element type. Otherwise, only those arrays are > > >> included whose actual array element type is the result of upgrading > > >> element-type; see Section 15.1.2.1 (Array Upgrading). > > > > > > Beware, I've always specified the type of the elements. I've only used > > > the * wildcard for the dimension. > > > > Perhaps you failed to read the second sentence of the quote? > > Yes. You're right. That's unfortunate. They link such a high level > expression as: (ARRAY (ARRAY BASE-CHAR *) *) to an implementation > detail such as UPGRADED-ARRAY-ELEMENT-TYPE. This is without much > consequence until you treat type declarations as assertions. I'm not so sure. The CLHS page for Declaration TYPE has this to say: Within the lexical scope of an array type declaration, all references to array elements are assumed to satisfy the expressed array element type (as opposed to the upgraded array element type). A compiler can treat the code within the scope of the array type declaration as if each access of an array element were surrounded by an appropriate the form. The Examples section there reinforces this, except that it seems to invoke undefined behavior by storing 127 into an (array (signed-byte 5) 1) array. I think that's probably an errata, but maybe I'm missing something? -- Todd Sabin <ts...@op...> |
From: Christophe R. <cs...@ca...> - 2003-05-09 00:55:03
|
Todd Sabin <ts...@op...> writes: > I'm not so sure. The CLHS page for Declaration TYPE has this to say: > > Within the lexical scope of an array type declaration, all > references to array elements are assumed to satisfy the expressed > array element type (as opposed to the upgraded array element > type). A compiler can treat the code within the scope of the array > type declaration as if each access of an array element were > surrounded by an appropriate the form. Oh, great! :-) I'd never absorbed that passage before. At least this seems to give some latitude for implementing what is demonstrably user-requested behaviour. There's at least a chance that it can be made to work consistently, too, but it'll take some thinking, I should think. Cheers, Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge) |
From: Christophe R. <cs...@ca...> - 2003-06-27 10:17:00
|
[ sbcl-help removed, but protagonists retained :-) ] Christophe Rhodes <cs...@ca...> writes: > Todd Sabin <ts...@op...> writes: > >> I'm not so sure. The CLHS page for Declaration TYPE has this to say: >> >> Within the lexical scope of an array type declaration, all >> references to array elements are assumed to satisfy the expressed >> array element type (as opposed to the upgraded array element >> type). A compiler can treat the code within the scope of the array >> type declaration as if each access of an array element were >> surrounded by an appropriate the form. > > Oh, great! :-) I'd never absorbed that passage before. > > At least this seems to give some latitude for implementing what is > demonstrably user-requested behaviour. There's at least a chance that > it can be made to work consistently, too, but it'll take some > thinking, I should think. It did take some thinking, but I believe I've got it right. In CVS as of now (so I'm afraid that, thanks to sourceforge's remarkably bad anoncvs access at present, non-developers might have to wait a little; ideas for solutions to this suboptimality are welcome), in sbcl-0.8.1.9, I've implemented the behaviour this describes. So (compile nil '(lambda (x) (declare (type (simple-array (simple-string 3) (5)) x)) (aref (aref x 0) 0))) does not emit any notes, and (defun array-element-type-handling (x) (declare (optimize safety)) (declare (type (vector cons) x)) (when (consp (aref x 0)) (aref x 0))) signals an error when called with argument #(0). Cheers, Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge) |
From: William H. N. <wil...@ai...> - 2003-05-07 12:11:42
|
On Wed, May 07, 2003 at 12:44:22PM +0200, Pascal Bourguignon wrote: > > Christophe Rhodes writes: > > Pascal Bourguignon <pj...@in...> writes: > > > > > For example compiling the following source gives all these notices. > > > Why could not I decide how to build my own data structures? How would > > > you do it? > > > > > > In particular, what type uncertainty is there in being a > > > (VECTOR (ARRAY BASE-CHAR)) ? > > > > There are two kinds of type uncertainty in that type, both of them > > fairly fundamental (i.e. common to all CL implementations). > > > > The first is that it is uncertain whether an object of type > > (VECTOR (ARRAY BASE-CHAR)) is a SIMPLE-ARRAY or not. Knowing that an > > object is definitely a simple-array can lead to significant > > performance improvements; unfortunately, there is no way of > > expressing, currently, "I am aware that I may pay a price for the > > genericity of having this code work on all vectors, not just simple > > arrays of rank 1". So some implementations shut up about it, others > > don't. (Maybe we should at default compilation settings, I don't > > know). > > To see why this behavior is obnoxious, try to compile this: > > (defun test-a (stuff) > (declare (type t stuff)) > (cond > ((simple-vector-p stuff) (aref (the simple-vector stuff) 0)) > ((vectorp stuff) (aref (the vector stuff) 0)) > (t nil))) > > It looks like sbcl is incapable of (or at least, can't bear) working > with anything else than simple arrays. There is a significant performance penalty for working with nonsimple arrays, although less than there used to be. ANSI doesn't provide any portable way to declare the subcases of nonsimpleness, so once you allow an array to be simple it might have a FILL-POINTER or be displaced, and although a sufficiently smart compiler might be able to avoid checking for those things on every array access, SBCL's compiler is not usually as smart as that, so it's expensive. And as noted before, there's no way defined by ANSI to say "I'm intentionally working with a non-SIMPLE array here" as opposed to an array you know to be simple but just didn't get around to declaring. (A similar problem also exists with INTEGERs as opposed to FIXNUMs.) Then since the compiler can't be told the difference between unintentionally general and intentionally general operations, once it takes it upon itself to notify people of expensive operations, it becomes rather noisy. > Well, why stop here? Since it's much more efficient to do additions > with fixnums, why not issue notices when we use floating point > numbers? > > And why not when you use a string (even a simple-string) issue a > notice remembering that it would be much more efficient to avoid those > long arrays and just use fixnums. After all, strings can't be stored > in registers while fixnum can. > > It seems to me that the solution is simple: just believe what the > programmer writes! Although most of your suggestions above are facetious, I think you may have hit the mark with the last one. I'd suggest ignoring the optimization notes (on the theory that you know best, pretty close to "believe what the programmer writes") except where profiling shows you that the performance of a piece of code is an issue. In any code where the performance of a naive byte-coded implementation would be good enough -- i.e., in somewhat more than 90% of the code that most people write today -- the optimization notes are unlikely to be worth bothering with. When and if you get around to trying to improve the performance of a bottleneck, though, you may find the notes less annoying. -- William Harold Newman <wil...@ai...> "The difference between us is that you are the end of your genealogy, and I the beginning of mine." -- Bedouin to another Bedouin who has been boasting of his ancestry, from Al-Tannukhi, _Tabletalk of a Mesopotamian Judge_ PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C |