[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
FIXNUM's aren't Bogus!
- To: email@example.com
- Subject: FIXNUM's aren't Bogus!
- From: Jon L White <firstname.lastname@example.org>
- Date: Fri, 22 Jul 88 06:40:17 PDT
- Cc: email@example.com, firstname.lastname@example.org, email@example.com
- In-reply-to: masinter.pa@Xerox.COM's message of 21 Jul 88 12:56 PDT <880721-125503-4335@Xerox>
re: Xerox Common Lisp has 17-bit fixnums. LISP:MOST-POSITIVE-FIXNUM = 65535,
LISP:MOST-NEGATIVE-FIXNUM = -65536.
This choice is quite arbitrary. FIXNUM is not constrained to mean
"immediate" data type (indeed it was NOT an immediate in PDP10 MacLisp),
and Xerox Lisp's FIXP could just have well been included in its FIXNUM
type; that would have yielded a range of 32 bits rather than 17. At one
time, at least some implementations of Interlisp-D had microcode to cover
the case of FIXP's; so it was a relatively efficient type.
MacLisp may be considered to be the father of the modern FIXNUM -- it
originated the trick of reserving a couple pages of write-protected memory
filled in with a dense neighborhood of integers centered around 0; thus
"consing" a small fixnum didn't require new storage allocations. The
critical meaning for FIXNUM's, however, is not merely that they be "small",
nor that basic operations on them not consume storage, but that they be
operable in a few, fixed number of steps. In fact, in compiled code, the
basic operations (on fixnums) were always one PDP10 instruction [including
the four rationals, shifting, and even HAULONG, the predecessor of CL's
INTEGER-LENGTH. Love that JFFO!] A *uniform* representation for fixnums
was the critical factor in compiling these operations into one machine
The opposite of FIXNUM is thus a datum that falls into the asymptotic
algorithms of "bignums", whose operational timing is proportional to the
length of the numbers involved.
I propose this meaning for FIXNUM: that the basic integer operations
use algorithms that are not proportional to the size of the data; it
should be just about as fast to add numbers in the middle of the fixnum
range as it is to add, say, 10 and 11.
I would _prefer_ that the range of positive FIXNUM's be at least as large
ARRAY-TOTAL-SIZE-LIMIT, so that one can be assured that any legitimate
array index is a FIXNUM. However, I'll admit that this is of more
concern to an implementation on "stock" hardware with "general purpose"
Regarding the portability issues raised by differing FIXNUM ranges --
I agree with all of Jeff Dalton's comments. Championing portability
here is making a mountain of a molehill.
-- JonL --
P.S. A candidate for early fixnums might also be Interlisp-10's assymetric
representation, wherein very small integers were "immediate" and
medium-sized integers fit into one word (maybe Lisp1.5 had a similar
scheme too?). Although operating on such a representation did not
require use of an "asymptotic" algorithm, it did require so much more
time than the PDP10 MacLisp scheme that they were not considered
particularly "efficient" by the relevant community of users. In fact,
just decoding the representation cost a subroutine call. [Who among
us remembers (JSP T, NUMVAL)?]
P.P.S. The more common technique now for representing fixnums is to
notice that on byte-addressed machines (like VAX, MC68000 series,
INTEL 80386, most Risc-type machines, etc.) the low-order two bits
or more of an address are redundant (cons cells requiring at least 4
and probably 8 bytes of memory). So the low-order two or three bits
can be used arbitrarily as datatype tag information, and a prudent
choice of the tag code leads to a very efficient FIXNUM implementation.
Let fixnums have all "low-order" bits zero; thus data in a format like:
(where "s" is a sign bit and the "x"'s are arbitrary bits) will still
be in that format after a machine "longword" addition or subtraction;
and multiplication and division require at most a pre- or post- shift
by a couple bits to retain that format. Hence basic fixnum operations
can still be done in about one machine instruction. [I credit Stallman
with first noticing the immense utility of this fact, back in 1978
when we were brainstorming the design of VAX/NIL]. Despite the vast
difference in implementational "tricks", PDP10 MacLisp and VAX/NIL
share what I condsider to be the fundamental feature: low, constant-
time value for basic operations costs.