Subject: Common Lisp wish list item From: Erik Naggum <erik@naggum.no> Date: 19 Aug 2002 20:50:12 +0000 Newsgroups: comp.lang.lisp Message-ID: <3238779012022126@naggum.no> 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.