From: simon@lia.di.epfl.ch (Simon Leinen)
Newsgroups: comp.arch,comp.lang.lisp
Subject: Re: Ideas for new LISP Machines
Date: 2 Apr 92 09:14:48 GMT
Followup-To: comp.arch
Organization: DI-LIA -- Ecole Polytechnique Federale de Lausanne
In-reply-to: wilson@cs.utexas.edu's message of 2 Apr 92 02:42:26 GMT
X-Md4-Signature: 4093cddb618b17186cbd1852c81a753a

In article <ktkt4iINN65g@boogie.cs.utexas.edu> wilson@cs.utexas.edu
(Paul Wilson) writes [lots of highly interesting text deleted]:

   Have a look at the SPARC's tagged arithmetic instructions.  All they
   really do---if I recall correctly---is check to see if the low two
   bits are zeroes, and makes it easy (by setting condition codes?) to
   do a quick branch if they're not.

They also check for over/underflow of the result (adding/substracting
two fixnums may result in a bignum).

   I think that one nice hardware feature would be bit addressing,
   because then we could steal 10 low-order bits instead of just 2,
   and use more patterns for tags.  That's not likely, though, because
   the world pretty much assumes C pointers-to-character these days.

The transition to 64bit-addressing that has just started seems like a
good opportunity to convince chip designers that this makes sense.

   And 2 bits actually is adequate, if not ideal---it lets you
   distinguish between pointers, immediate integers, and a couple of
   other things.  For further discriminations, you can consult object
   headers.

By "careful choice of tag values" you can encode seven types directly
using the three least significant bits as tag (000 and 100 are the
resp. typecodes for "even fixnum" and "odd fixnum").  That fits nicely
with an 8-byte granularity of indirect objects on byte-address
machines.  You also can align symbols and conses so that (CAR NIL) and
(CDR NIL) evaluate to NIL using normal low-level CONS access...

   I think it's probably better to focus on better OS support and
   software techniques than on specialized hardware.  For example, you
   can do wonderful things with virtual memory protections, and take
   extra advantage of the parallel checking hardware you've already
   got---the TLB.

   In that respect, conventional architectures are fine, if the pages
   aren't too large.

Good point.  The problem with conventional architectures is not so
much that they are missing support in form of expensive features like
hardware tags etc.  It's rather that the assumptions behind the
existing cache and VM implementations break down in the case of Lisp
and friends because the access patterns to memory are very different.

Unfortunately I never see Gabriel benchmark times in announcements for
new machines... which leads me to think that Lisp performance is not a
high-priority issue for HW vendors.

Rather than invest in their own hardware development, Lisp
implementors should lobby for reasonable support from the mainstream
hardware vendors.  SPARC's tagged add/sub instructions are an
excellent example here (hopefully not the last one).

I'm also sure that Lisp runtime systems could become a lot nicer with
respect to locality.  (Just one of many wierd examples: every symbol
sould be allocated non-contiguously on two or four or six pages -- one
for the function/value cells, one for the print name/package etc. :-)
-- 
Simon Leinen.
Laboratoire d'Intelligence Artificielle
Ecole Polytechnique Federale de Lausanne
Newsgroups: comp.arch