TAOCP 2.5 Exercise 2

Section 2.5: Dynamic Storage Allocation

Exercise 2. [**] [HM23] (E. Wolman.) Suppose that we want to choose a fixed node size for variable-length items, and suppose also that when each node has length $k$ and when an item has length $l$, it takes $\lceil l/(k-b)\rceil$ nodes to store this item. (Here $b$ is a constant, signifying that $b$ words of each node contain control information, such as a link to the next node.) If the average length $l$ of an item is $L$, what choice of $k$ minimizes the average amount of storage space required? (Assume that the average value of $(l/(k-b))\bmod 1$ is equal to $1/2$, for any fixed $k$, as $l$ varies.)

Verified: yes
Solve time: 6m25s

Let $k$ be the node length and $b$ the control-word overhead per node. Each item of length $l$ requires

$\left\lceil \frac{l}{k-b} \right\rceil = \frac{l}{k-b} + \delta_l$

nodes, where $0 \le \delta_l < 1$ is the fractional part. By assumption, the average value of $\delta_l$ over all items is $1/2$. Hence the average number of nodes per item is

$\frac{L}{k-b} + \frac12,$

and the average storage used per item is

$S(k) = k\left(\frac{L}{k-b} + \frac12\right) = \frac{k L}{k-b} + \frac{k}{2}.$

To minimize $S(k)$, differentiate with respect to $k$, treating $k>b$ as continuous:

$\frac{dS}{dk} = \frac{L(k-b) - k L}{(k-b)^2} + \frac12 = -\frac{L b}{(k-b)^2} + \frac12.$

Setting $dS/dk = 0$ gives

$\frac12 = \frac{L b}{(k-b)^2} \implies k-b = \sqrt{2 L b} \implies k = b + \sqrt{2 L b}.$

This value of $k$ minimizes $S(k)$ because the second derivative

$\frac{d^2S}{dk^2} = \frac{2 L b}{(k-b)^3} > 0$

for $k>b$. Therefore, the optimal node length is

$\boxed{k = b + \sqrt{2 L b}}.$