From: wilson@cs.utexas.edu (Paul Wilson)
Newsgroups: comp.arch
Subject: Re: Ideas for new LISP Machines
Date: 9 Apr 1992 16:00:16 -0500
Organization: CS Dept, University of Texas at Austin
NNTP-Posting-Host: estoril.cs.utexas.edu

In article <SIMON.92Apr2111448@liasg2.epfl.ch> simon@lia.di.epfl.ch (Simon Leinen) writes:
>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).

Yes.  That's important---you want to be able to have overflows into
bignums, rather than either undetected overflows or extra checking
overhead.

>   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.

That's my sense on this.  How hard is it to get people to support
bit addresssing when everybody's supporting byte addressing for
backward compatibility with their 32-bit machines?  What's the
best and/or cheapest approach?

>   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 believe CMU Common Lisp is one system that does these things.

>   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.

A lot of this can be fixed in software, if you're clever.  My (forthcoming)
paper for Lisp and Functional Programming talks about that sort of thing.
You still want a fairly big cache and/or tons of memory bandwidth, though.

>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.

I'd like to see something more like SPECmarks for Lisp.  The Gabriel
benchmarks are interesting for evaluating particular aspects of
Lisp system performance, but they're not nearly as "representative"
of "real" programs as SPECmarks.  (That is, even if I put scare
quotes around those words for SPECmarks, there's still more consensus
about how those numbers relate to "typical" programs.)  The Gabriel
suite hasn't had nearly as much work put into it as SPEC, and its results
are even easier to misinterpret or intentionally abuse.  Definitely not
the kind of numbers you want marketing droids tossing around!  (This is
NOT to say that the Gabriel benchmarks aren't useful, just that you need
to be knowledgeable and careful in interpreting them.)

There's also the problem that the first thing people get running on
a new chip is a good C compiler.  Lisp usually lags well behind that,
so for new chips there's often no way to do the benchmarks with a
hot implementation of LISP.  (There's also not as obviously one
language to use---a Scheme implementation might be faster, given
the same amount of effort, than an implementation of Common Lisp...
but unfortunately Common Lisp is more standard.)

>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. :-)

Yes.  Bob Shaw's thesis from Stanford (Feb 1988) points this out.

(My 1991 SIGPLAN paper also points out that you need to be careful
not to actually store the value cells in hash table order, or it can 
royally screw with your locality;  a copy collector will reach
objects in hash table order and reorder them that way in memory---
pseudo-random order is Not Good for locality.)

>Simon Leinen.
>Laboratoire d'Intelligence Artificielle
>Ecole Polytechnique Federale de Lausanne

   -- PRW

-- 
| Paul R. Wilson, runtime environmentalist          wilson@cs.utexas.edu      |
| U. of Texas Computer Sciences Dept.               voice: (512) 471-9555     |
| Taylor Hall 2.124, Austin, TX 78712-1188          fax:   (512) 471-8885     |
| "Inertia makes the world go 'round."              DoD M.C. # e  (Sz GS450T) |