goodhart@noscvax.UUCP (Curtis L. Goodhart) (05/15/85)
Anybody have any pointers to some good references about lisp machine
architecture; ie why isn't a conventional computer suitable for running
lisp?
Thanks,
Curt Goodhart (goodhart@nosc ; on the arpanet)barmar@mit-eddie.UUCP (Barry Margolin) (05/16/85)
If you want information on why special hardware is extremely useful (but
not necessary) for running Lisp, see the proceedings of the various
Conferences on Lisp and Functional Programming, which were held in the
summers of 1980, 1982, and 1984. There were papers presented at each of
these conferences on Lisp Machine architectures. These proceedings can
be obtained from ACM Publications Service, for around $20 each.
There also have been ACM conferences on architectures for programming
languages, but I don't recall the exact name of the conferences. I
haven't read any proceedings, but I do recall some lisp machine
designers being involved in such a conference.
--
Barry Margolin
ARPA: barmar@MIT-Multics
UUCP: ..!genrad!mit-eddie!barmarhenry@utzoo.UUCP (Henry Spencer) (05/17/85)
In the recent AI issue of Byte, there was an article by some folks at a
company (Fairchild?) that is looking at building a super-fast AI machine.
Their analysis of supporting AI languages (notably Lisp) really well on
conventional machines ultimately boiled down to "efficient simulation of
tagged memory is the major stumbling block". Their conclusion was that
conventional machines will be good for Lisp etc. in direct proportion to
how quickly they can (a) pick out some bits from a word and branch to one
of several places depending on the value of those bits, and (b) do an
indirect fetch which ignores some of the bits in the address register.
For example, the original 68000 is good for (b), since it ignores the top
8 bits of an address value, but its bit-extraction facilities are poor
which hurts (a). The 68020 has better bit extraction but hits problems
on (b), since it tries to use a full 32-bit address. And so forth.
I am not up on the intricacies of Lisp machines, but this article made sense.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henryshebs@utah-cs.UUCP (Stanley Shebs) (05/20/85)
In article <5604@utzoo.UUCP> henry@utzoo.UUCP (Henry Spencer) writes: >In the recent AI issue of Byte, there was an article by some folks at a >company (Fairchild?) that is looking at building a super-fast AI machine. >Their analysis of supporting AI languages (notably Lisp) really well on >conventional machines ultimately boiled down to "efficient simulation of >tagged memory is the major stumbling block". Their conclusion was that >conventional machines will be good for Lisp etc. in direct proportion to >how quickly they can (a) pick out some bits from a word and branch to one >of several places depending on the value of those bits, and (b) do an >indirect fetch which ignores some of the bits in the address register. This is true only if one has a relatively stupid compiler that does no type inference of any sort (sadly, this is the case for most compilers today). The nice thing about a really high-level language is that a compiler can look at something like (car quux) and turn that into a single instruction that does offset addressing without any tag checking at all! Of course, the compiler has to be smart, so that it doesn't try that trick with (car 12)... Compiled PSL code wins big because it sacrifices some reliability and debuggability of code for speed. Also, to get the best performance, one must use several kinds of declarations and flags. The net effect is to compile away a large percentage of function calls and type checks. The moral? Fixing the compiler is a better approach than sinking millions of dollars into hardware, then trying to sell it as an "advanced AI engine" or "powerful Lisp machine"... stan shebs
barmar@mit-eddie.UUCP (Barry Margolin) (05/21/85)
In article <3345@utah-cs.UUCP> shebs@utah-cs.UUCP (Stanley shebs) writes: >... Compiled PSL code wins >big because it sacrifices some reliability and debuggability of code >for speed. Also, to get the best performance, one must use several >kinds of declarations and flags. The net effect is to compile away >a large percentage of function calls and type checks. But Lisp Machines provide all the type checking WITHOUT sacrificing efficiency. For instance, the hardware that implements the "+" function on a Symbolics 3600 does all the following things IN PARALLEL: 1) Direct the top two items on the stack to the fixed-point addition circuit. 2) Direct the top two items on the stack to the floating-point addition unit. 3) Check the type bits of the top two items on the stack. If they are both fixna then the result of (1) will be used; if they are both flonums then the result of (2) will be used as the result; and in any other case an exception will be generated, and the addition will be performed by appropriate microcode routines. The point is that on a Lisp Machine you don't sacrifice any type checking in order to get optimal performance. If you are adding two fixna then it takes just as long as a fixed point addition instruction on any other machine. In order to get all the checking that the Lisp Machine implements on conventional hardware you would have to slow down the code for "+" by a factor of two or three; for this reason, most Lisp cmpilers for conventional machines don't generate type checking code, and users must use the interpreter to get this checking. Most Lisp Machine programmers I know do all their debugging on compiled code, which would be unthinkable on most other systems. Another place where special hardware can be a big win is in garbage collection. I won't go into details here; see the paper titled something like "Garbage Collection in Large Address Spaces", by David Moon of Symbolics, in the Proceedings of the 1984 ACM Symposium on Lisp and Functional Programming. -- Barry Margolin ARPA: barmar@MIT-Multics UUCP: ..!genrad!mit-eddie!barmar
rggoebel@water.UUCP (Randy Goebel LPAIG) (05/22/85)
> ... Compiled PSL code wins > big because it sacrifices some reliability and debuggability of code > for speed... > > stan shebs Admittedly taken out of context, but I'm amazed that anyone would sacrifice reliability for speed? Randy Goebel Waterloo
shebs@utah-cs.UUCP (Stanley Shebs) (05/22/85)
In article <4314@mit-eddie.UUCP> barmar@mit-eddie.UUCP (Barry Margolin) writes: >The point is that on a Lisp Machine you don't sacrifice any type >checking in order to get optimal performance. If you are adding two >fixna then it takes just as long as a fixed point addition instruction >on any other machine. In order to get all the checking that the Lisp >Machine implements on conventional hardware you would have to slow down >the code for "+" by a factor of two or three; for this reason, most Lisp >cmpilers for conventional machines don't generate type checking code, >and users must use the interpreter to get this checking. Most Lisp >Machine programmers I know do all their debugging on compiled code, >which would be unthinkable on most other systems. I don't know why debugging compiled code is such a wonderful thing; object code (even on a LM) is not particularly readable. With the interpreter you can see exactly what is being executed. While runtime type checking does increase robustness, it's usually an incredible waste of resources; 99.99999% of type tests will return a result that is knowable in advance (the remaining .00001% are bug detections). There are better ways to ensure robustness; after all, we don't put usually put checksums with every byte on the tape. In general, I tend to object to doing complex operations (like typechecking) in hardware - it's just too inflexible. Does anybody really believe that the primitive types in Zetalisp are worth wiring into the machine (or even the microcode)? >Another place where special hardware can be a big win is in garbage >collection. I agree, but a GC coprocessor is really all you need. Actually, it would be better just to have a vanilla multiprocessor, and run GC tasks concurrently with computation tasks, but that's still in research! stan shebs
barmar@mit-eddie.UUCP (Barry Margolin) (05/23/85)
In article <3346@utah-cs.UUCP> shebs@utah-cs.UUCP (Stanley shebs) writes: >I don't know why debugging compiled code is such a wonderful thing; >object code (even on a LM) is not particularly readable. With the >interpreter you can see exactly what is being executed. The Lisp Machine compiler puts enough information in compiled code so that it is easy to relate to its source code. For instance, variable names are still available when debugging compiled code. When a function stops with an error there is not much more that you can do with it if it is being interpreted than if it is being executed from compiled code. > While runtime >type checking does increase robustness, it's usually an incredible >waste of resources; 99.99999% of type tests will return a result that >is knowable in advance (the remaining .00001% are bug detections). Not in a language that provides generic operations but doesn't require type declarations (see below); in this case, the type-checking is necessary in order to dispatch. By the way, about half the bug reports that I see being sent from MIT Lisp Machine users are generated because the software made an error that would not be caught by most compiled Lisp implementations: array bounds and argument types; similar bugs in Multics Emacs (written in Maclisp) generally cause random errors (like faults during GC) to start occurring. Personally, I prefer it when software stops as soon as the bug occurs, rather than waiting until twenty minutes later. Of course, the best thing is for the code not to have any bugs, but that is not an option as long as people are doing the programming. >There are better ways to ensure robustness; after all, we don't put >usually put checksums with every byte on the tape. How about parity bits? Or ECC bits in every word of memory? Is there that much of a leap from ECC that checks that the memory word is correct to tag bits that are used to check that the triple (operation,arg1,arg2) is correct? I don't think so. >In general, I tend to object to doing complex operations (like typechecking) >in hardware - it's just too inflexible. The alternatives are either (1) doing type checking in software or (2) adding type declarations to programs. For those of you who think I should add (3) do code analysis that determines the parameter types, please explain how a compiler is to perform such an analysis when the entire compilation unit contains a single function definition such as: (defun sample-function (arg1 arg2) (sample-function-2 (+ arg1 arg2)) Without the user adding type declarations, as in (defun sample-function (arg1 arg2) (declare (fixnum arg1 arg2)) (sample-function-2 (+ arg1 arg2)) (or the implicit declaration facility, such as Maclisp's +/+$/plus distinction) there is no way for the compiler to know that it can compile the (+ arg1 arg2) into a simple ADD instruction. >>Another place where special hardware can be a big win is in garbage >>collection. > >I agree, but a GC coprocessor is really all you need. Actually, it >would be better just to have a vanilla multiprocessor, and run GC >tasks concurrently with computation tasks, but that's still in research! I suggest you read David Moon's "Garbage Collection in a Large Address Space Lisp Implementation", in the Proceedings of the 1984 ACM Symposium on Lisp and Functional Programming. Without special assist it is really hard to prevent the GC from seriously impacting your paging performance, as most GC's need to look at nearly all of virtual memory. The above paper describes the mechanism used in the Symbolics 3600 to implement a very good garbage collector that doesn't need to page in lots of memory. barmar -- Barry Margolin ARPA: barmar@MIT-Multics UUCP: ..!genrad!mit-eddie!barmar
mark@apple.UUCP (Mark Lentczner) (05/23/85)
-=-
I would claim that if 99.999999% of your runtime checks are actually
knowable at compile time then you are not taking advantage of the
polymorphic properties of the system. In the code I've seen and
written for polymorphic systems I'd say that less than 50% of the
checks are knowable at compile time if even that many.
--
--Mark Lentczner
Apple Computer
UUCP: {nsc, dual, voder, ios}!apple!mark
CSNET: mark@Apple.CSNETfaustus@ucbcad.UUCP (Wayne A. Christopher) (05/24/85)
> I don't know why debugging compiled code is such a wonderful thing; > object code (even on a LM) is not particularly readable. With the > interpreter you can see exactly what is being executed. I think that dbx is a pretty useful debugger, and C is compiled. The same sort of debugger cold be run easily for lisp. You have the advantage of not having to worry about things working differently when you are compiled from when you are interpreted, too. > While runtime > type checking does increase robustness, it's usually an incredible > waste of resources; 99.99999% of type tests will return a result that > is knowable in advance (the remaining .00001% are bug detections). Really? Say you are doing a lot of high-precision numbers -- how do you know whether you are adding fixnums, bignums, or flonums? You will often have two pointers to something, and want to know whether they point to the "same" thing. What you do depends on whether they point to ints, atoms, or whatever. > In general, I tend to object to doing complex operations (like typechecking) > in hardware - it's just too inflexible. Does anybody really believe > that the primitive types in Zetalisp are worth wiring into the machine > (or even the microcode)? I don't know about Zetalisp, but considering the sorts of worries you have when designing a prolog machine, it certainly is worth the trouble. > I agree, but a GC coprocessor is really all you need. Actually, it > would be better just to have a vanilla multiprocessor, and run GC > tasks concurrently with computation tasks, but that's still in research! I think the point of having special hardward for this is so that you can have extra gc bits along, instead of having to use structs instead of just plain pointers... Wayne
darrelj@sdcrdcf.UUCP (Darrel VanBuer) (05/24/85)
The main reason I debug running compiled code (on Xerox lisp machines) is
the substantial difference in speed between native code and interpretation.
Because the Xerox debugging tools are unable to do much inside compiled
code, I switch back to source for the current problem function only.
[The Xerox break package only works at the point a function is about to be
entered. As a result, inline errors may result in unwinding back to
"before" the error occurred and then breaking.]
--
Darrel J. Van Buer, PhD
System Development Corp.
2500 Colorado Ave
Santa Monica, CA 90406
(213)820-4111 x5449
...{allegra,burdvax,cbosgd,hplabs,ihnp4,orstcs,sdcsvax,ucla-cs,akgua}
!sdcrdcf!darrelj
VANBUER@USC-ECL.ARPAshebs@utah-cs.UUCP (Stanley Shebs) (05/24/85)
In article <4328@mit-eddie.UUCP> barmar@mit-eddie.UUCP (Barry Margolin) writes: >The Lisp Machine compiler puts enough information in compiled code so >that it is easy to relate to its source code. For instance, variable >names are still available when debugging compiled code. When a function >stops with an error there is not much more that you can do with it if it >is being interpreted than if it is being executed from compiled code. In the "primitive" PSL runtime environment, it's possible to edit the expression whose evaluation caused an error, as long as it's interpreted. This is invaluable when fixing nuisance bugs (like mismatched numbers of args). And of course variable names are always available. >>In general, I tend to object to doing complex operations (like typechecking) >>in hardware - it's just too inflexible. > >The alternatives are either (1) doing type checking in software or (2) >adding type declarations to programs. For those of you who think I >should add (3) do code analysis that determines the parameter types, >please explain how a compiler is to perform such an analysis when the >entire compilation unit contains a single function definition such as: > >(defun sample-function (arg1 arg2) > (sample-function-2 (+ arg1 arg2)) > >Without the user adding type declarations, as in > >(defun sample-function (arg1 arg2) > (declare (fixnum arg1 arg2)) > (sample-function-2 (+ arg1 arg2)) > >(or the implicit declaration facility, such as Maclisp's +/+$/plus >distinction) there is no way for the compiler to know that it can >compile the (+ arg1 arg2) into a simple ADD instruction. I exaggerated about the 99.9999%. It's probably more like 99%, in average code; the remaining 1% being operations that are being used in a truly generic way. LM code probably has a higher percentage of generic ops, but examination of the source code suggests to me that many of the generic flavor-mixing operations are gratuituous. On the other hand, ML does full type inference all the time, and I don't know of any inherent reason that Lisp can't do that also. The above example is unrealistic - presumably sample-function and sample-function-2 have a context, and type inference starts from that context. All that can be done with the above example is to infer that sample-function and sample-function-2 return the same type that + does; just a number. >>I agree, but a GC coprocessor is really all you need. Actually, it >>would be better just to have a vanilla multiprocessor, and run GC >>tasks concurrently with computation tasks, but that's still in research! > >I suggest you read David Moon's "Garbage Collection in a Large Address >Space Lisp Implementation", in the Proceedings of the 1984 ACM Symposium >on Lisp and Functional Programming. Without special assist it is really >hard to prevent the GC from seriously impacting your paging performance, >as most GC's need to look at nearly all of virtual memory. The above >paper describes the mechanism used in the Symbolics 3600 to implement a >very good garbage collector that doesn't need to page in lots of memory. I heard the paper, and I read the proceedings, and the paper is a case study rather than a general treatise on the topic. There's not much to convince me that the mechanism is general enough to be useful anywhere else. The idea of several kinds of spaces has been around for awhile, but most of the other details are 3600-specific. It's also not clear to me what the performance results were supposed to prove. stan shebs