[jlebar]

It's worth noticing that most of the optimizations here are for "space" -- reducing the working set size or the number of memory accesses. CPUs have gotten much faster than memory blah blah. This is the sort of thing where microbenchmarks may mislead you, because you WSS is probably not realistic.

I think we don't have great tools for helping with this sort of optimization. One can use perf to find cache misses, but that doesn't necessarily tell the whole story, as you might blame some other piece of code for causing a miss. Maybe I should try cachegrind again...