LostLists: Interlisp-10 facility for finding lost list space - 4/9/82
                                Comments/suggestions -> DonC@ISIF 

The LostLists program is meant to answer the age old question:
            "Where is my list space going?"
Unfortunately, it is rather less useful at the stage when you're desparate
for list space.  (Note that SETSBSIZE can help in that situation.)
Rather, it is useful when a certain program appears to lose list space and
you want to find the discrepancy.

The recommended usage goes something like this:

Load your program
LOAD(LOSTLISTS.COM)    note that it only works compiled!
InitLostLists()
MINFS(...)             Allocate enough list space to run your program
RECLAIM()              with at least 5000 extra cells for the LostLists pkg
MINFS(100)             try not to allocate any new list space
GAINSPACE()            get rid of everything you can
MarkFreeCells()
MarkAtoms(T)

<Mark whatever other odd data structures you can think of, e.g. CLISPARRAY
 if you didn't get rid of it in GAINSPACE>

(LENGTH (SETQ Misc (Sweep)))
<run your program>
ReInit()
GAINSPACE()            again try to get rid of everything you can
MarkFreeCells()
MarkAtoms()            This will tell you changes in sizes of atoms

<Mark whatever else you can think of>

HowMany()              see how much space was "lost"
(LENGTH (SETQ Misc2 (Sweep)))

<examine Misc2 to see what other lists there are>

Basically, LOSTLISTS acts like a garbage collector (but only for lists).

InitLostLists creates a bit table for which you need several thousand words
of array space (a 512 word page table plus 16 words of bit table per list
page and one list cell per list page).

ReInit zeros the bit table (and in fact allocates a new one if BadPage is
non NIL - see below).

MarkFreeCells marks all of the list cells that the GC considers free.  It is
important not to interrupt this process, because interactions with the break
package (as well as anything else) allocate free cells which will then not
be marked.

MarkAtoms marks the function definitions, property lists and values of all
atoms.  If it is given a non-NIL argument it does not report anything.
Otherwise, it tells you which atoms have changed size since the last time.
"Size" in this case means the number of list cells marked from the atom.
This is sensitive to the order in which atoms which share structure are
marked.  A typical example is that the editor stores the context of the
last edit in the atom EDIT.  Thus, if you edit something between two
calls to MarkAtoms, the second may report that space has moved among the
edited atom, EDIT and some previously edited atom (the last one edited
before the first call to MarkAtoms).  Also, one should not call MarkAtoms
twice without doing a ReInit between, since this will change (and report!)
the sizes of all atoms to zero (since they are already marked).
SaveSizes may be set to NIL if you do not want MarkAtoms to save the sizes
of the atoms.  Of course this also prevents it from reporting the changes
in those sizes, but if you're only interested in the results of Sweep,
this will save space (2 list cells per atom which uses list space - this
is about 3000 list cells in an empty sysout).

HowMany reports how many of the list cells have been marked.

Sweep returns a list (which may be fairly long and thus take a lot of space if
there is a lot of stuff unmarked! - use HowMany to see how much is unmarked)
which contains all of the unmarked cells.  It is hoped that browsing through
this list will give you a hint of what the lost space is being used for.

Mark marks from its argument.  It is available in order to allow the user
to mark structures that he knows about (and does not want to collect with
sweep) that are not "obvious" in the sense below.  (LOC (Mark x)) is the
number of list cells that were actually marked.  For example, 
(for i to (ARRAYSIZE A) sum (LOC (Mark (ELT A i))))
will mark the array A and return its size.

Right after a thorough GAINSPACE, the free list and atoms are what we consider
to be the "obvious" uses of list space.  However there is a lot of other
miscellaneous stuff in an initial core image, e.g. constants used by compiled
code.  This is why it is recommended that you do a sweep (and keep the results
around) before you run your program.  That way, the next sweep will only give
you the new miscellaneous lists.  In an empty sysout, the first Sweep returns
a list of almost 1300 elements (thereby consuming 1300 list cells), which
accounts for over 5000 unmarked cells (HowMany would have shown 5000 cells
unmarked just before the Sweep).

The bit table is created by InitLostLists.  If list space is allocated after
that, there is no space for marking the new list cells.  This is why we want
to avoid allocation.  If Mark encounters a list from a page that was allocated
since the bit table was created, it stores that list in the variable BadPage.

Even if no list space is "lost", the second call to MarkAtoms is likely to
report small changes in such things as the spelling lists.  Also, Sweep will
normally return a few recent events of history (even if you discard the
history in GAINSPACE).  The lists returned by Sweep may be pointed to from
Arrays, user datatypes or stack frames.  Note that a bug in the garbage
collector sometimes prevents free stack frames from being reclaimed.  If
(STORAGE) reports more than one stack frame in use when you are at the top
level (and you don't think you are using the spaghetti stack), the stack
frams can sometimes be reclaimed by running an infinite recursion, e.g.,
define (F) as (F) and then call F.  When this runs out of stack type ctl-D.