Reselect’s Memoization in 3 Functions

I’ve been reading through Reselect’s source code (only 107 lines unminified) and thought it might be worth unpacking some of the concepts in a blog post.

Concept 1: Memoization

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. (source)

Differently put, if you have a pure function doResourceHoggingThing that hogs resources while running (e.g.doResourceHoggingThing(argument)), memoization is a shortcut so that if you run it over and over again without changing argument then the function only runs the first time. After that, it just keeps a copy of the result and spits it out whenever the sameargument is provided so that you don’t have to waste resources calculating the same value over and over.

Since Reselect runs within the React render cycle, it’s primary concern is not saving all results of previous function executions, but just the last result, so that the (possibly expensive) update cycle can be skipped if it’s going to spit out a consistent value.

Simple memoization (storing the last result for a function with a single parameter) is easy to accomplish in Javascript using a closure.

const memoizeFunc = func => {
  // these variables inside the closure keep track of
  // the previous data to do the comparison
  let lastArg = null;
  let lastResult = null;
  return function (newArg) {
    // if the arguments don't match
    // calculate the result and return it
    if (newArg !== lastArg) {
      console.log('new', lastResult)
      lastResult = func(newArg)
    }
    // otherwise just return the old result
    lastArg = newArg;
    console.log('cached', lastResult)
    return lastResult;
  }
}
const identity = x => x;
const memedFunc = memoizeFunc(identity);
memedFunc(4) // 'new', 4
memedFunc(5) // 'new', 5
memedFunc(5) // 'cached', 4

However, performing memoization for any number of parameters is a little more complicated.

Refresher 1: Equality Checks by Reference

The main decision that a memoized function needs to make is “did my arguments change since this last time I was called?”, so the first function in Reselect is a simple equality check which is used to determine the equality of arguments passed into the function:

// Reselect Function #1
function defaultEqualityCheck(a, b) {
  return a === b
}

What’s worth understanding here is that this works by comparing two values by reference instead of by value. Since a memoized function will frequently take Javascript objects (any non-primitive data type such as {} or []) as arguments, and since equality checking objects is itself potentially resource intensive, Reselect skips a deep comparison of object values and uses their underlying reference as a proxy for equality.

This shortcut is safe, because while it’s relatively easy to get this check to return false for two objects that are equal by value but different by reference, I can’t think of a scenario where two objects can share a reference while having differing values.

const opt0 = {value: 0};
const opt1 = {value: 1};
const opt2 = {value: 1};
const opt3 = opt1;
const arr = [
  opt0, opt1, opt2, opt3
]
// Both values and reference match
defaultEqualityCheck(arr[0], arr[0]) // true
// Neither value nor reference matches
defaultEqualityCheck(arr[0], arr[1]) // false
// value matches, but reference doesn't
defaultEqualityCheck(arr[1], arr[2]) // false
// reference matches
defaultEqualityCheck(arr[1], arr[3]) // true

This is the side to err on in a React app, because this edge case (should it occur) would result in a redundant render cycle and not in a failed update when the underlying data changes.

Refresher 2: The Arguments Object

The arguments object is “a local variable available within all (non-arrow) functions. You can refer to a function’s arguments within the function by using the arguments object. This object contains an entry for each argument passed to the function, the first entry's index starting at 0.” (source)

It’d be nice if we could just run the equality check on the two instances of arguments directly, but they’ll never share the same underlying reference so this won’t work. We’ll have to dig deeper, which brings us to the next Reselect function.

// Reselect Function #2
function areArgumentsShallowlyEqual(equalityCheck, prev, next) {
  if (
    prev === null || 
    next === null || 
    prev.length !== next.length
  ) {
    return false
  }

  // Do this in a for loop (and not a `forEach` or an `every`)
  // so we can determine equality as fast as possible.
  const length = prev.length
  for (let i = 0; i < length; i++) {
    if (!equalityCheck(prev[i], next[i])) {
      return false
    }
  }

  return true
}

This just iterates over the properties in the two arguments objects and shallowly compares them using a passed-in equality check. Since the arguments object is an array-like object, it has a built-in property length which allows for some quick tests before the loop to speed things up.

Concept 3: The Memoization Function

Now that all the building blocks are understood, the default memoization function used in reselect is just their combination.

// Reselect Function #3
export function defaultMemoize(func, equalityCheck = defaultEqualityCheck) {
  let lastArgs = null
  let lastResult = null
  // we reference arguments instead of spreading them for performance reasons
  return function () {
    if (!areArgumentsShallowlyEqual(equalityCheck, lastArgs, arguments)) {
      // apply arguments instead of spreading for performance.
      lastResult = func.apply(null, arguments)
    }

    lastArgs = arguments
    return lastResult
  }
}

I’m not 100% sure on the granular details of the enhancement added by using func.apply, but it looks like Babel transpiles func(...arguments) to this under the hood.

Conclusion

That’s it. The basics of Reselect in three functions. There’s a bit more in the source code so maybe I’ll add a part 2 in the near future.