If you add two FIXNUMs, the result may be a BIGNUM. A
factorial of a FIXNUM may not be a FIXNUM. If I want
maximum performance in cases where I know all types,
how can I declare the type of the result?
Extra variables, like this ?
(DEFUN MULTIPLY-FIXNUMS (X Y)
(LET ((RES 0))
(DECLARE (OPTIMIZE (SPEED 3) (DEBUG 0) (SAFETY 0)))
(DECLARE (FIXNUM RES) (FIXNUM X) (FIXNUM Y))
(SETQ RES (* X Y))))
(DISASSEMBLE 'MULTIPLY-FIXNUMS)
=> do you get simple assembly code here?
(I know there are special functions for FIXNUM arithmetic,
of course. This is just an example)
········@ziplip.com" <·······@ziplip.com> writes:
> If you add two FIXNUMs, the result may be a BIGNUM. A
> factorial of a FIXNUM may not be a FIXNUM. If I want
> maximum performance in cases where I know all types,
> how can I declare the type of the result?
Look up THE in the hyper spec. For example:
(defun multiply-fixnums (x y)
(declare (fixnum x y))
(the fixnum (* x y)))
-Peter
> Extra variables, like this ?
>
> (DEFUN MULTIPLY-FIXNUMS (X Y)
> (LET ((RES 0))
> (DECLARE (OPTIMIZE (SPEED 3) (DEBUG 0) (SAFETY 0)))
> (DECLARE (FIXNUM RES) (FIXNUM X) (FIXNUM Y))
> (SETQ RES (* X Y))))
>
> (DISASSEMBLE 'MULTIPLY-FIXNUMS)
>
> => do you get simple assembly code here?
>
> (I know there are special functions for FIXNUM arithmetic,
> of course. This is just an example)
>
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Note also that CL will likely not automatically do what you want
because of boxing.
> (defun multiply-fixnums (x y)
> (declare (fixnum x y))
> (the fixnum (* x y)))
This looks good at first glance. The problem is that when you call
this function, even though (* x y) is a fixnum, and you've declared it
a fixnum, CL will return this fixnum inside a generic CL "object"
which can hold something of any type, which can hurt you a lot
relative to these small numeric functions. CL has to do this because
it cannot know when it generates the code for multiply-fixnums that
every call to multiply-fixnums expects to get a fixnum back.
One thing that seems like it might help, but won't, is to declare what
the function returns when you call the function:
(let ((foo (the fixnum (multiply-fixnums num1 num2)))))
That this won't help is obvious to the experts, but it "got" me, so
I'll point it out. the reason this can't help you is because the
boxing code is part of the multiply-fixnums functions; to do anything
useful, it would have to modify the code generated for
multiply-fixnums.
If you're using CMUCL, you can get what you want by either declaring
the function to be inline, or by using block compilation (the latter
is basically a guarantee that a given group of functions will only
call each other). If your Lisp compiler can't inline, you can also
play tricks with macros, although I think that is considered somewhat
old-school these days.
Cheers,
rif
In article <···············@five-percent-nation.mit.edu>, rif
<···@mit.edu> wrote:
> Note also that CL will likely not automatically do what you want
> because of boxing.
>
> > (defun multiply-fixnums (x y)
> > (declare (fixnum x y))
> > (the fixnum (* x y)))
>
> This looks good at first glance. The problem is that when you call
> this function, even though (* x y) is a fixnum, and you've declared it
> a fixnum, CL will return this fixnum inside a generic CL "object"
> which can hold something of any type,
No, that's not true. In fact, it's non-sensical. There is no such thing
as "a generic CL 'object' that can hold something of any type."
What is true is that a CL *variable* can hold objects of any type, so if
you store the result of multiply-fixnums in an undeclared variable that CL
will generally not know that the contents of that variable is a fixnum,
because a non-fixnum might be stored there by some other part of the
program.
> which can hurt you a lot
> relative to these small numeric functions. CL has to do this because
> it cannot know when it generates the code for multiply-fixnums that
> every call to multiply-fixnums expects to get a fixnum back.
No. What callers do with the result is irrelevant to the compilation of
multiply-fixnums.
> One thing that seems like it might help, but won't, is to declare what
> the function returns when you call the function:
>
> (let ((foo (the fixnum (multiply-fixnums num1 num2)))))
>
> That this won't help
Because it doesn't guarantee that foo will always hold a fixnum. What you
want is:
(let ((foo (multiply-fixnums num1 num2)))
(declare (fixnum foo))
...
)
> is obvious to the experts, but it "got" me, so
> I'll point it out. the reason this can't help you is because the
> boxing code is part of the multiply-fixnums functions;
No. The reason this won't help is because in your version you've told the
compiler "the thing that I'm putting in this variable now is a fixnum",
but you have not promised that the contents of the variable will always be
a fixnum, which is what you need to promise to get the optimizations you
want.
E.
P.S. Here's what MCL does.
? (defun m-f (x y) (declare (fixnum x) (fixnum y)) (the fixnum (* x y)))
M-F
? (disassemble 'm-f)
(TWNEI NARGS 8)
(MFLR LOC-PC)
(BLA .SPSAVECONTEXTVSP)
(VPUSH ARG_Y)
(VPUSH ARG_Z)
(LWZ NARGS 331 RNIL)
(TWGTI NARGS 0)
(LWZ ARG_Y 4 VSP)
(LWZ ARG_Z 0 VSP)
(SRAWI IMM0 ARG_Z 2)
(MULLW ARG_Z ARG_Y IMM0)
(BA .SPPOPJ)
?
···@jpl.nasa.gov (Erann Gat) writes:
> In article <···············@five-percent-nation.mit.edu>, rif
> <···@mit.edu> wrote:
>
> > Note also that CL will likely not automatically do what you want
> > because of boxing.
> >
> > > (defun multiply-fixnums (x y)
> > > (declare (fixnum x y))
> > > (the fixnum (* x y)))
> >
> > This looks good at first glance. The problem is that when you call
> > this function, even though (* x y) is a fixnum, and you've declared it
> > a fixnum, CL will return this fixnum inside a generic CL "object"
> > which can hold something of any type,
>
> No, that's not true. In fact, it's non-sensical. There is no such thing
> as "a generic CL 'object' that can hold something of any type."
>
> What is true is that a CL *variable* can hold objects of any type,
I think a more genral [sic] answer is that a "Generalized Reference"
http://www.franz.com/support/documentation/6.2/ansicl/section/generali.htm
can hold objects of any type. This would include slots in objects as well
as locations normally only thought of as variables.
> No. What callers do with the result is irrelevant to the compilation of
> multiply-fixnums.
>
> > One thing that seems like it might help, but won't, is to declare what
> > the function returns when you call the function:
> >
> > (let ((foo (the fixnum (multiply-fixnums num1 num2)))))
> >
> > That this won't help
Rif is not necessarily correct.
> Because it doesn't guarantee that foo will always hold a fixnum.
Why not? Assuming that foo is not globally special or closed over, and
is not setq'd or setf'd elsewhere in the code, any good compiler could
infer that the type of foo is fixnum.
> What you want is:
>
> (let ((foo (multiply-fixnums num1 num2)))
> (declare (fixnum foo))
> ...
> )
>
>
> > is obvious to the experts, but it "got" me, so
> > I'll point it out. the reason this can't help you is because the
> > boxing code is part of the multiply-fixnums functions;
>
> No. The reason this won't help is because in your version you've told the
> compiler "the thing that I'm putting in this variable now is a fixnum",
> but you have not promised that the contents of the variable will always be
> a fixnum, which is what you need to promise to get the optimizations you
> want.
Obviously rif's original code was trivial so as to be non-instructive
(the let had no body). But if the body had been given, and if no other
sets of foo were possible, then foo could indeed be limited to fixnum.
--
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 <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
> > Because it doesn't guarantee that foo will always hold a fixnum.
>
> Why not?
Because you have to make additional assumptions before you can conclude
that foo will always hold a fixnum. That is what the phrase "it doesn't
guarantee that foo will always hold a fixnum" means.
> Assuming that foo is not globally special or closed over, and
> is not setq'd or setf'd elsewhere in the code, any good compiler could
> infer that the type of foo is fixnum.
This is tantamount to saying, "if none of the situations under which a
non-fixnum can be placed in foo occur, then one can conclude that foo can
never hold a non-fixnum." That is true, but seems vacuous to me.
> Obviously rif's original code was trivial so as to be non-instructive
> (the let had no body). But if the body had been given, and if no other
> sets of foo were possible, then foo could indeed be limited to fixnum.
If you apply enough assumptions and do enough analysis then you can
conclude that foo will always hold a fixnum (assuming that is in fact the
case) even without any declarations at all.
E.
···@jpl.nasa.gov (Erann Gat) writes:
> In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
>
> > > Because it doesn't guarantee that foo will always hold a fixnum.
> >
> > Why not?
>
> Because you have to make additional assumptions before you can conclude
> that foo will always hold a fixnum. That is what the phrase "it doesn't
> guarantee that foo will always hold a fixnum" means.
>
> > Assuming that foo is not globally special or closed over, and
> > is not setq'd or setf'd elsewhere in the code, any good compiler could
> > infer that the type of foo is fixnum.
>
> This is tantamount to saying, "if none of the situations under which a
> non-fixnum can be placed in foo occur, then one can conclude that foo can
> never hold a non-fixnum." That is true, but seems vacuous to me.
No more vacuous than how you corrected the OP:
| > (let ((foo (the fixnum (multiply-fixnums num1 num2)))))
| >
| > That this won't help
|
| Because it doesn't guarantee that foo will always hold a fixnum. What you
| want is:
|
| (let ((foo (multiply-fixnums num1 num2)))
| (declare (fixnum foo))
| ...
| )
Your solution no more guarantees that foo is a fixnum than the OP's code.
Why? Because no compiler _must_ trust the declaration; any compiler might
completely ignore it. Because no compiler must _enforce_ the declaration;
a user might violate it. And because interpreters are likely to
do _nothing_ at all with the declaration.
The problem was that the OP was looking for a guarantee, and didn't
get one. You (correctly) nixed the OP's attempt at a guarantee, and
then tried to provide one yourself. There are _no_ guaranteed
declarations, except for SPECIAL and NOTINLINE.
My response was geared toward what the compiler might do, not what the
user can expect. The bottom line is always: ask your vendor.
--
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 <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > In article <·············@beta.franz.com>, Duane Rettig
<·····@franz.com> wrote:
> >
> > > > Because it doesn't guarantee that foo will always hold a fixnum.
> > >
> > > Why not?
> >
> > Because you have to make additional assumptions before you can conclude
> > that foo will always hold a fixnum. That is what the phrase "it doesn't
> > guarantee that foo will always hold a fixnum" means.
> >
> > > Assuming that foo is not globally special or closed over, and
> > > is not setq'd or setf'd elsewhere in the code, any good compiler could
> > > infer that the type of foo is fixnum.
> >
> > This is tantamount to saying, "if none of the situations under which a
> > non-fixnum can be placed in foo occur, then one can conclude that foo can
> > never hold a non-fixnum." That is true, but seems vacuous to me.
>
> No more vacuous than how you corrected the OP:
>
> | > (let ((foo (the fixnum (multiply-fixnums num1 num2)))))
> | >
> | > That this won't help
> |
> | Because it doesn't guarantee that foo will always hold a fixnum. What you
> | want is:
> |
> | (let ((foo (multiply-fixnums num1 num2)))
> | (declare (fixnum foo))
> | ...
> | )
>
> Your solution no more guarantees that foo is a fixnum than the OP's code.
> Why? Because no compiler _must_ trust the declaration; any compiler might
> completely ignore it. Because no compiler must _enforce_ the declaration;
> a user might violate it. And because interpreters are likely to
> do _nothing_ at all with the declaration.
>
> The problem was that the OP was looking for a guarantee, and didn't
> get one. You (correctly) nixed the OP's attempt at a guarantee, and
> then tried to provide one yourself. There are _no_ guaranteed
> declarations, except for SPECIAL and NOTINLINE.
>
> My response was geared toward what the compiler might do, not what the
> user can expect. The bottom line is always: ask your vendor.
I guess the term "guarantee" was misleading. I should have used the word
"promise."
(let ((foo (the fixnum (multiply-fixnums num1 num2)))))
This only promises the compiler that foo will initially contain a fixnum,
not that it will always contain a fixnum.
(let ((foo (multiply-fixnums num1 num2)))
(declare (fixnum foo))
This promises the compiler that foo will always contain a fixnum. (Of
course, you could violate this promise, in which case you must bear the
consequences.)
None of this is guaranteed to have any effect, but AFAIK you are more
likely to get the kind of compiler optimization that the OP was after with
the second idiom than with the first.
E.
My apologies for propagating incorrect information. Just when I
thought I knew something, too.
My own experience has been with trying to optimize functions that
compute with and return double-floats. It seems that the tradeoffs
are different there. Suppose I have:
(defun multiply-double-floats (d1 d2)
(declare (type double-float d1)
(type double-float d2))
(the double-float (* d1 d2)))
In this case, will multiply-double-floats return its results boxed,
unless you somehow inline the function? (I'm not at a machine with CL
right now, so I can't check for myself.)
rif
rif <···@mit.edu> writes:
> My apologies for propagating incorrect information. Just when I
> thought I knew something, too.
>
> My own experience has been with trying to optimize functions that
> compute with and return double-floats. It seems that the tradeoffs
> are different there. Suppose I have:
>
> (defun multiply-double-floats (d1 d2)
> (declare (type double-float d1)
> (type double-float d2))
> (the double-float (* d1 d2)))
>
> In this case, will multiply-double-floats return its results boxed,
> unless you somehow inline the function? (I'm not at a machine with CL
> right now, so I can't check for myself.)
I think it would be best to stay with "consing" and "tagging" terminology
for precision. Whether or not you think of a fixnum as boxed, both
fixnums and double-floats must normally be tagged values when returned
from a function. Tagging a fixnum is trivial - either the operation had
been performed on the fixnum in its tagged form, or the machine-integer
must simply be shifted (in most CLs) to get a fixnum without consing.
However, a double-float is too big to fit into a 32-bit tagged LispVal,
and so its "box" must be a heap-allocated object (itself tagged) into
which the result goes. Reuse of these "boxes" is not normal, because
it is not known to what extent the usage lasts (we leave that to the
garbage-collector to decide) and so a fresh box is consed each time for
a new value, unless the boxed values are cached in some way.
So it seems your major concern is with consing, not boxing, per se.
To throw a wrench into this - it is possible in Allegro CL to call
and to return from a lisp function with unboxed (machine-value/untagged)
values. The function must be properly declared, and it has some
non-lispy semantics regarding redefinition, but it is possible to
create functions which can be called in boxed or unboxed manner.
Other lisp implementations might offer similar techniques using block
compilation, but unfortunately block-compilation tends to close off
any external access to the functions which are being treated specially,
whreas our individual approach allows functions to be called normally
by regular lisp functions as well as specially by lisp functions which
know about the special prototyping of the function being called.
--
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
On 20 Aug 2003 11:00:36 -0700, Duane Rettig <·····@franz.com> wrote:
> To throw a wrench into this - it is possible in Allegro CL to call
> and to return from a lisp function with unboxed
> (machine-value/untagged) values. The function must be properly
> declared, and it has some non-lispy semantics regarding
> redefinition, but it is possible to create functions which can be
> called in boxed or unboxed manner. Other lisp implementations might
> offer similar techniques using block compilation, but unfortunately
> block-compilation tends to close off any external access to the
> functions which are being treated specially, whreas our individual
> approach allows functions to be called normally by regular lisp
> functions as well as specially by lisp functions which know about
> the special prototyping of the function being called.
Could you provide a pointer to the part of the AllegroCL docs which
explain this?
Thanks,
Edi,
Edi Weitz <···@agharta.de> writes:
> On 20 Aug 2003 11:00:36 -0700, Duane Rettig <·····@franz.com> wrote:
>
> > To throw a wrench into this - it is possible in Allegro CL to call
> > and to return from a lisp function with unboxed
> > (machine-value/untagged) values. The function must be properly
> > declared, and it has some non-lispy semantics regarding
> > redefinition, but it is possible to create functions which can be
> > called in boxed or unboxed manner. Other lisp implementations might
> > offer similar techniques using block compilation, but unfortunately
> > block-compilation tends to close off any external access to the
> > functions which are being treated specially, whreas our individual
> > approach allows functions to be called normally by regular lisp
> > functions as well as specially by lisp functions which know about
> > the special prototyping of the function being called.
>
> Could you provide a pointer to the part of the AllegroCL docs which
> explain this?
There are no official docs yet, and haven't been since its invention
many years ago. The reason for this is that we don't like the non-lispy
nature of the interface - it's similar to defining a foreign function
in some ways. Instead, we've tended toward giving informal docs to
users who ask for them. We do intend to clean up the interface and
document it eventually, but there have always been higher priorities...
There's no reason why I can't provide the doc publically, though, as
long as anyone who reads the page understands that it is not official
documentation and thus the interface will probably change eventually.
It may take a while to propagate through servers, but you should be
able to grab the plaintext file
ftp://ftp.franz.com/pub/duane/immed_args.n
for your reading enjoyment.
--
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
rif <···@mit.edu> writes:
> Note also that CL will likely not automatically do what you want
> because of boxing.
>
> > (defun multiply-fixnums (x y)
> > (declare (fixnum x y))
> > (the fixnum (* x y)))
>
> This looks good at first glance. The problem is that when you call
> this function, even though (* x y) is a fixnum, and you've declared it
> a fixnum, CL will return this fixnum inside a generic CL "object"
> which can hold something of any type, which can hurt you a lot
> relative to these small numeric functions. CL has to do this because
> it cannot know when it generates the code for multiply-fixnums that
> every call to multiply-fixnums expects to get a fixnum back.
This is simply not true. A declaration is a promise to the compiler
that the type declared will be within the range declared. If you
provide a (the fixnum ...) form around a single calculation with fixnum
arguments x and y, then you are making three promises to the compiler:
1. The x argument is a fixnum.
2. The y argument is a fixnum.
3. The result is a fixnum.
Thus, if the compiler is trusting your declarations, it might
completely opencode the operation. Note, of course, that this
only works for a single calculation, or for series of
calculations which continue the declaration chain. So, for
example, if x, y, and z are declared fixnum, then
(the fixnum (* x (* y z)))
would have to generate boxing code, but
(the fixnum (* x (the fixnum (* y z))))
could generate two inline multiply instructions.
Note for example the original defun (with added optimizations to
make the rest of the function entry checks go away) on the x86 in
Allegro CL:
CL-USER(1): (compile
(defun multiply-fixnums (x y)
(declare (optimize speed (safety 0) (debug 0))
(fixnum x y))
(the fixnum (* x y))))
MULTIPLY-FIXNUMS
NIL
NIL
CL-USER(2): (disassemble *)
;; disassembly of #<Function MULTIPLY-FIXNUMS>
;; formals: X Y
;; code start: #x7162e53c:
0: 55 pushl ebp
1: 8b ec movl ebp,esp
3: 56 pushl esi
4: 83 ec 24 subl esp,$36
7: c1 f8 02 sarl eax,$2
10: f7 ea imull edx
12: f8 clc
13: c9 leave
14: 8b 75 fc movl esi,[ebp-4]
17: c3 ret
CL-USER(3):
I think that there is a trivial optimization possible here - on
the x86 integer multiplication is complicated because it requires
specific registers (eax and edx) and so it thinks it needs to create
a stack to handle the overflow, but since the values are already in
the correct registers anyway, there is no need to save stack space.
The results are even more impressive on the Alpha, which does have
an integer multiply instruction, but which has no compilcations as
to where the argumens must go:
CL-USER(2): (disassemble *)
;; disassembly of #<Function MULTIPLY-FIXNUMS>
;; formals: X Y
;; code start: #x3064894c:
0: 4a005790 sra r16,2,r16 X
4: 4e110010 mull r16,r17,r16
8: 47e03404 [bis] mov 1,r4
12: a15e0008 ldl r10,8(r30)
16: 6bfa8001 ret r31,(r26),1
CL-USER(3):
--
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
Obviously, your expertise in this is far superior to mine. However, I
still don't fully understand. I get that the result of (the fixnum (*
x y)) is a fixnum, but what I don't get is how a function that calls
multiply-fixnums avoids boxing/unboxing? What if multiply-fixnums is
passed as a functional argument?
Is there a special property of fixnums that allows one to avoid
boxing/unboxing, or should the same be true of a function like
multiply-double-float?
rif
rif <···@mit.edu> writes:
> Is there a special property of fixnums that allows one to avoid
> boxing/unboxing, or should the same be true of a function like
> multiply-double-float?
Essentially, yes there is. The fixnum type is usually chosen by
implementors to be that integer type that does not need boxing, but is
instead represented as an immediate.
Slightly less short answer (examples from SBCL, but Allegro's fixnums
at least are the same on 32-bit platforms):
fixnum bit pattern: #bXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX00
other immediate bit pattern: #bXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX10
pointer bit pattern: #bXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX1
These are the representations of the lisp objects as binary. So a
fixnum doesn't need boxing, because it's already a lisp object.
Similarly, a character, represented in SBCL by
#b0000000000000000ASCICODE10110010
would not need to be boxed on return from a function. Other objects,
however, including double floats, do in general need to be boxed on
function return unless the function can be inlined.
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:
> rif <···@mit.edu> writes:
>
> > Is there a special property of fixnums that allows one to avoid
> > boxing/unboxing, or should the same be true of a function like
> > multiply-double-float?
>
> Essentially, yes there is. The fixnum type is usually chosen by
> implementors to be that integer type that does not need boxing, but is
> instead represented as an immediate.
It really depends on what your definition of "boxing" is. There are
three factors that go into this issue, and I tend, as an implementor,
to choose the less-used association, because it allows me to think more
clearly about the different compilation issues involved between
LispVal compilation and machine-{integer,float} compilation:
The three pairs of concepts are:
1. Boxing/unboxing: putting values into a "box", whatever that is.
2. Consing/non-consing: does the generation of a value take up
heap space?
3. Tagged/untagged: Is the value recognizable by the gc, or does it
take an anonymous bit pattern that fills up the machine word?
These three concepts are distinct, but most people tend to pair
off items #1 and #2, because consing more obviously affects users
of lisps. And I actually try to avoid using the term "boxing",
because it is not very well defined - in conversations about consing
issues, I try to always use the term "consing" and in conversations
about tagged compilation vs native machine value compiltion, I try to
use "tagged vs untagged or machine-value" terminology.
That said, one could make a case for pairing off #1 with #3, instead.
What that means is that heap-allocated objects are thought of in the
same way as before, but immediates are considered boxed if they are
tagged. Thus, a fixnum is a cons-free box, into which a small integer
is placed. Boxing an immediate integer into a fixnum is easy in most
current CL implementations: it simply involves a shift of 2 or 3,
depending on the bit size of the lisp.
It also helps to answer rif's question more precisely, by saying:
1. The fixnum values are already in boxed form, but not consed
(on the heap).
2. If the operation had been an addition, there would be no
need to unbox the values at all; a fixnum plus a fixnum can be
punned in machine code as a simple add; the result is an
already-boxed fixnum (assuming, of course, that the promise of
the declaration held and no overflow occurred).
3. In a pure-fixnum multiply, the simple algorithm is to unbox
(shift right) one of the fixnums, and a punned multiply instruction
yields an already-boxed fixnum result.
Pairing off #1 and #3 also simplifies the concepts invloved with
distinguishing array accesses on (array t) from those on
specialized arrays; if you think of a simple-array with an
element type of t as just a lisp structure, whose elements must be
boxed (i.e. tagged LispVals) and whose elements are unchanged when
accessing from or storing them into the arrays, and specialized
simple-arrays can be thought of simply as boxes for unboxed values
of various sizes. This distinction makes more clear the issue which
often bites users when they try to use svref on a specialized array.
Now that I have written such a long answer, I want to clarify why I
answered you instead of rif directly - It was just one word you
repeated:
> Essentially, yes there is. The fixnum type is usually chosen by
> implementors to be that integer type that does not need boxing, but is
============================================================^
> instead represented as an immediate.
I would have used "consing" here, even though rif used the word boxing,
simply because consing is defined in the CL spec and boxing is not.
--
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 <···············@five-percent-nation.mit.edu>,
rif <···@mit.edu> wrote:
> Note also that CL will likely not automatically do what you want
> because of boxing.
>
> > (defun multiply-fixnums (x y)
> > (declare (fixnum x y))
> > (the fixnum (* x y)))
>
> This looks good at first glance. The problem is that when you call
> this function, even though (* x y) is a fixnum, and you've declared it
> a fixnum, CL will return this fixnum inside a generic CL "object"
> which can hold something of any type, which can hurt you a lot
> relative to these small numeric functions. CL has to do this because
> it cannot know when it generates the code for multiply-fixnums that
> every call to multiply-fixnums expects to get a fixnum back.
There is the possibility to declare the type of the function:
(defun multiply-fixnums (x y)
(declare (ftype (function (fixnum fixnum) fixnum) multiply-fixnums))
...)
See http://www.lispworks.com/reference/HyperSpec/Body/d_ftype.htm#ftype
(Don't know if I've done it correctly in the example above, though.)
Pascal
Pascal Costanza <········@web.de> writes:
> In article <···············@five-percent-nation.mit.edu>,
> rif <···@mit.edu> wrote:
>
> > Note also that CL will likely not automatically do what you want
> > because of boxing.
> >
> > > (defun multiply-fixnums (x y)
> > > (declare (fixnum x y))
> > > (the fixnum (* x y)))
> >
> > This looks good at first glance. The problem is that when you call
> > this function, even though (* x y) is a fixnum, and you've declared it
> > a fixnum, CL will return this fixnum inside a generic CL "object"
> > which can hold something of any type, which can hurt you a lot
> > relative to these small numeric functions. CL has to do this because
> > it cannot know when it generates the code for multiply-fixnums that
> > every call to multiply-fixnums expects to get a fixnum back.
>
> There is the possibility to declare the type of the function:
>
> (defun multiply-fixnums (x y)
> (declare (ftype (function (fixnum fixnum) fixnum) multiply-fixnums))
> ...)
I think it makes more sense to put this into a DECLAIM before the
DEFUN, not?
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
In article <··············@cartan.de>, Nils Goesche <······@cartan.de>
wrote:
> > There is the possibility to declare the type of the function:
> >
> > (defun multiply-fixnums (x y)
> > (declare (ftype (function (fixnum fixnum) fixnum) multiply-fixnums))
> > ...)
>
> I think it makes more sense to put this into a DECLAIM before the
> DEFUN, not?
That I don't know.
There should be an idiot's guide to the proper use of declaim, proclaim
and declare...
Pascal
Pascal Costanza <········@web.de> writes:
> In article <··············@cartan.de>, Nils Goesche <······@cartan.de>
> wrote:
>
> > > There is the possibility to declare the type of the function:
> > >
> > > (defun multiply-fixnums (x y)
> > > (declare (ftype (function (fixnum fixnum) fixnum) multiply-fixnums))
> > > ...)
> >
> > I think it makes more sense to put this into a DECLAIM before the
> > DEFUN, not?
>
> That I don't know.
>
> There should be an idiot's guide to the proper use of declaim,
> proclaim and declare...
In this case, it's about scope. The FTYPE of MULTIPLY-FIXNUMS will
probably be interesting everywhere this function is used, so you
establish a global declaration with DECLAIM. An idiot's guide would
probably say ``Never use PROCLAIM��. PROCLAIM is a function, so for
it to take effect you'd have to wrap it into an EVAL-WHEN all the
time, which is easy to forget. DECLAIM does this for you, so you can
just forget about PROCLAIM altogether.
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
In article <··············@cartan.de>, Nils Goesche <······@cartan.de>
wrote:
> An idiot's guide would
> probably say ``Never use PROCLAIM��. PROCLAIM is a function, so for
> it to take effect you'd have to wrap it into an EVAL-WHEN all the
> time, which is easy to forget. DECLAIM does this for you, so you can
> just forget about PROCLAIM altogether.
So why does proclaim exist in the first place? Only for historical
reasons, or is there some deeper meaning to it?
Pascal
Pascal Costanza <········@web.de> writes:
> In article <··············@cartan.de>, Nils Goesche <······@cartan.de>
> wrote:
>
> > An idiot's guide would
> > probably say ``Never use PROCLAIM��. PROCLAIM is a function, so for
> > it to take effect you'd have to wrap it into an EVAL-WHEN all the
> > time, which is easy to forget. DECLAIM does this for you, so you can
> > just forget about PROCLAIM altogether.
>
> So why does proclaim exist in the first place? Only for historical
> reasons, or is there some deeper meaning to it?
It is more functionally primitive. It allows you to globally attach
declarations to newly generated symbols, e.g., so that you can use
EVAL or COMPILE without warnings.
rif <···@mit.edu> writes:
> This looks good at first glance. The problem is that when you call
> this function, even though (* x y) is a fixnum, and you've declared it
> a fixnum, CL will return this fixnum inside a generic CL "object"
Not necessarily. An implementation that uses tagged pointers to its
objects will often (dare I say it, usually) allocate a tag bit (or
two) to fixnums, so they can be represented unboxed. In fact, this is
why fixnums are tyically smaller than the native machine integer:
because the extra bits are needed to indicate that they're fixnums and
not, say, conses or instance pointers.
In this example I defined the range of the inputs more tightly than
'fixnum' so that the compiler can infer the result type will also fit
in fixnum without my needing to lie to it using THE.
* (defun multiply-small-numbers (a b)
(declare (optimize (speed 3))
(type (integer 0 100) a b))
(* a b))
MULTIPLY-SMALL-NUMBERS
* (disassemble *)
; 090C4874: SAR EDX, 2 ; no-arg-parsing entry point
; 77: IMUL EDX, EDI
; 7A: MOV ECX, [EBP-8]
; 7D: MOV EAX, [EBP-4]
; 80: ADD ECX, 2
; 83: MOV ESP, EBP
; 85: MOV EBP, EAX
; 87: JMP ECX
Look, no boxing. Slightly weird function return mechanism, conceded,
but still no calls to allocation routines.
-dan
--
http://www.cliki.net/ - Link farm for free CL-on-Unix resources
rif <···@mit.edu> writes:
> > (defun multiply-fixnums (x y)
> > (declare (fixnum x y))
> > (the fixnum (* x y)))
>
> This looks good at first glance. The problem is that when you call
> this function, even though (* x y) is a fixnum, and you've declared it
> a fixnum, CL will return this fixnum inside a generic CL "object"
> which can hold something of any type, which can hurt you a lot
> relative to these small numeric functions.
Boxing a fixnum is usually just a matter of shifting it by a few bits
(since they are commonly represented as immediate objects with a zero
tag at bottom), so that doesn't hurt much compared to the cost of the
multiplication. However, if the example were talking about any other
numerix type (expect possibly SHORT-FLOATs which are immediate in some
implementations) your remarks would be appropriate, since boxing those
involves allocating a block to hold the value. (And unboxing would
also cost an extra dereference.)
--
Pekka P. Pirinen
Go not to Usenet for help, for it will tell you 'Yes' and 'No' and 'Try
another group'.