Balancing Multiple Garbage Collectors

Consider a program that runs continuously with \(W\) bytes of live memory, and also generates garbage at a constant rate of \(g\) bytes per second. That garbage could be new short-lived allocations, or it could be some of the live memory regularly becoming unreachable, replaced with new live allocations. Of course this is a toy model, in that it is totally steady-state time-invariant.

Garbage collection passes usually take time proportional to the live memory. Since in our toy model live memory is fixed, each pass should take a fixed time, call it \(t\). How often the passes occur, however, depend on how much garbage our program can suffer. If the total available memory is \(M\), with \(W\) being used for live memory, \(M - W\) can be garbage, which means in second \(g / (M - W)\) passes will have to be done. Those passes will take \(t g / (M - W)\) time. Plus of course the program is also doing some other things, which take \(b\) time. So the total runtime is:

\[ T = \frac{tg}{M - W} + b \]

Now let's imagine we have two different programs, naturally with different \(g\), \(t\), \(W\), and \(b\) values, sharing a fixed amount of memory \(M\). We want to split that total memory into \(M = M_1 + M_2\) and limit the first program to \(M_1\) memory and the second to \(M_2\) memory.¹ [¹ This assumes that garbage collection passes are going to be more frequent that changes to the per-process memory allocations. Otherwise you could try to put the two programs' collections out-of-phase.] Let's imagine we want to minimize the sum of their total runtimes—the programs are running concurrently, but either we care about both of them independently or we're interested in something like battery life that sums across concurrent processes. The total time is then:

\[ T_1 + T_2 = \frac{t_1 g_1}{M_1 - W_1} + \frac{t_2 g_2}{M_2 - W_2} + b_1 + b_2 \]

What is the best split? We can rewrite \(M_2 \leadsto M - M_1\) and take the derivative, which we set to zero:

\[ 0 = \frac{\partial(T_1 + T_2)}{\partial M_1} = \frac{t_2 g_2}{(M - M_1 - W_2)^2} - \frac{t_1 g_1}{(M_1 - W_1)^2} \]

Naturally we need to at least give each program its working memory, so let's rewrite \(M \leadsto E + W_1 + W_2\) and replace \(M_i \leadsto W_i + E_i\), where \(E_i\) is the "extra" memory for each process. Add some algebra and you have:

\[ \frac{t_1 g_1}{E_1^2} = \frac{t_2 g_2}{E_2^2} \]

In other words, multiple programs are balanced when the factor \(gt / (M - W)^2\) is the same for each. There's a couple of intuitions for this.

First, you can think of this as "total GC time, divided by extra memory", or ideally "Wasted time per byte". If giving a byte to one process saves more time than giving the byte to another process, that's how it should be allocated. The optimal allocation must make it basically irrelevant which process you give the marginal byte to.

Another way to think about this factor is to invert it and factor it into two terms:

\[ \frac{M - W}{t} \frac{M - W}{g} \]

The first term is how much garbage is collected, per second of collection time; it's a measure of garbage collection efficiency. The second term is the inverse of the number of GC passes done. The intuition here is that adding more memory is going to both reduce the number of GC passes, and increase the collection efficiency (since each pass will take the same time but collect more garbage). Multiplying the two factors incorporates both ways that adding memory helps speed up a program.

This toy model is nothing like the real world, but the intuition suggests it could generalize. Our next step is to develop a "memory controller", where multiple garbage collectors record information about their performance, and the controller tells them to increase or decrease memory usage to achieve the optimal memory split. If you're interested in this work, contact me and Marisa!