Friday, November 18, 2011

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.
Post a Comment