next up previous contents
Next: 5.11.6 Word Integers Up: 5.11 Numbers Previous: 5.11.4 Generic Arithmetic

5.11.5 Fixnums

     

A fixnum is a ``FIXed precision NUMber''. In modern Common Lisp implementations, fixnums can be represented with an immediate descriptor, so operating on fixnums requires no consing or memory references. Clever choice of representations also allows some arithmetic operations to be done on fixnums using hardware supported word-integer instructions, somewhat reducing the speed penalty for using an unnatural integer representation.

It is useful to distinguish the fixnum type from the fixnum representation of integers. In Python, there is absolutely nothing magical about the fixnum type in comparison to other finite integer types. fixnum is equivalent to (is defined with deftype to be) (signed-byte 30). fixnum is simply the largest subset of integers that ıcan be represented using an immediate fixnum descriptor.

Unlike in other Common Lisp compilers, it is in no way desirable to use the fixnum type in declarations in preference to more restrictive integer types such as bit, (integer -43 7) and (unsigned-byte 8). Since Python does understand these integer types, it is preferable to use the more restrictive type, as it allows better type inference (see section 5.3.4.)

The small, efficient fixnum is contrasted with bignum, or ``BIG NUMber''. This is another descriptor representation for integers, but this time a pointer representation that allows for arbitrarily large integers. Bignum operations are less efficient than fixnum operations, both because of the consing and memory reference overheads of a pointer descriptor, and also because of the inherent complexity of extended precision arithmetic. While fixnum operations can often be done with a single instruction, bignum operations are so complex that they are always done using generic arithmetic.

A crucial point is that the compiler will use generic arithmetic if it can't prove that all the arguments, intermediate values, and results are fixnums. With bounded integer types such as fixnum, the result type proves to be especially problematical, since these types are not closed under common arithmetic operations such as +, -, * and /. For example, (1+ (the fixnum x)) does not necessarily evaluate to a fixnum. Bignums were added to Common Lisp to get around this problem, but they really just transform the correctness problem ``if this add overflows, you will get the wrong answer'' to the efficiency problem ``if this add might overflow then your program will run slowly (because of generic arithmetic.)''

There is just no getting around the fact that the hardware only directly supports short integers. To get the most efficient open coding, the compiler must be able to prove that the result is a good integer type. This is an argument in favor of using more restrictive integer types: (1+ (the fixnum x)) may not always be a fixnum, but (1+ (the (unsigned-byte 8) x)) always is. Of course, you can also assert the result type by putting in lots of the declarations and then compiling with safety 0.


next up previous contents
Next: 5.11.6 Word Integers Up: 5.11 Numbers Previous: 5.11.4 Generic Arithmetic

Raymond Toy
Mon Jul 14 09:11:27 EDT 1997