Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!rutgers!brl-adm!seismo!rochester!pt.cs.cmu.edu!spice.cs.cmu.edu!ram
From: ram@spice.cs.cmu.edu.UUCP
Newsgroups: comp.lang.lisp
Subject: Re: autoload (was: Re: Against the Tide of Common LISP)
Message-ID: <1141@spice.cs.cmu.edu>
Date: Fri, 20-Feb-87 05:20:51 EST
Article-I.D.: spice.1141
Posted: Fri Feb 20 05:20:51 1987
Date-Received: Sat, 21-Feb-87 06:03:16 EST
References: <2581@well.UUCP> <2582@well.UUCP> <4296@utah-cs.UUCP> <359@bcsaic.UUCP> <148@utah-orion.UUCP>
Organization: Carnegie-Mellon University, CS/RI
Lines: 140

In article <148@utah-orion.UUCP> shebs@utah-orion.UUCP (Stanley T. Shebs) writes:
>In article <359@bcsaic.UUCP> michaelm@bcsaic.UUCP (Michael Maxwell) writes:
>
>>I'm curious: what's the disadvantage (besides the time it takes to do it)
>>of autoloading?

Another point is that unless you are careful to make fasloaded code
shareable, autoloads for popular functions will actually waste memory.  Many
systems make it possible to share the initial read-only portion of a
program, but do not allow shareable reading of files after a program has
started.  If you have a VM system good enough to allow those sorts of games,
then autoloading is probably of dubious benefit.

The system I am most familar with that made extensive use of autoloads was
Maclisp.  In the case of Maclisp, the autoloads were more of a way of
getting around the prohibitively small PDP-10 address space, rather than of
reducing memory usage.

Our approach to building systems here at CMU under Accent and now under Mach
is to put all standard faclilties in the core.  Our cold-load builder 
initially allocates all objects dynamically.  When we build a full system,
we load in the editor, compiler, etc., once again allocating all structures
dynamically.  We then use a GC-like utility called Purify that moves all
accessible objects into statically allocated storage.  Objects that are
obviously unmodifiable such as function constants are moved into a
non-scavenged (unmarked) area, allowing GC to ignore these objects since
they can only point to statically allocated objects that cannot move.

Since Mach supports copy-on-write mapping of files, the entire Lisp image is
initially shareable.  Only as objects are modified do pages become
non-sharable.  Since the bulk of the system is code and strings that are
never modified, even a well-used Lisp is still largely sharable.  I believe
that sharing is important even on single-user machines, since it is often
useful to have several lisps running.

Purify also uses heuristics to attempt to improve the code locality in the
resulting core image.  It basically does a breadth-first traversal of the
call graph, placing the code for functions in the order it reaches them.
Eyeballing of the core file suggests that this does place groups of related
functions together, and subjective reports indicate that there is a
resulting improvement in response time.  Unfortunately these effects are
difficult to quantify since they are largely things such as reductions in
the time to swap in the compiler after editing for a while.

Lisp is often accused of "bad locality"; although this is true to some
degree, it is also largely a result of an apples-and-oranges comparison.
The system manager looks at this "lisp" process and observes that it has a
huge amount of memory allocated, and has only accessed scattered parts of it
in recent history.  If you compare it to a nice C program like grep, then it
has bad locality; the thing is that the C programmer doesn't just sit there
all day using grep, he also uses editors and debuggers and does all kinds of
file I/O.  If you mashed all that stuff together into one address space then
you would see bad locality too.  The reason that the lisp thrashes the
system and the C programmer doesn't is that the changes of context that the
C programmer makes are often explicitly flagged to the system by process
creation and termination.

One of the things that Purify attempts to do is place different systems in
different parts of memory so that the Lisp behaves more like a collection of
programs than a big ball of spaghetti.  This is done by specifying a list of
"root structures"; the stuff reachable from a given root structure is
transported in one shot, and then you go on to the next root structure.
Currently our root structures are the top-level loop, the compiler the
editor and the editor key bindings table.  Other symbols with no references
are also treated as call-graph roots.

Another advantage of the strategy of initially allocating all objects
dynamically is that allows stripped delivery vehicle Lisps to be created by
GC'ing away unreferenced objects.  There is a version of purify that
uninterns all symbols and then does a GC while keeping a finger on a root
function.  After the GC, symbols that still exist are reinterned, and the
root function is called when the suspended core image is resumed.

I haven't used this facility much, since it makes our life easier to
maintain only one core and inflict it on everyone.  I once built a system
rooted on our editor, and it was about 50% smaller than the full system,
weighing in at about 1meg with a dense byte-coded instruction set.  The
editor is a sizable system that makes no attempt to avoid hairy Common Lisp
features (the opposite if anything).  I also didn't destroy the error
system, which meant that the READ and EVAL and PRINT and the debugger and
format ~:R were still all there.  Things like bignum arithmetic also won't
go away unless you explictly blast them, since they are implicitly
referenced by the standard generic arithmetic routines.


>
>>We're using a version of Common Lisp that takes up
>>something over 5 megs just for itself,
>
>Sounds suspiciously like Lucid's system, which is unusually voluminous,
>partly because the compiler is resident (now *there's* a function to
>autoload!).  

This really depends on your goal.  Here at CMU we are more interested in
having great Lisp development environment than in having a Lisp you can use
for minimal $$$.  I am much more intimidated by the functionality present in
the Lisp machine's 20meg+ world than I am intimidated by the efficiency of a
minimal Lisp that can run a silly benchmark in 512k.

The Lucid system contains both a resident compiler and editor, which is
required to implement the sort of incremental development environment that
Lisp machines offer.  I don't doubt that an interpreted development cycle
would be more efficient of resources, but I would prefer what I have.  

Yes I have used Interlisp.  Back in my timesharing days I preferred it to
Maclisp, since it offerred an integrated development environment.  Everyone
thought I was crazy since it was so big (and therefore slow).  Today I am
using an integrated Lisp environment on a machine with 5x as much physical
memory as the 20 had virtual memory; I *like* it.

>Many people believe that a full CL can be fit into one meg
>of memory, but it requires serious attention to space optimization, which is
>currently unfashionable - "just add another memory board!".  

I have little doubt that this is true if you used a byte-code interpreter. 
The bare PERQ Spice Lisp system wasn't much more than a meg, and it was
optimized more for time than space, and had 150k of doc strings.  The
question is why bother?  The only use I can think of for such a toy system
would be for educational use on PC's.  Once you start layering a real
development environment on top, it won't make much difference whether the
root Lisp is 500k or 5meg.

The day that Lisp is no longer perceived as being wasteful of resources will
be the day that Lisp is permantly banished from the cutting edge of
programming environment development.  The current flamage shows that the day
is not here yet, but I can see an omen in the comparison to Smalltalk.
Smalltalk's pervasive object-oriented paradigm wastes CPU in a way
unthinkable in a Lisp system, and Smalltalk based systems are also
accomplishing amazing things.

>I wonder
>if compiler writers ever get kickbacks from memory manufacturers... :-(
>
>>Mike Maxwell
>
>							stan

Well, I haven't gotten mine yet, but they say the check is in the mail...

  Rob