Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!ugle.unit.no!ugle.unit.no!haltraet
From: haltraet@gondle.idt.unit.no (Hallvard Traetteberg)
Newsgroups: comp.lang.lisp
Subject: Re: Eternal fixnum question (was Re: GET / GETF warning.)
Message-ID: <HALTRAET.91May1165253@gondle.idt.unit.no>
Date: 1 May 91 14:52:53 GMT
References: <641@zogwarg.etl.army.mil> <4580@skye.ed.ac.uk>
Sender: news@ugle.unit.no
Organization: Norwegian Inst. of Tech., Div. of Computer Syst. and Telematics
Lines: 73
In-Reply-To: jeff@aiai.ed.ac.uk's message of 30 Apr 91 18:08:26 GMT

In article <4580@skye.ed.ac.uk> jeff@aiai.ed.ac.uk (Jeff Dalton) writes:

   As you all will recall, Common Lisp allows EQ to return false
   for fixnums that are EQL.  Indeed, it can do so even in a case
   like this:

   [1]   (let ((x z) (y z)) (eq x y))  ; CLtL II p 288

   or even:

   [2]   (let ((x 5)) (eq x x))        ; CLtL II p 104

   ... we need a different argument to show why [1] or
   [2] might return NIL, because if all fixnums were pointers-to, both
>   [1] and [2] would be true (unless we imagine that merely referring to
>   a fixnum causes a new one to be allocated, an implementation that
>   would be bizarre, to say the least).  Moreover, they would also be
   true if all fixnums were always represented as tagged immediate
   values, because they would have the same tag (fixnum) and the same
   value.  Indeed, it's hard to imagine any reasonable representation
   that, if used for all fixnums, would have [1] or [2] be false.

   -- jd

It may not be all that bizarre always to allocate new fixnum-objects when
referring to then. The whole thing depends on what fixnums are used for.
Consider: 

       (dotimes (a-fixnum *max-fixnum*) <some code>)

This code would generate an enormous amount of garbage fixnums, since one
cannot in general know if the values of a-fixnum are alive e.g put into a
list after the loop. But if one can guarantee that no fixnum-object is shared
between structures, one can always garbage collect fixnum-objects that lose a
(its only) reference. How can an implementor make this guarantee?

The code above may expand to:

     (let ((a-fixnum 0))
       (tagbody #:start <some code>
                        (if (< (setq a-fixnum (1+ a-fixnum)) *max-fixnum*)
                          (go #:start))))

Every time a-fixnum is set, the old fixnum-object that it refered to is
garbage collected. This is safe if a-fixnum is the only reference to the
fixnum-object. And with the above-mentioned guarantee this is true. The
technique is to generate a new fixnum-object every time eval returns a fixnum.
In the loop above, this new object will be the old fixnum-object just garbage
collected. So the total amount of new fixnum-objects allocated in the loop is
very small (2). Compare this with the *max-fixnum* fixnums that must be
allocated without this technique, which would you prefer?

KCL has a fixed set of already-made fixnum-objects that is reused instead of
allocating duplicates. Short loops will thus not generate garbage like the
example above suggests it should. The same trick can be used with the
technique described above to prevent calling the allocator all the time. 

If one writes code that normally generates fixnum-sharing datastructures, the
technique will slow the system down. But if this isn't the case, i believe it
will be considerable faster as long as the implementation optimizes the
recycling of garbage collected fixnums. Also, the technique depends on that
copying fixnums is fast, e.g. one memory read/store. Extending this to bigger
objects than fixnums may not be wise.

I have never tried this although I intended to implement it in a Lisp
interpreter I wrote some years ago. Is this really and old idea that everybody
has thought of, tried and discarded as inefficient? Has anyone experience with
systems implementing it?

                            - haltraet, Norwegian Institute of Technology
--

                                                           - hal