Path: utzoo!utgpu!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!csd4.milw.wisc.edu!uxc!uxc.cso.uiuc.edu!uxg.cso.uiuc.edu!uicbert.eecs.uic.edu!wilson
From: wilson@uicbert.eecs.uic.edu
Newsgroups: comp.lang.lisp
Subject: big lisp, locality, and multiproces
Message-ID: <63200004@uicbert.eecs.uic.edu>
Date: 26 Dec 88 23:10:00 GMT
Lines: 63
Nf-ID: #N:uicbert.eecs.uic.edu:63200004:000:2802
Nf-From: uicbert.eecs.uic.edu!wilson    Dec 26 17:10:00 1988


I am looking for general views of the future of Lisp systems, especially
parallel systems.  A major concern is the effect of Lisp's locality
problems on the performance of multiprocessors, and I am wondering
about the compatibility of "big" systems (with a single many-megabyte
heap) with multiprocessors.

What worries me is the continuing trend for processor speeds to increase
faster than memory speeds.  For now, people mostly build faster and
faster uniprocessors (or not-many-processors) with bigger and bigger
main and cache memories.

Generational garbage collection helps keep things in RAM.  With big
enough caches, I guess we can keep the youngest generation in cache,
but the locality problem will probably just keep replicating itself
at a new level.  And when do we have to make some painful tradeoffs
between clustering and scattering data, to optimize the tradeoff
between locality and contention in multiprocessors?

Bob Courts' adaptive incremental collector seems to give another nice
improvement in locality, halving RAM requirements.  (I have a couple
of ideas of my own, one of which I'm pretty sure will also give a
reasonable boost.)  But are these techniques going to be enough? 

Some questions:

  1.  What is the irreducible locality cost of garbage
      collection?  (i.e., if you gc a generation too
      often, you copy too much data without giving it time to die,
      but if you gc it less often, you have too much garbage
      interspersed with live data.)

  2.  What does the heap of a big Lisp system (i.e., 3600, Explorer)
      mostly hold?  Would locality be much better if there were
      heavyweight process "firewalls" separating the data and code
      of different utilities (like the editor, browser, compiler)?
      I've heard Kyoto Common Lisp forks a separate process for
      compiling, and usually manages to finish a compile and just
      throw away the process without gc'ing it.  Does that really
      work well, and does a generational gc remove the need for it?

  3.  Does anybody have any data on the effect of different scavenging
      algorithms on cache-block-scale locality and/or contention?  On
      page-scale contention in distributed Lisp systems?  (Do people
      do distributed Lisp systems?)

  4.  Just how serious is the locality issue, really, both for now
      and in the future?  (How much time does your system lose to
      paging, and what happens when we have big multiprocessors?) 


I'd appreciate any views and/or references on these issues, especially
references to overviews of relevant topics.

Thanks prematurely,

Paul


Paul R. Wilson                         
Human-Computer Interaction Laboratory
U. of Illin. at C. EECS Dept. (M/C 154)   wilson%uicbert@uxc.cso.uiuc.edu
Box 4348   Chicago,IL 60680