List Processing in Real Time on a Serial Computer

A real-time list processing system is one
in which the time required by the elementary list 
operations (e.g. CONS, CAR, CDR, RPLACA, REPLACD, EQ,
and ATOM in LISP) is bounded by a (small) constant. 
 Classical implementations of list processing systems
lack this property because allocating a list cell 
from the heap may cause a garbage collection, which process
requires time proportional to the heap size 
to finish.  A real-time list processing system is presented
which continuously reclaims garbage, including 
directed cycles, while linearizing and compacting the
accessible cells into contiguous locations to avoid 
fragmenting the free storage pool.  The program is small
and requires no time-sharing interrupts, making 
it suitable for microcode.  Finally, the system requires
the same average time, and not more than twice 
the space, of a classical implementation, and those
space requirements can be reduced to approximately 
classical proportions by compact list representation.
 Arrays of different sizes, a program stack, and 
hash linking are simple extensions to our system, and
reference counting is found to be inferior for 
many applications.

CACM April, 1978

Baker, H.

Real-time, compacting,garbage collection, list processing,
virtual memory, file or database management, 
storage management, storage allocation, LISP, CDR-coding, reference counting.  

3.50 3.60 3.73 3.80 4.13 4.22 4.32 4.33 4.35 4.49

CA780404 DH February 26,1979  4:32 PM

1024	4	3112
1050	4	3112
1051	4	3112
1098	4	3112
1214	4	3112
1380	4	3112
1388	4	3112
1393	4	3112
1393	4	3112
1485	4	3112
1487	4	3112
1541	4	3112
1549	4	3112
1549	4	3112
1570	4	3112
1846	4	3112
1878	4	3112
1946	4	3112
1957	4	3112
1972	4	3112
2023	4	3112
2060	4	3112
2156	4	3112
2156	4	3112
2168	4	3112
2168	4	3112
2218	4	3112
2361	4	3112
2438	4	3112
2513	4	3112
2625	4	3112
2723	4	3112
2723	4	3112
2736	4	3112
2736	4	3112
2833	4	3112
2833	4	3112
2838	4	3112
2845	4	3112
2855	4	3112
2855	4	3112
2855	4	3112
2857	4	3112
2896	4	3112
2922	4	3112
2944	4	3112
3039	4	3112
3074	4	3112
3074	4	3112
3074	4	3112
3081	4	3112
3101	4	3112
3106	4	3112
3112	4	3112
3112	4	3112
3112	4	3112
3112	4	3112
3112	4	3112
3112	4	3112
3112	4	3112
3112	4	3112
3112	4	3112
3112	4	3112
627	4	3112
106	5	3112
1380	5	3112
1826	5	3112
1972	5	3112
2438	5	3112
2723	5	3112
2736	5	3112
2833	5	3112
2838	5	3112
3112	5	3112
3112	5	3112
3112	5	3112
731	5	3112