From: cet1@cus.cam.ac.uk (C.E. Thompson)
Subject: Re: TeX's memory
Organization: U of Cambridge, England
Date: Thu, 17 Dec 1992 19:19:03 GMT

In article <9212150429.AA21324@orion.arc.nasa.gov>, "Arthur Ogawa"
<ogawa@orion.arc.nasa.gov> writes:
|> While barbara beetons comments are accurate, so is don hosek's.
|> 
|> TeX really does not perform garbage collection: if you fragment TeX's
|> memory, those unusable small areas will not be consolidated. This
|> is what's meant by  not doing garbage collection, I believe.

Well not precisely, in normal usage. (Unless you mean `This is what people
mean when they say that *TeX* doesn't do garbage collection', possibly.)

TeX (we are talking about `main memory' here) doesn't have garbage in the
sense of allocated areas that no longer have references from `outside'.
The data structures it uses are not recursive (in the sense that the
representation of an \hbox, say, cannot point to a contents list that
itself points back at the \hbox), and in so far as they are shared at all,
they have reference counts, and are explicitly freed when the count falls
to zero. (This does put some constraints on what can be done in TeX, of
course.) In particular, the redefinitions that LaTeX does, mentioned by
Don Hosek, do cause the main memory allocated to the previous definitions
to be freed.

|> The implication is that you can create a situation in which TeX will
|> run out of mem, but the net mem in use would still have allowed
|> your operation (say a \def), if only it weren't fragmented.

But it *is* possible for the free space to become fragmented, so that a
request cannot be satsified although the total amount of free space is
sufficient. This is because TeX does not have a *compactor* rather than
a garbage collector. Admittedly, you don't often find compactors in 
dynamic storage allocation schemes except as part of compacting garbage
collectors, as the complexity required is essentially the same (all outside
and internal references have to be adjusted), but the notions are distinct.

Fragmentation of main memory in TeX happens at two levels. First, there is
a division into two parts, one for multi-word nodes (`box memory') and one
for one-word nodes (`macro memory'). Either part can grow as required, but
never shrinks again. This seems to be the commonest reason for not being
able to use the whole of the allocated main memory, though things are much
better than they were before TeX 1.3, when the size of each part was fixed.
(David Fuchs was responsible for the idea of making the division dynamic,
I believe.)

Secondly, the free space in the multi-word node part is subject to the usual
sort of fragmentation found in any dynamic storage allocation scheme without
compaction. If there are 1000 free non-adjacent 2-word nodes, TeX cannot 
allocate a single 3-word node. The allocation algorithm used by TeX, together
with its quite unaggressive distribution of request sizes, means that this is
not usually a serious problem, although one can certainly construct counter-
examples.

The allocated amounts of multi-word and one-word main memory are shown
separated by an `&' in \tracingstats output. Exactly the same algorithms 
are used in METAFONT, by the way. 

|> Interestingly enough, there is nothing that prevents a TeX implementor
|> from garbage collection into TeX, and some TeX engines actually run
|> in an environment in which could allow garbage collection without
|> TeX's active participation.

In *theory*. I will believe it when I see it :-)

|> As I recall, Don Knuth said that the reason garbage collection was not
|> built into TeX is because writing garbage collection  procedures is quite
|> error-prone, and he decided to avoid getting into that altogether.
|> 
|> Certainly, anyone who has seriously thought out the implications of adding
|> garbage collection to TeX will realize what a complex task it is.
|> 
|> By the way, concerning \csnames: It is true that TeX never yields up
|> space in the hash table (where control sequence names, but not their meanings
|> are stored). It is interesting to note that the mere act of testing
|> whether a \csname is defined, as in
|> 
|> \ifx\foo\undefined
|> 
|> will make an entry for \foo in the hash table, and thereby use up additional
|> space for "multiletter control sequence names".

All true. A new multi-letter control sequence gets allocated space in the hash
table whenever it is read *without* expansion (more accurately, via |get_token|).
By an interesting dispensation, this doesn't happen if it is being read with
expansion, and therefore generates an immediate error! More significantly, 
control sequences occuring in parts of files that are being conditionally
skipped do not go into the hash table.

Chris Thompson
Cambridge University Computing Service
JANET:    cet1@uk.ac.cam.phx
Internet: cet1@phx.cam.ac.uk