Caching for Optimization

Caching is a strategy that would seem to have no downside. After all, computing a value only once is obviously always going to be quicker than recomputing it many times^[132]. That's true, of course, but it isn't the whole story. Occasionally, caching can backfire and actually make a computation slower.

It's certainly the case that computing once is always quicker than recomputing every time. However, caching isn't quite a case of computing-once; it's actually a case of computing-once-and-forever-after-rechecking-whether-you've-already-computed-and-if-so-then-accessing-the-previously-computed-value. That more complicated process may not always be quicker than recomputing every time. Searching and then accessing a look-up table has an intrinsic cost, which can occasionally be greater than redoing the entire calculation. Especially if the look-up table is a hash.