Hi all,
any idea on a way to solve this note ?
array is declared to be a simple-array and order is declared to be a fixnum.
; (- (LENGTH ARRAY) ORDER)
; Note: Doing signed word to integer coercion (cost 20), for:
; The first result of inline (signed-byte 32) arithmetic.
Thanks anyway
Martin
Raspaud Martin <········@free.fr> writes:
> array is declared to be a simple-array and order is declared to be a fixnum.
>
> ; (- (LENGTH ARRAY) ORDER)
> ; Note: Doing signed word to integer coercion (cost 20), for:
> ; The first result of inline (signed-byte 32) arithmetic.
(LENGTH ARRAY) could be as much as (1- ARRAY-DIMENSION-LIMIT), which
in cmucl is 536870910. ORDER is anything between -536870912 and
536870911. So the result of the subtraction lies between -536870911
and 1073741822, which falls outside the fixnum range: hence, if you're
unlucky, you will cons a bignum (and cmucl's note is telling you so).
If all you know about ORDER is that it is a fixnum, then this note
is unavoidable (well, it can be turned off with judicious use of
inhibit-warnings, but the underlying cause of the note remains).
However, if you can be more specific about the type of ORDER: say, if
you know it is a positive fixnum, then say so -- declaring it of type
(and fixnum unsigned-byte) would cause cmucl to infer the type of the
result as (integer -536870911 536870910), which is subtypep FIXNUM,
and so has an unboxed representation.
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)
Christophe Rhodes <·····@cam.ac.uk> wrote in message news:<··············@cam.ac.uk>...
> However, if you can be more specific about the type of ORDER: say, if
> you know it is a positive fixnum, then say so -- declaring it of type
> (and fixnum unsigned-byte) would cause cmucl to infer the type of the
> result as (integer -536870911 536870910), which is subtypep FIXNUM,
> and so has an unboxed representation.
Would (and fixnum (integer 0 *)) also work? I like the mathematical
look of that better.
···············@yahoo.com (Mark McConnell) writes:
> Christophe Rhodes <·····@cam.ac.uk> wrote in message news:<··············@cam.ac.uk>...
> > However, if you can be more specific about the type of ORDER: say, if
> > you know it is a positive fixnum, then say so -- declaring it of type
> > (and fixnum unsigned-byte) would cause cmucl to infer the type of the
> > result as (integer -536870911 536870910), which is subtypep FIXNUM,
> > and so has an unboxed representation.
>
> Would (and fixnum (integer 0 *)) also work? I like the mathematical
> look of that better.
Using our "new" excl:normalize-type function from 7.0 on a 32-bit
Allegro CL:
CL-USER(3): (normalize-type '(and fixnum (integer 0 *)))
(INTEGER 0 536870911)
CL-USER(4):
Note also that the normalization of a fixnum:
CL-USER(4): (normalize-type 'fixnum)
(INTEGER -536870912 536870911)
CL-USER(5):
gives a range of one greater on either side in Allegro CL than
it does in Christophe's lisp :-)
[Sorry, Christophe, couldn't resist - I assume your range was just
a typo]
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
In article <·············@franz.com>, Duane Rettig <·····@franz.com> wrote:
> Using our "new" excl:normalize-type function from 7.0 on a 32-bit
> Allegro CL:
>
> CL-USER(3): (normalize-type '(and fixnum (integer 0 *)))
> (INTEGER 0 536870911)
> CL-USER(4):
>
> Note also that the normalization of a fixnum:
>
> CL-USER(4): (normalize-type 'fixnum)
> (INTEGER -536870912 536870911)
> CL-USER(5):
>
> gives a range of one greater on either side in Allegro CL than
> it does in Christophe's lisp :-)
>
> [Sorry, Christophe, couldn't resist - I assume your range was just
> a typo]
I believe Christophe was referring to the compiler-inferred type of the
result of (- (length array) order), where (length array) is of type
(integer 0 (1- array-dimension-limit)), and order is of type
(and fixnum (integer 0 *)).
As far as I can tell, the limits of this would be:
CL-USER> (- 0 most-positive-fixnum)
-536870911
CL-USER> (- (1- array-dimension-limit) 0)
536870910
These are the numbers that Christophe gave. I don't think it was a typo. :)
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Duane Rettig <·····@franz.com> writes:
> ···············@yahoo.com (Mark McConnell) writes:
>
>> Christophe Rhodes <·····@cam.ac.uk> wrote in message news:<··············@cam.ac.uk>...
>> > However, if you can be more specific about the type of ORDER: say, if
>> > you know it is a positive fixnum, then say so -- declaring it of type
>> > (and fixnum unsigned-byte) would cause cmucl to infer the type of the
>> > result as (integer -536870911 536870910), which is subtypep FIXNUM,
>> > and so has an unboxed representation.
>>
>> Would (and fixnum (integer 0 *)) also work? I like the mathematical
>> look of that better.
>
> [...]
> Note also that the normalization of a fixnum:
>
> CL-USER(4): (normalize-type 'fixnum)
> (INTEGER -536870912 536870911)
> CL-USER(5):
>
> gives a range of one greater on either side in Allegro CL than
> it does in Christophe's lisp :-)
>
> [Sorry, Christophe, couldn't resist - I assume your range was just
> a typo]
No, it was accurate. (INTEGER -536870911 536870910) is the range of
the result of the computation in the original question, under the
assumptions made: the loss of one on either side of the range comes
from the fact that ARRAY-DIMENSION-LIMIT is the largest it can be,
MOST-POSITIVE-FIXNUM, but is an exclusive bound: so the return value
of length can be at most (1- array-dimension-limit); and also that
MOST-POSITIVE-FIXNUM is (1- (- MOST-NEGATIVE-FIXNUM)).
* (defun foo (order)
(declare (optimize speed)
(type (and fixnum unsigned-byte) order))
(- (length (lisp-implementation-version)) order))
FOO
* (sb-kernel:%simple-fun-type #'foo)
(FUNCTION ((UNSIGNED-BYTE 29))
(VALUES (INTEGER -536870911 536870910) &OPTIONAL))
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)
Christophe Rhodes <·····@cam.ac.uk> writes:
> Duane Rettig <·····@franz.com> writes:
>
> > ···············@yahoo.com (Mark McConnell) writes:
> >
> >> Christophe Rhodes <·····@cam.ac.uk> wrote in message news:<··············@cam.ac.uk>...
> >> > However, if you can be more specific about the type of ORDER: say, if
> >> > you know it is a positive fixnum, then say so -- declaring it of type
> >> > (and fixnum unsigned-byte) would cause cmucl to infer the type of the
> >> > result as (integer -536870911 536870910), which is subtypep FIXNUM,
> >> > and so has an unboxed representation.
> >>
> >> Would (and fixnum (integer 0 *)) also work? I like the mathematical
> >> look of that better.
> >
> > [...]
> > Note also that the normalization of a fixnum:
> >
> > CL-USER(4): (normalize-type 'fixnum)
> > (INTEGER -536870912 536870911)
> > CL-USER(5):
> >
> > gives a range of one greater on either side in Allegro CL than
> > it does in Christophe's lisp :-)
> >
> > [Sorry, Christophe, couldn't resist - I assume your range was just
> > a typo]
>
> No, it was accurate. (INTEGER -536870911 536870910) is the range of
> the result of the computation in the original question, under the
> assumptions made: the loss of one on either side of the range comes
> from the fact that ARRAY-DIMENSION-LIMIT is the largest it can be,
> MOST-POSITIVE-FIXNUM, but is an exclusive bound: so the return value
> of length can be at most (1- array-dimension-limit); and also that
> MOST-POSITIVE-FIXNUM is (1- (- MOST-NEGATIVE-FIXNUM)).
And the moral of this is to carefully read the context before
trying to get cute. I had equated "it" with "the result", but
re-reading the original post helped me to understand where I
was wrong. Sorry.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
···············@yahoo.com (Mark McConnell) writes:
> Christophe Rhodes <·····@cam.ac.uk> wrote in message news:<··············@cam.ac.uk>...
>> (and fixnum unsigned-byte) would cause cmucl to infer the type of the
>
> Would (and fixnum (integer 0 *)) also work? I like the mathematical
> look of that better.
Sure. Those two types are type equivalent (though, believe it or not,
a Common Lisp system is not required to recognize that fact).
(integer 0 #.most-positive-fixnum) would also mean the same.
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)
Christophe Rhodes wrote:
> Raspaud Martin <········@free.fr> writes:
>
>
>>array is declared to be a simple-array and order is declared to be a fixnum.
>>
>>; (- (LENGTH ARRAY) ORDER)
>>; Note: Doing signed word to integer coercion (cost 20), for:
>>; The first result of inline (signed-byte 32) arithmetic.
>
>
> (LENGTH ARRAY) could be as much as (1- ARRAY-DIMENSION-LIMIT), which
> in cmucl is 536870910. ORDER is anything between -536870912 and
> 536870911. So the result of the subtraction lies between -536870911
> and 1073741822, which falls outside the fixnum range: hence, if you're
> unlucky, you will cons a bignum (and cmucl's note is telling you so).
>
> If all you know about ORDER is that it is a fixnum, then this note
> is unavoidable (well, it can be turned off with judicious use of
> inhibit-warnings, but the underlying cause of the note remains).
> However, if you can be more specific about the type of ORDER: say, if
> you know it is a positive fixnum, then say so -- declaring it of type
> (and fixnum unsigned-byte) would cause cmucl to infer the type of the
> result as (integer -536870911 536870910), which is subtypep FIXNUM,
> and so has an unboxed representation.
>
> Christophe
Thanks very much !
So saying order is a positive fixnum indeed solves the problem. Now I
guess if I do (+ (length array) order) instead, then I'll have a similar
problem. Is it solvable by saying that order should be a small number ?
(say less than 32 for example ?)
Martin
Raspaud Martin <········@free.fr> writes:
> So saying order is a positive fixnum indeed solves the problem. Now I
> guess if I do (+ (length array) order) instead, then I'll have a
> similar problem. Is it solvable by saying that order should be a small
> number ? (say less than 32 for example ?)
In that case, not unless you know that the length of the array will be
at most 31 less than array-dimension-limit.
If you do, then saying
(+ (the (integer 0 #.(- array-dimension-limit 32)) (length array))
order)
will make things work (and since you're using cmucl, this will also
insert a typecheck for you to check that your declaration is true,
unless you're compiling in high speed.
Alternatively, you could say
(let ((x (length array)))
(typecase x
((integer 0 #.(- array-dimension-limit 32)) (+ x order))
((integer 0 #.array-dimension-limit) (+ x order))))
and the slow, note-emitting path would only be taken for those
computations which really need it.
(In fact, with computations of the form (+ <fixnum> <fixnum>), the
cmucl compiler is already able to do much the same internally as the
written-out typecase above:
68: SAR EDX, 2 ; No-arg-parsing entry point
6B: SAR EDI, 2
6E: LEA EAX, [EDX+EDI]
71: MOV EDX, EAX
73: SHL EDX, 1
75: JO L5
77: SHL EDX, 1
79: JO L5
from 68 to 6E, we first shift our fixnums right by two places to
eliminate the tag bits. We then add the resulting things (don't be
fooled by the lack of an ADD instruction: LEA is used here instead).
The remaining code is used to check to see if a bignum should be
consed: if the left shifts overflow, we jump to L5, otherwise we
simply return the fixnum in EDX.
To put it another way: have you profiled your code to find out what
the bottleneck is yet?
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)
Christophe Rhodes wrote:
> Raspaud Martin <········@free.fr> writes:
>
>
>>So saying order is a positive fixnum indeed solves the problem. Now I
>>guess if I do (+ (length array) order) instead, then I'll have a
>>similar problem. Is it solvable by saying that order should be a small
>>number ? (say less than 32 for example ?)
>
>
> In that case, not unless you know that the length of the array will be
> at most 31 less than array-dimension-limit.
>
> If you do, then saying
> (+ (the (integer 0 #.(- array-dimension-limit 32)) (length array))
> order)
> will make things work (and since you're using cmucl, this will also
> insert a typecheck for you to check that your declaration is true,
> unless you're compiling in high speed.
>
> Alternatively, you could say
> (let ((x (length array)))
> (typecase x
> ((integer 0 #.(- array-dimension-limit 32)) (+ x order))
> ((integer 0 #.array-dimension-limit) (+ x order))))
> and the slow, note-emitting path would only be taken for those
> computations which really need it.
I did something similar to the first solution actually. Though the
second one would be more secure...
> (In fact, with computations of the form (+ <fixnum> <fixnum>), the
> cmucl compiler is already able to do much the same internally as the
> written-out typecase above:
>
> 68: SAR EDX, 2 ; No-arg-parsing entry point
> 6B: SAR EDI, 2
> 6E: LEA EAX, [EDX+EDI]
> 71: MOV EDX, EAX
> 73: SHL EDX, 1
> 75: JO L5
> 77: SHL EDX, 1
> 79: JO L5
>
> from 68 to 6E, we first shift our fixnums right by two places to
> eliminate the tag bits. We then add the resulting things (don't be
> fooled by the lack of an ADD instruction: LEA is used here instead).
> The remaining code is used to check to see if a bignum should be
> consed: if the left shifts overflow, we jump to L5, otherwise we
> simply return the fixnum in EDX.
>
> To put it another way: have you profiled your code to find out what
> the bottleneck is yet?
Yes, and the part we're talking about is not the bottleneck part of the
code, but asking those questions allow me to understand better the inner
workings of lisp, and will surely help me for the bottleneck :-)
Thanx a million
Martin