[gclist] Get Real! Require GC (was re: quality of impl., etc.)

[Jeff Barnett]

>> >From nickb@harlequin.co.uk Mon Apr 22 03:55:21 1996
>> >Date: Mon, 22 Apr 1996 09:54:45 +0100
>> >From: Nick Barnes <nickb@harlequin.co.uk>
>> >
>> >Rumour has it that some early Lisp Machines had broken GCs. Unlike
>> >[typical programs in] some other languages, [some typical programs in]
>> >Lisp allocates slowly enough that the absence of a GC used to be
>> >acceptable.
>> 
>> Good point.  As I understand it, the early Lisp Machines had simple
>> GC that was so bad that people would often turn it off, let the machine
>> run until swap space was exhausted, and reboot.
>
>Let's keep things in context.  The early Lisp Machines had very little
>memory -- 2 Mbytes or so -- and had very little control over the placement
>of objects.  Therefore, things like pop-up menus could get paged out and
>cause a lot of paging to get back in.  Thus, due to memory starvation,
>the early Lisp Machines were barely usable at all -- GC or no GC.  
>
>One of the main reasons for developing the MIT Lisp Machine was DEC's
>intransigence about making very large address spaces available for
>single programs.  (Yes, the VAX offered large address spaces, but due
>to its page table structure, it handled large _discontiguous_
>addresses very badly.)  The natural language projects, symbolic
>algebra projects, speech understanding projects, etc., had all run
>into the address space problem.  It is my understanding that the ARPA
>speech understanding project utilized > 10 separate processes running
>on the DEC-20 in order to be able to operate, and everyone agreed that
>huge amounts of time were being wasted 'shoe-horning' large projects
>into small address spaces.

I ran the ARPA specch projects at SDC.  You are indeed correct that
memory & adress management was a big problem.  My group used an IMB
370 but our LISP wasn't up to the task.  Doug Pintar and I did an
implementation called CRISP -- Crunching Lisp -- to solve the problem.
Our 370 had about an 8 m bytes virtual limit and about 4 m bytes real.
CRISP allowed space definitions to be made with "policy functions".
There where several space kinds -- cons cells, arrays, stacks, etc.
The policy functions were mark-an-item, resolve weak link, 
folder(erasurer), slider, updater, clean up.  There was also a conser
called by the user-level conser.  With this setup you could, when you
created a space, choose between folding, erasure lists (with or
without smart consing), copy collecting, etc.  We wrote large speech
systems with pasta-plus stack controlls and moby data.  By being a
little careful, our gc wasn't a resource hog.  Further, our paging
traffic during gc was less than that of the IBM assembler doing anything.
By the way, CRISP ran under VM so there were other users on the machine
time-sharring style.

Interesting result from some experiments:  folding and/or compacting
seemed to be much better than any form of erasure list schemes including
use of smart cons -- mentioned to Danny Bobrow and he hadn't really done
any experiments at the time (didn't talk to Warren Titleman so don't
really know).  Note, we couldn't do a copy collect or incremental
collector since the total address space was so limited.  One other thing,
CRISP was a fully typed (by declaration) language so we could get the
necessary performance for speech processing -- that's where the name
Crunching LISP came from.

Jeff Barnett