In article <··········@coils.cims.nyu.edu> ········@coils.cims.nyu.edu (Mark McConnell) writes:
>
>I just ran some experiments to see how the Austin Kyoto Common Lisp
>(AKCL) compiler would handle declarations. I used programs which do a
>lot of addition of fixnums modulo a small integer p. Surprisingly,
>declaring the numbers to be fixnums make the compiled code run 17%
>slower.
>==========
>Even if you tell the compiler that A and B are fixnums, it can't be
>sure that A+B will be a fixnum.
You should say (the fixnum (+ ...)).
> Therefore, I redid the experiment by
>replacing the variable p with 2 throughout the code (removing it from
>argument lists where necessary), and declaring the numbers to be (mod
>2). Version 2 of the program became version 2', as follows:
>
>(proclaim '(optimize (speed 3)))
>(proclaim '(inline pascal-aux2)) ; doesn't matter much if either
> ; auxiliary is inline?
>
>(defun pascal (n)
> (pascal-aux n '(1)))
>
>(defun pascal-aux (n ans)
> (declare (type fixnum n))
> (if (zerop n)
> ans
> (pascal-aux (1- n) (pascal-aux2 ans '(1)))))
>
>(defun pascal-aux2 (in out)
> (if (null (cdr in))
> (cons 1 out)
> (pascal-aux2 (cdr in)
> (cons (mod (+ (the (mod 2) (car in))
> (the (mod 2) (cadr in)))
> 2)
> out))))
>
>Version 1' is the same as version 2', but with no declarations or
>proclamations. Version 1' ran almost exactly as fast as version 1:
>359.8 secs. Version 2' was only a hair faster than version 2, at
>414.8 secs (versus 420.4). Version 1' still beats version 2'.
>
>==========
>
>Does anyone know what is going on? Is there are better way to do
>these declarations? Or does this simply reflect an idiosyncracy in
>the compiler? Do other compilers, such as CMU CL, have the same
>property?
When you declare a variable to be of type fixnum in KCL, it will
prbably be stored in a C int as an actual int. Normally, fixnums
are allocated on the heap inside some stuff that says they're
fixnums. This is sometimes called being "boxed", perhaps from
the way list are sometimes diagrammed using boxes and arrows.
Declaring the var to be a fixnum changes the way it's
stored so that you don't have to repeatedly extract it from
the heap structure. On the other hand, if you need the heap
version it has to be constructed. So that's happening when
you call pascal-aux2 from pascal-aux.
Within pascal-aux2, you're doing + and mod without any declarations
to say fixnums are involved. So you don't get any compensating
speedup for the slowdowns introduced as described above.
I'm not sure that's all there is to it, but it's pretty easy for
you to see what KCL's doing by calling disassemble on a fn that's
not compiled.
In some Common Lisps, you could do better by making the aux
functions local functions defined by LABELS and declaring their
type or by having a top-level PROCLAIM that gave their type
(w/o making them local functions). Either of these might
eliminate the need to convert fixnums stored as ints to their
"boxed" heap forms when calling one of the functions so defined.
I'm not sure how much AKCL does with that kind of thing these days.
-- jeff
From: Scott McLoughlin
Subject: Re: AKCL: declare makes it worse??
Date:
Message-ID: <uLDosc2w165w@sytex.com>
····@aiai.ed.ac.uk (Jeff Dalton) writes:
>
> When you declare a variable to be of type fixnum in KCL, it will
> prbably be stored in a C int as an actual int. Normally, fixnums
> are allocated on the heap inside some stuff that says they're
> fixnums. This is sometimes called being "boxed", perhaps from
> the way list are sometimes diagrammed using boxes and arrows.
>
Howdy,
Boxed fixnums. Is this typical? I've always assumed
(I know ass-u-me) that fixnum would give me something like
III...IIttt, where ttt are low bit tags and III's are bits
for the fixnum (or swap high/low bits for high bit tagging
schemes). Using 000 for ttt can even allow fast fixnum.+
with no tag extracting shifts. Boxed fixnums? Hmmm... Why?
=============================================
Scott McLoughlin
Conscious Computing
=============================================
Scott McLoughlin <····@sytex.com> wrote:
>Boxed fixnums. Is this typical? Why?
I think the term "boxing" generally means taking a raw bits
representation of an object and creating something that can be
identified later. This definition subsumes both pointer-tagging and
(tagged) heap allocation. So as to avoid this semantic quibble I'll
refer to what you mean here as "heap-consing."
Most implementations that I can think of use some pointer tagging or
BiBoP scheme. But not all of them. Reasons to heap-cons fixnums:
1. It's easier to implement: You can treat all objects the same way
and so don't have to worry about special cases.
2. It's more portable. For C-based implementations in particular.
Fiddling around with bits in pointers is not portable C, though it
happens to work for many byte-addressed flat memory machines. It
doesn't have to work on word-addressed or structured memory machines.
3. The intended applications may not care about fixnum arithmetic, so
why bother optimizing an unimportant special case.
Of course, if you really do care about fixnum arithmetic performance,
it is worth it to work hard to avoid heap-consing fixnums.
--David Gadbois