michaelm@bcsaic.UUCP (02/16/87)
In article <4296@utah-cs.UUCP> shebs@utah-cs.UUCP (Stanley Shebs) writes: >... >programs are continually loading this module or that module. PSL for instance >has hundreds of modules that can be loaded, but it's a pain in practice to >forget one of them (and autoloading has its disadvantages as well)... I'm curious: what's the disadvantage (besides the time it takes to do it) of autoloading? We're using a version of Common Lisp that takes up something over 5 megs just for itself, before we even load in any functions When we ran in Franz, we used a *lot* less space. I suspect that a lot of the difference is in the parts of CL that are over and above Franz (ratios, real numbers, ad infinitum) and most of which I have no use for, plus the things that Franz autoloaded (machacks, the tracer, etc.). What's the disadvantage to autoloading? -- Mike Maxwell Boeing Advanced Technology Center arpa: michaelm@boeing.com uucp: uw-beaver!uw-june!bcsaic!michaelm
shebs@utah-orion.UUCP (02/17/87)
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? In order to provide for autoloading of a function, you have to preload the name of the function and the place where its code lives, i.e. a form like (define-autoload sort "/net/fileserver/usr/lib/cl/sort.b") or some such. You have to have both the symbol SORT and the pathname for its file present all the time. This may not seem like a big deal, but consider that CL has over 600 functions---you chew up a bit of space for all those (tho admittedly not several megs!). A decent autoloading system should also be more clever than just to look at functions - consider FORMAT with strange options, or even ordinary /. It would be unreasonable to load Roman numeral printing just because you happened to say (format "hi there.~%"), or to load ratios just because / can produce them sometimes. The observant reader will suggest that autoloading be performed on internal functions like RATIO/ and PRINT-ROMAN, but of course there are thousands and thousands of internal functions. Finally, the loading time overhead can be nontrivial---if the implementation is highly interconnected internally, you may end up loading most of the system the hard way anyhow (it's not implausible for INTERSECT to call SORT, which calls MAKE-ARRAY, ...). Of course, none of these are insurmountable problems, but they do tend to discourage implementors from building a system based on autoloading. It *is* a useful feature to have! >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!). 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 wonder if compiler writers ever get kickbacks from memory manufacturers... :-( >Mike Maxwell stan
wade@su-russell.UUCP (02/18/87)
I see no reason to support autoloading in a system which supports a decent implementation of virtual memory (UNIX does not fall into this class). A good virtual memory implementation completely subsumes autoloading by keeping only what you are likely to need in your working set (this ignores the cost of page table size, etc.).
shebs@utah-orion.UUCP (02/18/87)
In article <253@su-russell.ARPA> wade@su-russell.ARPA (Wade Hennessey) writes: >I see no reason to support autoloading in a system which supports a >decent implementation of virtual memory (UNIX does not fall into this >class). A good virtual memory implementation completely subsumes >autoloading by keeping only what you are likely to need in your >working set (this ignores the cost of page table size, etc.). This is yet another reason for implementors being indifferent about autoloading. Unfortunately, there is a tendency to shrug and assume that "virtual memory will take care of problem X". Virtual memories can be sandbagged by poor implementation style, such as a high degree of internal connection. Adding flavor to a user interface by using kinky FORMAT options, or defining all the sequence functions in terms of each other has severe costs in terms of paging rate. You also need cooperation from storage management so that GC doesn't page in every single last byte of system code. Lots of research has been done on this, but there isn't even a consensus on reference counting vs GC vs hybrids... stan
wade@su-russell.UUCP (02/19/87)
Stan Shebs is correct in saying that complex function inter-dependencies can cause poor paging behavior; however, autoloading doesn't help this problem one bit. In fact, it can actually aggravate the problem by paging in many useless objects. Autoloading is a poor substitute for a good virtual memory system because the grain size is too large - you generally must load a complete group of related functions and you must waste time parsing the binary file format at run time. Virtual memory avoids both of these problems. I'm only arguing against autoloading in a good virtual memory system, though. Many popular operating systems do not have wonderful virtual memory systems. UNIX, for example, handles large processes so poorly that I might argue that autoloading *is* a good idea when writing a Lisp to run on it. Wade
ram@spice.cs.cmu.edu.UUCP (02/20/87)
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
chris@mimsy.UUCP (02/20/87)
In article <254@su-russell.ARPA> wade@su-russell.ARPA (Wade Hennessey) writes: >Many popular operating systems do not have wonderful virtual memory >systems. UNIX, for example, handles large processes so poorly that I >might argue that autoloading *is* a good idea when writing a Lisp to >run on it. Unix? What is a Unix? Please note that there are many different virtual memory systems out there, all running under some Unix variant. They may indeed all be bad, but saying `Unix handles large processes poorly' does not provide enough information for someone who would be willing to fix it. Which Unix? (The 4.[123]BSD VM code is generally acknowledged as overdue for a rewrite. One is in progress, but I have no details.) Back to the `main point': autoloading generally gives up time in favour of space---file system space. One can have umpteen versions of a lisp binary that all share the same package. In a way this is much like shared libraries. (If your system does the sharing automatically, without requiring `autoload's or other helpful hints, well, that *is* neat.) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7690) UUCP: seismo!mimsy!chris ARPA/CSNet: chris@mimsy.umd.edu
paul@osu-eddie.UUCP (02/24/87)
In article <254@su-russell.ARPA> wade@su-russell.ARPA (Wade Hennessey) writes: > >Many popular operating systems do not have wonderful virtual memory >systems. UNIX, for example, handles large processes so poorly that I >might argue that autoloading *is* a good idea when writing a Lisp to >run on it. > >Wade No, this is not alltogether true. Unix will handle a very large program just fine, as long as the memory refrences are not scattered, but are instead mostly local and/or sequential. The problem here is that most Lisp implementors are too lazy to carefully watch how there lisp deals with VM. One can, of course, give your Lisp a compacting GC, but this opens up a whole new can of worms, including possibly, reduced GC performace... -- Paul Placeway Department of Computer and Information Science SNail: The Ohio State University 2036 Neil Ave. Columbus OH USA 43210-1277 ARPA: paul@ohio-state.{arpa,csnet} UUCP: ...!cb{osgd,att}!osu-eddie!paul -- Paul Placeway Department of Computer and Information Science SNail: The Ohio State University 2036 Neil Ave. Columbus OH USA 43210-1277 ARPA: paul@ohio-state.{arpa,csnet} UUCP: ...!cb{osgd,att}!osu-eddie!paul
wade@su-russell.UUCP (02/24/87)
When I said that Unix didn't handle VM well, I was refering to SUN Unix. I wasn't complaining about locality problems - any virtual memory system has a problem with scattered references. I was complaining about the need to have the maximum amount of swapping space (I tend to call it paging space) needed by a process available at image startup. I've frequently been unable to run a Lisp on the SUN because Unix doesn't think it has enough swapping space. I also wish that Unix had features like copy-on-write and demand-zero pages.
bzs@bu-cs.UUCP (03/01/87)
Re: all the problems with autoloading. Hmm, seems to me that a solution would be to have a LISP hook into an orderly virtual memory system so packages can be put (preferably read-only and shared, re-binding would just stop pointing at the read-only version, that happens in lisps now on such systems that support read-only code) on page cluster (ie. 1 or more pages) boundaries. This should give all the advantages of auto-loading with the added advantage of a possible auto-unloading automatically by a virtual memory system. That is, all the features, none of the hassles, transparent. Seems like if we took a UNIX loader and convinced it to understand some sort of hook (hmm, perhaps just "align each .o file" would be enough, certainly as a start) to re-align packages* onto page or segment boundaries it would just sort of happen. Or am I missing something here? [start stream-of-consciousness, sorry] Well, replacing a package would now necessitate re-linking the LISP, is that a fatal problem? (if everything was so neatly aligned how hard could it be to just re-load [eg. with ld's -A flag] at the same address and put it back into the runnable image, hmm, unless it didn't fit, ok, well, try that and if not then re-build (or, hell, shuffle everything down, no, that may cause problems with non-relocatable code, ok, rebuild.) We are starting to see UNIX systems which re-build on every boot (SYS/V), not free, but we're not talking about doing it that often either (not on every start-up, just if a package changes.)) I assume I am going to hear that such-and-such did this in 1929, oh well. -Barry Shein, Boston University * Not necessarily in the CL sense of the word, I just mean a group of functions which would be auto-loaded together.
bruce@stride.Stride.COM (Bruce Robertson) (03/08/87)
In article <257@su-russell.ARPA> wade@su-russell.ARPA (Wade Hennessey) writes: >I also wish that Unix had features like copy-on-write and demand-zero >pages. Much as I dislike System V, the virtual memory system provided by AT&T does not require you to have enough swap space to contain the process no matter how big it might get, and it does have copy-on-write and demand-zero pages. Because of copy-on-write, data pages are stored in the page cache as well as text pages, resulting in commonly used programs starting up much more quickly. In fact, we are using the System V virtual memory implementation in the 4.3bsd port that we are working on, rather than Berkeley's implementation. -- Bruce Robertson bruce@stride.Stride.COM cbosgd!utah-cs!utah-gr!stride!brucad