Consider the following code, which is part of a larger program, but
which I have isolated to show my problem :
(declaim
(optimize (speed 3) (compilation-speed 0)))
(declaim
(ftype (function (shift) (unsigned-byte 32)) propagate))
(defstruct shift
(result 0 :type (unsigned-byte 32))
(value 0 :type (unsigned-byte 32)))
(defun propagate (s)
(setf (the (unsigned-byte) (shift-value s))
(the (unsigned-byte) (shift-result s))))
When I compile this with SBCL, I get the following notes :
; in: DEFUN PROPAGATE
; (DEFUN PROPAGATE (S)
; (SETF (THE (UNSIGNED-BYTE) (SHIFT-VALUE S))
; (THE (UNSIGNED-BYTE) (SHIFT-RESULT S))))
; --> PROGN EVAL-WHEN SB-IMPL::%DEFUN SB-INT:NAMED-LAMBDA
; ==>
; #'(SB-INT:NAMED-LAMBDA PROPAGATE (S)
; (BLOCK PROPAGATE
; (SETF (THE (UNSIGNED-BYTE) (SHIFT-VALUE
S))
; (THE (UNSIGNED-BYTE) (SHIFT-RESULT
S)))))
;
; note: doing unsigned word to integer coercion (cost 20) to "<return
value>"
;
Whatever I try, I can't seem to get rid of the unsigned-byte to integer
coercion.
Can anybody explain what is (could be) going on here ?
Regards,
Jurgen
From: Pascal Bourguignon
Subject: Re: Adding typedeclarations to SBCL for optimisations
Date:
Message-ID: <87u04129aj.fsf@informatimago.com>
"jurgen_defurne" <··············@pandora.be> writes:
> Consider the following code, which is part of a larger program, but
> which I have isolated to show my problem :
> [...]
> Whatever I try, I can't seem to get rid of the unsigned-byte to integer
> coercion.
>
> Can anybody explain what is (could be) going on here ?
I don't observe the same (even with the (unsigned-byte) instead of
(unsigned-byte 32))...
* (cat "/tmp/s.lisp")
(declaim
(optimize (speed 3) (compilation-speed 0)))
(declaim
(ftype (function (shift) (unsigned-byte 32)) propagate))
(defstruct shift
(result 0 :type (unsigned-byte 32))
(value 0 :type (unsigned-byte 32)))
(defun propagate (s)
(setf (the (unsigned-byte 32) (shift-value s))
(the (unsigned-byte 32) (shift-result s))))
(defun main ()
(let ((s (make-shift :value 32)))
(propagate s)
(print s)))
* (load(compile-file "/tmp/s.lisp"))
; compiling file "/tmp/s.lisp" (written 24 AUG 2006 09:59:25 PM):
; compiling (DECLAIM (OPTIMIZE # ...))
; compiling (DECLAIM (FTYPE # ...))
; compiling (DEFSTRUCT SHIFT ...)
; compiling (DEFUN PROPAGATE ...)
; compiling (DEFUN MAIN ...)
; /tmp/s.fasl written
; compilation finished in 0:00:00
T
* (main)
#S(SHIFT :RESULT 0 :VALUE 0)
#S(SHIFT :RESULT 0 :VALUE 0)
* (lisp-implementation-version)
"0.9.15"
*
--
__Pascal Bourguignon__
Pascal Bourguignon wrote:
> "jurgen_defurne" <··············@pandora.be> writes:
>
> > Consider the following code, which is part of a larger program, but
> > which I have isolated to show my problem :
> > [...]
> > Whatever I try, I can't seem to get rid of the unsigned-byte to integer
> > coercion.
> >
> > Can anybody explain what is (could be) going on here ?
>
> I don't observe the same (even with the (unsigned-byte) instead of
> (unsigned-byte 32))...
>
> * (cat "/tmp/s.lisp")
> (declaim
> (optimize (speed 3) (compilation-speed 0)))
>
> (declaim
> (ftype (function (shift) (unsigned-byte 32)) propagate))
>
> (defstruct shift
> (result 0 :type (unsigned-byte 32))
> (value 0 :type (unsigned-byte 32)))
>
> (defun propagate (s)
> (setf (the (unsigned-byte 32) (shift-value s))
> (the (unsigned-byte 32) (shift-result s))))
>
>
> (defun main ()
> (let ((s (make-shift :value 32)))
> (propagate s)
> (print s)))
>
>
> * (load(compile-file "/tmp/s.lisp"))
>
> ; compiling file "/tmp/s.lisp" (written 24 AUG 2006 09:59:25 PM):
> ; compiling (DECLAIM (OPTIMIZE # ...))
> ; compiling (DECLAIM (FTYPE # ...))
> ; compiling (DEFSTRUCT SHIFT ...)
> ; compiling (DEFUN PROPAGATE ...)
> ; compiling (DEFUN MAIN ...)
>
> ; /tmp/s.fasl written
> ; compilation finished in 0:00:00
> T
> * (main)
>
> #S(SHIFT :RESULT 0 :VALUE 0)
> #S(SHIFT :RESULT 0 :VALUE 0)
>
> * (lisp-implementation-version)
>
> "0.9.15"
> *
>
>
>
> --
> __Pascal Bourguignon__
Well, I am using the same, SBCL 0.9.15 on Debian unstable.
But you are using '(load (compile-file ""))', which is not something
that one can seem to derive from the CLHS and Ansi Common Lisp.
I just do '(compile-file "")'.
I do not suppose it makes a real difference (can't test it at this
moment, but maybe this evening).
Thanks,
Jurgen
Pascal Bourguignon <···@informatimago.com> wrote:
> "jurgen_defurne" <··············@pandora.be> writes:
>
>> Consider the following code, which is part of a larger program, but
>> which I have isolated to show my problem :
>> [...]
>> Whatever I try, I can't seem to get rid of the unsigned-byte to integer
>> coercion.
>>
>> Can anybody explain what is (could be) going on here ?
>
> I don't observe the same
In that case you're probably using a 64-bit sbcl.
> (even with the (unsigned-byte) instead of (unsigned-byte 32))...
That is to be expected. But it should warn if you declare the types as
(UNSIGNED-BYTE 64).
--
Juho Snellman
Juho Snellman wrote:
> Pascal Bourguignon <···@informatimago.com> wrote:
> > "jurgen_defurne" <··············@pandora.be> writes:
> >
> >> Consider the following code, which is part of a larger program, but
> >> which I have isolated to show my problem :
> >> [...]
> >> Whatever I try, I can't seem to get rid of the unsigned-byte to integer
> >> coercion.
> >>
> >> Can anybody explain what is (could be) going on here ?
> >
> > I don't observe the same
>
> In that case you're probably using a 64-bit sbcl.
>
> > (even with the (unsigned-byte) instead of (unsigned-byte 32))...
>
> That is to be expected. But it should warn if you declare the types as
> (UNSIGNED-BYTE 64).
>
> --
> Juho Snellman
Allright, now I understand more of it. I have looked through the SBCL
manual and I should be able to suppress such notes on the function
level.
Regards,
Jurgen
From: Christophe Rhodes
Subject: Re: Adding typedeclarations to SBCL for optimisations
Date:
Message-ID: <sq1wr5rdmj.fsf@cam.ac.uk>
"jurgen_defurne" <··············@pandora.be> writes:
> (defstruct shift
> (result 0 :type (unsigned-byte 32))
> (value 0 :type (unsigned-byte 32)))
>
> (defun propagate (s)
> (setf (the (unsigned-byte) (shift-value s))
> (the (unsigned-byte) (shift-result s))))
>
> When I compile this with SBCL, I get the following notes :
>
> ; in: DEFUN PROPAGATE
> ; (DEFUN PROPAGATE (S)
> ; (SETF (THE (UNSIGNED-BYTE) (SHIFT-VALUE S))
> ; (THE (UNSIGNED-BYTE) (SHIFT-RESULT S))))
> ;
> ; note: doing unsigned word to integer coercion (cost 20) to "<return
> value>"
> ;
>
> Whatever I try, I can't seem to get rid of the unsigned-byte to integer
> coercion.
>
> Can anybody explain what is (could be) going on here ?
If you call PROPAGATE in a place where it is not inlined, the
PROPAGATE function must return a value to the caller. This caller
cannot assume anything about its return value, which can be any lisp
object. Therefore, PROPAGATE must box its return value, as (on a
32-bit Lisp) a 32-bit unsigned-byte is generally a bignum.
In this instance, I suspect that you meant not to return the
(unsigned-byte 32) quantity from PROPAGATE, but no values at all
(since you're destructively modifying your input). So with
(defun propagate (s)
(setf (shift-value s) (shift-result s))
(values))
you should no longer get any notes at all.
If you do want to return a 32-bit integer, then you can't get rid of
the efficiency note by adjusting your code, because the act of
returning a 32-bit integer is fundamentally inefficient. You would
probably want to mitigate that by inlining PROPAGATE in hotspots, and
to muffle the compiler note at the definition site.
Christophe
Christophe Rhodes wrote:
> "jurgen_defurne" <··············@pandora.be> writes:
>
> > (defstruct shift
> > (result 0 :type (unsigned-byte 32))
> > (value 0 :type (unsigned-byte 32)))
> >
> > (defun propagate (s)
> > (setf (the (unsigned-byte) (shift-value s))
> > (the (unsigned-byte) (shift-result s))))
> >
> > When I compile this with SBCL, I get the following notes :
> >
> > ; in: DEFUN PROPAGATE
> > ; (DEFUN PROPAGATE (S)
> > ; (SETF (THE (UNSIGNED-BYTE) (SHIFT-VALUE S))
> > ; (THE (UNSIGNED-BYTE) (SHIFT-RESULT S))))
> > ;
> > ; note: doing unsigned word to integer coercion (cost 20) to "<return
> > value>"
> > ;
> >
> > Whatever I try, I can't seem to get rid of the unsigned-byte to integer
> > coercion.
> >
> > Can anybody explain what is (could be) going on here ?
>
> If you call PROPAGATE in a place where it is not inlined, the
> PROPAGATE function must return a value to the caller. This caller
> cannot assume anything about its return value, which can be any lisp
> object. Therefore, PROPAGATE must box its return value, as (on a
> 32-bit Lisp) a 32-bit unsigned-byte is generally a bignum.
>
> In this instance, I suspect that you meant not to return the
> (unsigned-byte 32) quantity from PROPAGATE, but no values at all
> (since you're destructively modifying your input). So with
>
> (defun propagate (s)
> (setf (shift-value s) (shift-result s))
> (values))
>
> you should no longer get any notes at all.
>
> If you do want to return a 32-bit integer, then you can't get rid of
> the efficiency note by adjusting your code, because the act of
> returning a 32-bit integer is fundamentally inefficient. You would
> probably want to mitigate that by inlining PROPAGATE in hotspots, and
> to muffle the compiler note at the definition site.
>
> Christophe
Thanks for the explanation (I didn't know about the values clause), and
I will test it,
but I had already a variant in which I returned NIL. Even then I get a
warning about a integer coercion, but from the second field in the setf
clause. I will post it this evening.
Regards,
Jurgen
Christophe Rhodes wrote:
> If you call PROPAGATE in a place where it is not inlined, the
> PROPAGATE function must return a value to the caller. This caller
> cannot assume anything about its return value, which can be any lisp
> object.
(declaim (ftype (function (fixnum fixnum) (values fixnum &optional))
test))
(defun test(a b)
(+ a b))
Function could return unboxed fixnum if no one used function before
(declaim .. .
May be something like (declaim (maybe-inline test)) should exist - It
doesn't force compiler to do inlineing but assures that function will
not be redefined.
From: Christophe Rhodes
Subject: Re: Adding typedeclarations to SBCL for optimisations
Date:
Message-ID: <sqwt8xp0wh.fsf@cam.ac.uk>
"Alexander" <········@gmail.com> writes:
> Christophe Rhodes wrote:
>
>> If you call PROPAGATE in a place where it is not inlined, the
>> PROPAGATE function must return a value to the caller. This caller
>> cannot assume anything about its return value, which can be any lisp
>> object.
>
> (declaim (ftype (function (fixnum fixnum) (values fixnum &optional))
> test))
> (defun test(a b)
> (+ a b))
>
> Function could return unboxed fixnum if no one used function before
> (declaim .. .
Sadly, that is not so, not without doing extra work at call sites.
Consider
(defun bar (x a b)
(1- (funcall x a b)))
(declaim (ftype (function ((unsigned-byte 32) (unsigned-byte 32))
(values (unsigned-byte 32) &optional))
test))
(defun test (a b)
(+ a b))
(defun foo (a b)
(if (= 0 (random 2))
(bar #'test a b)
(bar #'+ a b)))
in this example, BAR cannot possibly know a priori what its first
argument's returning convention will be. So, if it is possible for
functions to return unboxed values, there has to be some accompanying
flag to inform the caller that it might need to box it before doing
anything else.
> May be something like (declaim (maybe-inline test)) should exist - It
> doesn't force compiler to do inlineing but assures that function will
> not be redefined.
It's not the redefinition that matters, unfortunately -- since the
ftype declamation promises that any redefinition will be compatible.
It is the fact that return conventions can be mixed at the same call
site. As I say, it is possible to implement this -- something similar
is done for multiple values, after all -- but it is tricky to get
right in all cases, and it's not clear that it actually solves a
problem.
Christophe
Christophe Rhodes wrote:
> Sadly, that is not so, not without doing extra work at call sites.
> Consider
I see. Thanks.
May be compiler could create two different code for the same function -
one to be used in general case (funcall) and another in 'direct'
function invocation via (test a b).
May be it's possible to generate specialized code for some call sites.
For example if some big function 'test' declared as inline (but without
type and ftype declarations) and used in most places with (integer 10)
arguments , and in other places with bignum - does it make sense not to
inline it in all sites but generate 3 different code - general case ,
and specialized cases for bignum and fixnum. Another example -
specialized code that could be called if rest and key arguments was
parsed by caller side(Then argument list is known at compile-time). May
be, it could be done with (compiler) macro , but it's tricky enouth.
First of all, thanks for the help, everyone who has posted.
I have been able to remove quite some warnings, also in part because of
switching from (unsigned-byte 32) to (signed-byte 32).
Well, as anyone of you probably already know, this is not the end of
optimising Common Lisp (btw. due to another thread, I found out about
the fannenkuch document, which shows a lot more nice integer
optimisations).
My next problem has to do with logical operations.
;;; Begin example code
(declaim
(optimize (compilation-speed 0) (speed 3)))
(deftype word ()
`(signed-byte 32))
(defstruct log-fields
(f1 0 :type word)
(f2 0 :type word)
(f3 0 :type word))
(defvar *component* (make-log-fields))
(defun compute-1 (lf)
(declare (log-fields lf))
(setf (log-fields-f3 lf)
(logand (log-fields-f1 lf) (log-fields-f2 lf))))
;;; End example code
==== Compiler output for SBCL (0.9.12 Win32/0.9.15 Debian ====
; in: DEFUN COMPUTE-1
; (SETF (LOG-FIELDS-F3 LF) (LOGAND (LOG-FIELDS-F1 LF)
(LOG-FIELDS-F2 LF)))
; --> LET* MULTIPLE-VALUE-BIND LET FUNCALL SB-C::%FUNCALL
; --> #<SB-C::GLOBAL-VAR :%SOURCE-NAME (SETF LOG-FIELDS-F3) :TYPE
#<SB-KERNEL:FUN-TYPE (FUNCTION ((SIGNED-BYTE 32) LOG-FIELDS) (VALUES
(SIGNED-BYTE 32) &OPTIONAL))> :WHERE-FROM :DECLARED :KIND
:GLOBAL-FUNCTION {A746FA9}>
; --> LET LET
; ==>
; (SB-KERNEL:%INSTANCE-SET (THE LOG-FIELDS #:ONCE-ONLY-65)
; 3
; (THE WORD #:ONCE-ONLY-64))
;
; note: doing signed word to integer coercion (cost 20), for:
; the third argument of INSTANCE-INDEX-SET
==== End compiler output ====
With the previous problem, I could at least try to make an educated
guess, but in this case I am completely puzzled.
I know that the boolean operators are a little different from what I
expect from boolean operators, eg. that (lognot #b1111) yields
'#b10000.
Is my problem an instance of this ? However, even when I try to mask
out the most significant bits, I still get the same problem.
Is there somewhere a Wiki where such problems are/can be described ? I
suppose I am not the first one to bump into these problems.
Regards,
Jurgen
jurgen_defurne <··············@pandora.be> wrote:
> My next problem has to do with logical operations.
>
> ;;; Begin example code
>
> (declaim
> (optimize (compilation-speed 0) (speed 3)))
>
> (deftype word ()
> `(signed-byte 32))
>
> (defstruct log-fields
> (f1 0 :type word)
> (f2 0 :type word)
> (f3 0 :type word))
SBCL doesn't support storing signed words as raw (unboxed) defstruct
slots, just unsigned words, floats and complex numbers. So if you try
to store a (signed-byte 32) that's not a fixnum into one of those
slots, it'll have to be stored as a boxed bignum.
If you're just going to store homogenous data in the structure, you
can instead define that as:
(defstruct (log-fields (:type (vector (signed-byte 32))))
...)
Or you can apply the following patch and recompile SBCL to add support
for raw signed word defstruct slots. I think there's no deeper reason
for them not being included, it's just that nobody has had any need
for them before now.
Index: src/code/defstruct.lisp
===================================================================
RCS file: /cvsroot/sbcl/sbcl/src/code/defstruct.lisp,v
retrieving revision 1.82
diff -u -r1.82 defstruct.lisp
--- src/code/defstruct.lisp 7 Apr 2006 11:41:46 -0000 1.82
+++ src/code/defstruct.lisp 31 Aug 2006 12:26:18 -0000
@@ -190,11 +190,12 @@
;;
;; If this object describes a raw slot, this value is the type of the
;; value that the raw slot holds.
- (raw-type t :type (member t single-float double-float
- #!+long-float long-float
- complex-single-float complex-double-float
- #!+long-float complex-long-float
- sb!vm:word))
+ (raw-type t :type (or (member t single-float double-float
+ #!+long-float long-float
+ complex-single-float complex-double-float
+ #!+long-float complex-long-float
+ sb!vm:word)
+ (cons (member signed-byte) t)))
(read-only nil :type (member t nil)))
(def!method print-object ((x defstruct-slot-description) stream)
(print-unreadable-object (x stream :type t)
@@ -247,6 +248,9 @@
(make-raw-slot-data :raw-type 'sb!vm:word
:accessor-name '%raw-instance-ref/word
:n-words 1)
+ (make-raw-slot-data :raw-type '(signed-byte #.sb!vm::n-word-bits)
+ :accessor-name '%raw-instance-ref/word
+ :n-words 1)
(make-raw-slot-data :raw-type 'single-float
:accessor-name '%raw-instance-ref/single
;; KLUDGE: On 64 bit architectures, we
--
Juho Snellman
Juho Snellman wrote:
>
> SBCL doesn't support storing signed words as raw (unboxed) defstruct
> slots, just unsigned words, floats and complex numbers. So if you try
> to store a (signed-byte 32) that's not a fixnum into one of those
> slots, it'll have to be stored as a boxed bignum.
>
Yes, this helps, redeclaring my fields as (unsigned-byte 32) removes
this warning. Of course, this has other consequences, which are also
warnings.
The clue is probably to try not be too a perfectionist, remove more
severe warnings and try to live with the other warnings.
I am simulating logical components on the signal level, and for me the
source of a signal should always be 32 bits (which may or may not be
used like that, depending on its interpretation : memory cell, register
or just a line which gives a 0 or a 1).
To summarise :
- If I use (unsigned-byte 32) then I can do logical operations without
much problems (occasionally using a '#FFFFFFFF for anding out
intermediate results (but is it necessary when doing LOG operations on
unsigned values ?)).
- I can suppress return values from being coerced to integers by not
providing return values.
- I will have to live with the warnings about coercion from
(unsigned-byte 32) to integer if I need return values, but if I inline
these functions, they should functionally pass an unboxed 32-bit word,
if I understand the terminology correctly.
Well, up to the next problem, about vectors not being simple-arrays,
but I think I can solve these on my own.
Regards,
Jurgen
From: Christophe Rhodes
Subject: Re: Adding typedeclarations to SBCL for optimisations
Date:
Message-ID: <sqzmdkoatq.fsf@cam.ac.uk>
"jurgen_defurne" <··············@pandora.be> writes:
> To summarise :
>
> - If I use (unsigned-byte 32) then I can do logical operations without
> much problems (occasionally using a '#FFFFFFFF for anding out
> intermediate results (but is it necessary when doing LOG operations on
> unsigned values ?)).
It is unnecessary if the compiler can prove that the higher bits in
the intermediate results are not used.
For example,
(defun foo (x y z)
(declare (type (unsigned-byte 32) x y z))
(logand x (logxor y (lognot z))))
Even though the (lognot z) call would in principle return a
(signed-byte 33) quantity, the outer (logand x ...) enables the
compiler to derive that the 33rd bit is never significant to the final
result of the function, so you get the (somewhat dubious) disassembly
of
; 0BC: F7D0 NOT EAX
; 0BE: 8BD7 MOV EDX, EDI
; 0C0: 31C2 XOR EDX, EAX
; 0C2: 8BCB MOV ECX, EBX
; 0C4: 21D1 AND ECX, EDX
for the meat of the function.
> - I can suppress return values from being coerced to integers by not
> providing return values.
Right. :-)
> - I will have to live with the warnings about coercion from
> (unsigned-byte 32) to integer if I need return values, but if I inline
> these functions, they should functionally pass an unboxed 32-bit word,
> if I understand the terminology correctly.
Right. Once you're certain that your function is as optimized as you
want it, you can suppress any remaining warnings by using the
sb-ext:muffle-conditions declaration, as
(defun foo (x y z)
(declare (sb-ext:muffle-conditions sb-ext:compiler-note))
(declare (optimize speed))
(declare (type (unsigned-byte 32) x y z))
(logand x (logxor y (lognot z))))
Christophe
>
> Right. Once you're certain that your function is as optimized as you
> want it, you can suppress any remaining warnings by using the
> sb-ext:muffle-conditions declaration, as
>
> (defun foo (x y z)
> (declare (sb-ext:muffle-conditions sb-ext:compiler-note))
> (declare (optimize speed))
> (declare (type (unsigned-byte 32) x y z))
> (logand x (logxor y (lognot z))))
>
How do I make this code compile with CLisp :
'There is no package "SB-EXT"'
Regards,
Jurgen
"jurgen_defurne" <··············@pandora.be> writes:
>>
>> Right. Once you're certain that your function is as optimized as you
>> want it, you can suppress any remaining warnings by using the
>> sb-ext:muffle-conditions declaration, as
>>
>> (defun foo (x y z)
#+sbcl
>> (declare (sb-ext:muffle-conditions sb-ext:compiler-note))
>> (declare (optimize speed))
>> (declare (type (unsigned-byte 32) x y z))
>> (logand x (logxor y (lognot z))))
>>
>
> How do I make this code compile with CLisp :
>
> 'There is no package "SB-EXT"'
--
__Pascal Bourguignon__ http://www.informatimago.com/
Pour moi, la grande question n'a jamais �t�: �Qui suis-je? O� vais-je?�
comme l'a formul� si adroitement notre ami Pascal, mais plut�t:
�Comment vais-je m'en tirer?� -- Jean Yanne
Juho Snellman <······@iki.fi> wrote:
> Or you can apply the following patch and recompile SBCL to add support
> for raw signed word defstruct slots.
Never mind, that one actually that won't work correctly.
--
Juho Snellman