## Wednesday, May 15, 2013

### Exponential Cache Behavior

Guerrilla alumnus Gary Little observed certain fixed-point behavior in simulations where disk IO blocks are updated randomly in a fixed size cache. For his python simulation with 10 million entries (corresponding to an allocation of about 400 MB of memory) the following results were obtained:
• Hit ratio (i.e., occupied) = 0.3676748
• Miss ratio (i.e., inserts) = 0.6323252

In other words, only 63.23% of the blocks will ever end up inserted into the cache, irrespective of the actual cache size. Gary found that WolframAlpha suggests the relation: $$\dfrac{e-1}{e} \approx 0.6321 \label{eq:walpha}$$ where $e = \exp(1)$. The question remains, however, where does that magic fraction come from?