Subject: Common Lisp wish list item
From: Erik Naggum <>
Date: 19 Aug 2002 20:50:12 +0000
Newsgroups: comp.lang.lisp
Message-ID: <>

  I really wish fixnums were the natural machine word.

  This may seem a petty concern, but I have recently worked on some algorithms
  that very naturally fit in 32-bit integers (or 16 or 64) and they become so
  much more /understandable/ in Common Lisp than in C, which I thought I could
  still read and write fluently, but my C has evidently become rusty and I
  find myself swearing at the computer when I try to write C again.

  But I am no less frustrated by Common Lisp, whose performance is abysmal due
  to bignum consomania when working with 32-bit numbers because the bignums
  are immutable objects.  I have in fact been sufficiently frustrated that I
  have been thinking about what it would take to implement a Common Lisp that
  used machine integers for integers and did not do any of those stupid
  computer tricks to convert in and out of some other "integer" with spare
  bits.  I used to think that using spare bits was cool, that it was a stupid
  waste to use a byte-adressable hardware when everything you could possibly
  want to address was never smaller than a 4-byte unit, but had to concede
  that I was only pining for the 36-bit processor days.

  The usual way to implement fixnums is to use three "inband bits" to denote
  integer (or two, using one bit for odd or even) and effectively reduce the
  whole machine to one with 1/8th as many real objects as it had addressable
  objects.  That the hardware has 1/8th as much addressable capacity as it has
  address lines is sheer insanity on the part of whoever decided that byte-
  addressability was brilliant.  It is particularly annoying since characters
  should be 16 bits wide, too, and regardless of the character width, you
  should use a byte pointer that would address bytes in a word.  But there I
  go pining for the PDP-10 again.

  Given that we waste 3 bits on the address and they can be used for cool
  things, the decision to reduce the integer value space similarly is a short
  inference step away, but it is wrong.  The right way is to use those three
  bits for type tags (or you could go up to four), and to use an additional
  "out-of-band bit" for the integer/other flag, carried elsewhere when a
  register or other storage held "raw" 32-bit values.  (Like the specialized
  array type for 32-bit values.)

  Naturally, one would have to have boxed integers, too, perhaps even
  interning for integers.  This has been done before, and I recall Kent Pitman
  explaining something about a design for integer-passing failing miserably,
  so I can understand that those who know the past both regard it as folly and
  reject the request to try their ingenuity at this problem.

  However.  I find that my functions either pass integers around a lot or they
  are almost entirely integer-free.  The same goes for floating-point numbers.
  If I want maximal floating-point performance, I can get that with the full
  machine-supported floating-point sizes, but if I can get by without maximal
  performance, I can live with boxed floating-point numbers.  I think the same
  should apply to integers.

  At least one other language (I dare not name it :) uses both immediate and
  boxed integers, but blew it as far as dynamic typing goes.  Common Lisp does
  not need to make the same design mistake.  Boxing and unboxing of integers
  can be made very efficient at the hardware level, and functions that work
  mostly with integer arithmetic should be able to store some information
  useful to the garbage collector about which registers are integers and which
  are pointers without noticeable cost.  I have obviously not worked this out,
  fully, but I am sufficiently peeved by the abbreviated fixnum that I want to
  find out if something like this is doable and what has already been tried
  and considered to have been failures.

Erik Naggum, Oslo, Norway

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.