Applications of Randomness in Systems Performance Measurement [pdf]

The idea was to make performance be a smooth function of policy parameters by adding randomization. In many systems it's a jagged function and hard to optimize.

For example: compilers have to make a choice whether to unroll loops. Unrolling generally uses fewer instructions, but also increases code bloat and therefore cache misses. Compilers have a policy with some tunable parameters to decide how much to unroll any given loop. Compiler writers tune those parameters by trying several to see what gives the fastest programs overall.

The map from parameters => performance is very jagged, because sometimes increasing code size decreases caches misses because of associativity. If you look at the graph at the top of page 38, it shows cache miss rate as a function of code bloat. Slight changes in size cause large, unpredictable changes in performance. If you add some randomization here and there and take an average across many random seeds, you can get the nice smooth graph on page 45.

Sadly, no compiler today does this. One reason is that people like reproducible, consistent builds.

There's also an application to network congestion control. I think this one has become less relevant over time, because modern networks have background activity enough to avoid performance artifacts.