10.2.2 Faster Integers

Unfortunately, the above representation has a serious disadvantage. In order to return an integer, an expression must allocate a struct value, initialize it to represent that integer, and return a pointer to it. Furthermore, fetching an integer’s value requires a memory reference, which is much slower than a register reference on most processors. Since integers are extremely common, this representation is too costly, in both time and space. Integers should be very cheap to create and manipulate.

One possible solution comes from the observation that, on many architectures, heap-allocated data (i.e., what you get when you call malloc) must be aligned on an eight-byte boundary. (Whether or not the machine actually requires it, we can write our own allocator for struct value objects that assures this is true.) In this case, the lower three bits of the structure’s address are known to be zero.

This gives us the room we need to provide an improved representation for integers. We make the following rules:

• If the lower three bits of an SCM value are zero, then the SCM value is a pointer to a struct value, and everything proceeds as before.
• Otherwise, the SCM value represents an integer, whose value appears in its upper bits.

Here is C code implementing this convention:

enum type { pair, string, vector, ... };

typedef struct value *SCM;

struct value {
  enum type type;
  union {
    struct { SCM car, cdr; } pair;
    struct { int length; char *elts; } string;
    struct { int length; SCM  *elts; } vector;
    ...
  } value;
};

#define POINTER_P(x) (((int) (x) & 7) == 0)
#define INTEGER_P(x) (! POINTER_P (x))

#define GET_INTEGER(x)  ((int) (x) >> 3)
#define MAKE_INTEGER(x) ((SCM) (((x) << 3) | 1))

Notice that integer no longer appears as an element of enum type, and the union has lost its integer member. Instead, we use the POINTER_P and INTEGER_P macros to make a coarse classification of values into integers and non-integers, and do further type testing as before.

Here’s how we would answer the questions posed above (again, assume x is an SCM value):

• To test if x is an integer, we can write INTEGER_P (x).
• To find its value, we can write GET_INTEGER (x).
• To test if x is a vector, we can write:

    POINTER_P (x) && x->type == vector
  

  Given the new representation, we must make sure x is truly a pointer before we dereference it to determine its complete type.

• If we know x is a vector, we can write x->value.vector.elts[0] to refer to its first element, as before.
• If we know x is a pair, we can write x->value.pair.car to extract its car, just as before.

This representation allows us to operate more efficiently on integers than the first. For example, if x and y are known to be integers, we can compute their sum as follows:

MAKE_INTEGER (GET_INTEGER (x) + GET_INTEGER (y))

Now, integer math requires no allocation or memory references. Most real Scheme systems actually implement addition and other operations using an even more efficient algorithm, but this essay isn’t about bit-twiddling. (Hint: how do you decide when to overflow to a bignum? How would you do it in assembly?)

This document was generated on February 3, 2012 using texi2html 5.0.