[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: masinter.pa@xerox.com*Subject*: FIXNUM's aren't Bogus!*From*: Jon L White <edsel!jonl@labrea.stanford.edu>*Date*: Fri, 22 Jul 88 06:40:17 PDT*Cc*: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, sandra%cdr@cs.utah.edu, cl-cleanup@sail.stanford.edu*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 instruction. 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" indexing registers. 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: sxxx...xx0...0 (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.

**References**:**Re: more on BOGUS-FIXNUMS***From:*masinter.pa@Xerox.COM

- Prev by Date:
**Re: Issue: PATHNAME-COMPONENT-CASE (Version 1)** - Next by Date:
**Re: more on BOGUS-FIXNUMS** - Previous by thread:
**Re: more on BOGUS-FIXNUMS** - Next by thread:
**Re: more on BOGUS-FIXNUMS** - Index(es):