Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!uwvax!husc6!panda!genrad!decvax!tektronix!uw-beaver!cornell!gvax!jqj
From: jqj@gvax.cs.cornell.edu (J Q Johnson)
Newsgroups: net.arch
Subject: Re: Reasons For Large Main Memories
Message-ID: <494@gvax.cs.cornell.edu>
Date: Mon, 8-Sep-86 11:27:10 EDT
Article-I.D.: gvax.494
Posted: Mon Sep  8 11:27:10 1986
Date-Received: Tue, 9-Sep-86 17:56:12 EDT
References: <1253@curly.ucla-cs.ARPA>
Reply-To: jqj@gvax.cs.cornell.edu (J Q Johnson)
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 31

Barry Shein writes, discussing large-memory lisp applications:

>Now, ok, you eliminated paging, garbage collection has become a field
>service thing. But, could you do anything useful with all that memory
>and that (relatively) itty-bitty processor? How long would it take you
>to do a MEMQ of a list of a few HUNDRED MILLION lisp objects long?
>etc.  Paging is only an advantage at some interim and relatively low
>point (100-200MB perhaps, probably less.)

I think I, and perhaps others, have lost the thread of the argument.  Barry's
original attack on very large memories seemed to be that any system frequently
needed to perform background/service tasks that were linear in the size of
the memory (e.g. zeroing memory, or scanning for dirty pages to be written
to disk).  I'm not convinced that he has offered any evidence that any service
task in a reasonable lisp machine needs to be linear in memory.  GC can be
incremental (hence linear in CONSing rate).  CONSing itself is constant-time.
User access to memory is by definition linear in use, hence more (unused)
memory doesn't hurt. 

The quoted paragraph makes a slightly different argument, I think. It claims
that a lisp application can't benefit from a very large address space, WHETHER
OR NOT it is virtual or backed by real memory.  In fact, I think this argument
is incorrect; none of the really big lisp systems that I know of organize
data into a really big list to MEMQ down.

Having a few hundred million lisp objects is quite reasonable.  But generally
they will be in a very complex data structure, so that access to an arbitrary
lisp object requires sublinear time (e.g. a binary tree, implying that getting
a particular object would take only log(10^8) [maybe order 30?] accesses for
that 100 million example.

Have I missed something important here?