Why is Caching so Important?

One powerful technique that can significantly boost performance is caching. By intelligently storing and retrieving data from a cache, applications can avoid redundant computations and minimize costly operations, resulting in performance gains.

To illustrate the impact of caching, let’s explore a classic example of calculating the Fibonacci sequence. The Fibonacci sequence is a series of numbers where each number is the sum of the two previous ones, starting with 0 and 1 (0, 1, 1, 2, 3, 5, 8, 13, …).

Calculating large Fibonacci numbers can quickly become computationally expensive, as each next number requires the calculation of its two previous ones.

Here’s a classic implementation of the fibonacci function in TypeScript:

// we assume that n is a natural number
function fib(n: number): number {
  
  // base case: fib(0) = 0, fib(1) = 1
  if (n <= 1) {
    return n;
  }
  
  // recursive case: fib(n) = fib(n - 1) + fib(n - 2)
  return fib(n - 1) + fib(n - 2);
}

This recursive solution is straightforward, but it recalculates the same values for each recursive call. For instance, to calculate fib(5), the function needs to compute fib(4) and fib(3), but each of those computations will recursively calculate fib(3) and fib(2) again, leading to extra calculations.

By storing previously computed Fibonacci values in a cache, we can avoid redundant calculations and significantly improve performance.

// let's define cache
type Cache = Record<number, number>

// we initilize cache as empty object and store it as a parameter
function fibc(n: number, cache: Cache = {}) {

  // if value in the cache, return it
  if (n in cache) {
    const cached = cache[n]
    return cached
  }

  // if value not cached yet, compute it
  const computed = n <= 1 
    // base case
    ? n
    // recursive case
    : fibc(n-1, cache) + fibc(n-2, cache)

  // put value in cache before returning it
  cache[n] = computed
  return computed
}

In this implementation, we use a plain object as a cache to store computed Fibonacci values. We pass it as a parameter to the function, with the default value being an empty object. This cache object will map computed inputs to outputs. Before calculating a new value, the function checks if it’s already in the cache. If so, it returns the cached value; otherwise, it calculates the value, saves it in the cache, and returns it.

Caching Use Cases

Web browsers and content delivery networks use caching. They store frequently accessed web resources. This allows quick retrieval instead of fetching from the server. Computer hardware implements caching at multiple levels. This includes CPU caches and disk caches. Caching speeds up access to frequently used data and instructions. Database systems leverage caching. They store frequently queried data in memory. This reduces the need for costly disk lookups. Distributed systems utilize caching. They store copies of data closer to clients. This reduces latency and improves responsiveness. Blockchain networks use caching. They store recently verified transactions and blocks. This enables quick validation of new transactions.

Experiments

The following benchmark results, while not obtained in a strictly controlled environment, give an idea of the potential performance gains from caching. AET - average execution time.

You can run benchmarks in your browser here

Caching improves performance, but you need to pay the cost of using extra memory to store those cached results.