Little's Law and Lisp

We model the Lisp heap as a queuing system.

A “queuing system” consists of discrete objects we shall call “items” that “arrive” at some rate to the “system.” Within the system the items may form one or more queues and eventually receive “service” and exit.
-- Graves and Little in Building Intuition: Insights from Basic Operations Management Models and Principles, edited by D. Chhajed and T. J. Lowe, Springer Science+Business Media, LLC, New York, 2008

Our discrete objects are the objects returned by cons, make-vector, make-string, and the other primitive constructors. The heap is where these objects wait, and the objects “exit” the system when they become unreachable.
We can now apply Little's Law:

L=λW

We will assign λ, the average number of items arriving per unit time, to 1. In other words, we normalize time to be equal to the allocation rate. Little's Law simplifies to:

L/λ=W (when λ is 1)
L=W

We let L, average number of items in the queuing system, be the size of the heap in allocation units. W, the average waiting time in the system for an item, is therefore the mean lifetime of an object. Provided that we meet the necessary boundary conditions: The mean lifetime of a heap allocated object is equal to the mean size of the reachable heap.

We are measuring object lifetime in `allocations'. If desired, we could measure the allocation rate in units of time, and then we would get the object lifetime also in units of time. Instead, we are determining the average number of word allocations that occur before an object becomes unreachable.

The boundary conditions for Little's Law are quite lax. If the heap begins and ends empty we can satisfy them. The heap naturally starts empty, and when a program ends, we discard the heap, so we can pretend it is empty again. (This puts an upper limit on the lifetime of all objects.) As I noted in a previous post, the mean heap size for MIT/GNU Scheme compiling itself is about 300,000 words. Therefore, the mean object lifetime is 300,000 word allocations.

I will expand on this in the next post...