Imagine that we have a boatload of memory and we're nowhere near the limit. Suppose, too, that we allocate memory simply by bumping the free pointer. If you think about it, you can see that the age of the most recently allocated objects is simply the distance between the object's location and the current value of the free pointer. Little's Law tells us that mean age of a heap allocated object is equal to the mean size of the reachable heap, so it must be the case that the mean distance from the reachable objects to the free pointer is also equal to the mean size of the heap (blah, blah, satisfy boundary conditions, blah, in the limit, etc.)

A few weeks ago, someone asked about the improvement in locality that one may get from the garbage collector. The vast majority of objects don't survive even a single garbage collection, so the vast majority of objects are layed out in memory exactly where they were consed and cannot benefit from any improvement in locality. This is not to say that there is no effect at all, but that the effect doesn't apply to the vast majority of objects.

Someone also asked what the GC pauses were. With a large heap (131072 blocks), the total time for MIT/GNU Scheme compiling itself was 167.7 seconds runtime, 1.06 second GC time. This comes out to about 22 milliseconds per GC.

Little's Law and the weak generational hypothesis

Theorem: The mean lifetime of a heap allocated object is equal to the mean amount of reachable storage.
Proof: This is Little's Law with λ=1.

This turns out to be a pretty handy theorem. Here's an example.

In a prior post, I mentioned that a prerequisite for effective garbage collection is that the amount of reachable storage must at all times be less than the amount of memory available for the heap. We apply Little's Law and get this: The mean lifetime of a heap allocated object must be less than the time it takes to exhaust the heap.

That naturally follows: in order for garbage collection to “work”, we need something to become garbage before we completely run out of memory. But Little's Law allows us to make a much stronger statement. The mean lifetime of all objects (where lifetime is measured in subsequent allocations), is, by Little's Law, equal to the mean size of reachable storage. The mean size of the reachable storage has to be less than the amount of memory available for the heap. Since the mean lifetime of an object must be small, and we have the occasional very long-lived object, it must be the case that the vast majority of objects have very short lifetimes. Or in other words,

Most allocated objects die young.

This statement is often called the weak generational hypothesis. It is usually presented as an empirical observation. By Little's Law, it is equivalent to saying that the size of the reachable objects is small, which is not a hypothesis, but a strong pre-condition of garbage collection.

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...

Little's Law

In Chapter 5 of 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, Steven Graves and John Little discuss Little's Law:

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.

Little's Law says that, under steady state conditions, the average number of items in a queuing system equals the average rate at which items arrive multiplied by the average time that an item spends in the system. Letting

L = average number of items in the queuing system,
W = average waiting time in the system for an item, and
λ = average number of items arriving per unit time, the law is

L=λW

Graves and Little give several examples, and I'll paraphrase one here.

Caroline is a wine buff. Her wine rack in the cellar holds 240 bottles. She seldom fills the rack to the top but sometimes after a good party the rack is empty. On average it seems to be about 2/3rds full. She buys, on average, about eight bottles per month. How long, on average, does a bottle languish in the cellar before being consumed?

Using Little's Law, we let L be the average number of bottles in the wine rack, 2/3×240=160. λ is the average number of items arriving per unit time, 12×8=96 bottles/year. Divide L by λ and we get W≅1.67 years per bottle.

(It seems to me that Little's Law is related to Stoke's Theorem. The size of the queue is the integral of the “flux” across the queue boundaries.)

more to come...

Another chart

Here is a chart of the number of words in use after each garbage collection (for MIT/GNU Scheme compiling itself with a heap of 1935360 words):

This is the smallest heap that is big enough for the compilation to complete. The limiting factor seems to be the big spike on the left at about 0.9×10⁹. We obviously wouldn't want to run with the minimum size heap; 3935 garbage collections are needed and almost a third of the total time is spent in GC. But the more frequently you collect, the better resolution you get.

Garbage collection gives us the illusion of nearly unlimited memory for temporary storage. To pull off this illusion, we must be able to satisfy every allocation request (at least up to the point where we throw up our hands and raise an “out of memory” condition). In other words, there must be free or unused memory available whenever we need some. Since the point of automatic memory management is to free the programmer from having to think about it, we expect to be able to allocate temporary storage at any time we wish during program execution.

A data structure can be considered “in use” if modifications to it can change the future behavior or result of a program. Since we cannot in general statically determine the future behavior, we compute the transitive closure of the data structures under the data access primitives. This is a superset of the data “in use”. That is, if you can't access the data, it cannot be “in use”.

In order for garbage collection to succeed as a storage management strategy, there must be at all times (anytime we want to allocate) some storage that is either unallocated or unreachable. The size of the heap must always exceed the size of the reachable data. Or we could say that the amount of reachable data must at all times be less than the size of the heap. (By ‘size of the heap’ I mean the total amount of storage both in use and free. For example, I could have a five megabyte heap, but only have 3 words in use.)

Any allocated data structure has but one of two ultimate fates: it remains reachable for the remainder of the run of the program or it becomes unreachable at some point (and we may re-use the storage). Assuming the heap starts empty, the size of reachable storage at any point in time is the difference between the total amount of all allocation and the total amount of all storage that has become unreachable up to that point. For example, if my program allocates sixty megabytes over its lifetime and it abandons fifty-nine megabytes, then the heap must contain the remaining megabyte.

---

We now consider the differential case, which is to say, the rates of allocation, collection, and heap growth or shrinkage. If the rate of allocation exceeds the rate of collection, the amount of storage in use in the heap must grow to meet the demand. Conversely, if the amount of reachable storage in the heap is decreasing, then we are abandoning storage at a faster rate than we are allocating it. But there are hard boundaries on the size of the heap. We can never have a negative amount of storage in use, and we have the requirement (see above) that the heap must be larger than the reachable storage at all times. The heap size is limited, so the rate of increase in reachable storage must be quite small over the long term if we are not to run out of heap.

The rate of storage allocation must be nearly equal to the rate of deallocation (or abandonment) almost all the time.

(This is only slightly different from the “steady-state” assumption that the rates are essentially equal. We're simply admitting the possibility that the reachable storage grows indefinitely and that the program would eventually crash if it doesn't finish first.)

John McCarthy

1927 - 2011