"A free curiosity is more effective in learning than a discipline based on fear."— Saint Augustine

Lazy Evaluation in JavaScript

2020-07-25

Sometimes evaluating an argument for a function is expensive! So expensive, that you only want to pay that fiddler to evaluate the value when the function you are calling uses the value.

Let's look at this problem abstractly first:

// The problem
const code = (props) => {
  // Arguments are sometimes only conditionally used!
  if (isExpensiveUseful(props.cheap)) {
    return doSomethingWithExpensiveArg(props.expensive);
  }

  return expensiveIsntEvenUsed;
};

const expensive = getExpensiveValue();
const cheap = {
  /*..*/
};

// Dangit! I had to compute expensive even though the `code`
// may not use it!
code({ cheap, expensive });

Do you see the problem? code, requires expensive but it only uses expensive if isExpensiveUseful is truthy! This isn't ideal because we have to compute expensive every time, even if code doesn't use it.

The Obligatorily Mentioned Boring Thunk

Jump to the section on Self Overwriting Lazy Getters to skip the obligatorily mentioned boring option.

If we have access to the function that only conditionally uses the expensive argument and we have access to update its other callers we can simply change the interface to make expensive a function that returns the expensive value. This allows the consumer of expensive to determine if we should pay the cost of computing it.

// Solution One - The Thunk, Explicit Deferred Evaluation
const code = (props) => {
  if (isExpensiveUseful(props.cheap)) {
    // We only pay the cost of `getExpensive`
    // (and therefore whatever functions it calls)
    // if we actually use it! Nice!
    return doSomethingWithExpensiveArg(props.getExpensive());
  }

  return expensiveIsntEvenUsed;
};

const payTheCostLaterIfYouWantThunk = () => {
  return getExpensiveValue();
};

const cheap = {
  /*..*/
};

// It's all on you now code, do us right.
code({
  cheap,
  getExpensive: payTheCostLaterIfYouWantThunk,
});

This updates the function's interface to make the conditional use of expensive explicit and allows code to decide when to evaluate it. This is a great option if you have access to update the code and all the callers. It also requires you to have confidence that they are using that expensive value only when it is needed. Unfortunately, their function may be consuming functions that conditionally want the expensive value and you'd need to be able to update every value user to where the value is needed to make sure this strategy works.

Self Overwriting Lazy Getters

An obscure and far less boring technique is to provide a getter that overwrites itself on the first retrieval. This allows us to avoid paying the cost of evaluating expensive if it isn't used without updating the function that conditionally uses it.

const code = (props) => {
  if (isExpensiveUseful(props.cheap)) {
    // Hey it's being access so it is time
    // to pay the fiddler!
    return doSomethingWithExpensiveArg(props.expensive);
  }

  return expensiveIsntEvenUsed;
};

const cheap = {
  /*..*/
};

code({
  cheap,
  // This code will only be run when someone
  // accesses `expensive`.
  get expensive() {
    // Don't forget to overwrite the value so you
    // only pay the cost once!
    delete this.expensive;
    // `this` is the object that contains `cheap` and
    // our `expensive` getter upon first retrieval we
    // overwrite the getter with its value.
    return (this.expensive = getExpensiveValue());
  },
});

First, we make expensive an "implicit thunk" by providing a getter. The getter is only run when someone accesses that field. Here comes the important part. The getter than overwrites itself with the computed value! this in the getter refers to the object that contains the getter. We are overwriting the getter from within the getter with the computed value. This prevents getExpensiveValue from being run several times if the value is accessed several times.

Concrete Example

Consider the following API that accepts any DOM element and returns a tree of the same shape with each element's computed styles & boundling client rect if that particular element has any classes attached.

const getVisualDetails = (el) => {
  return {
    children: Array.from(el.children || [])
      .map((child) =>
        getVisualDetails(child)
      ),
    styles:
      (el.classList || []).length === 0 
        ? null 
        : window.getComputedStyle(el),
    rect: el.getBoundingClientRect(),
  };
};

Let's explore some sample usage.

// Here is what usage looks like!
const styles = getVisualDetails(document.body);
// Should return the styles of the first element
// with classes in the document.
console.log(styles.children[0].styles);

// Should return the styles of the second element
// in the first child with classes.
console.log(styles.children[0].children[1].styles);

// Should return the layout of the first element
console.log(styles.children[1].rect);

If we wrap it in a time function we can get a rough pulse on how expensive it is and running it in the console.

const time = () => {
  // Time Before Computation
  const then = performance.now();
  const styles = getVisualDetails(document.body);
  styles.children[0].styles;
  styles.children[0].children[1].styles;
  styles.children[1].rect;
  // Subtract time before against time now.
  console.log("This computation took: ", performance.now() - then, "ms");
};

time();

My results running this function on github.com:

This computation took:  5.984999999782303 ms
This computation took:  3.9449999985663453 ms
This computation took:  4.269999999451102 ms

Make It Lazy, Make It Fast

Let's explore how we can use our new "Lazy Getter" technique to only compute what is used.

const getVisualDetails = (el) => {
  return {
    // We don't even walk the whole DOM in one go! Just one layer
    // of depth at a time, as needed!
    get children() {
      delete this.children;
      return (this.children = Array.from(el.children || [])
        .map((child) =>
          getVisualDetails(child)
        ));
    },
    // Only compute styles on demand if they're retrieved
    get styles() {
      delete this.styles;
      return (this.styles =
        (el.classList || []).length === 0 
          ? null 
          : window.getComputedStyle(el));
    },
    // Only compute rect on demand if it is retrieved
    get rect() {
      delete this.rect;
      return (this.rect = el.getBoundingClientRect());
    },
  };
};

When we first call our lazy implementation:

const styles = getVisualDetails(document.body);

Very little work is done! We just create an object with some locked and loaded properties that are ready to do the real work if and when needed. Additionally, we only do the work one layer at a time, so when children is accessed, that just returns a list of locked and loaded objects.

The actual heavy lifting of walking the DOM, computing styles, and measuring layout are all done lazily as needed.

Here are my results running the lazy version on github:

This computation took:  0.43000000005122274 ms
This computation took:  0.1250000004802132 ms
This computation took:  0.28000000020256266 ms

As we expected, the lazy version is many times faster. And less memory intensive! That is because we avoid computing or storing anything that isn't used, while the initial implementation computes the entire tree upfront even though only a handful of paths are accessed. Yikes!

Memoized Getters

An alternative implementation of self overwriting lazy getters is to define a memoized property that caches its result after its first call.

Lodash provices a handy utility called once which runs a function once and caches the value. Subsequent calls return the value initially computed.

Here is an implementation of once:

const once = (fn) => {
  let cache = null;
  // If we don't have it cached, compute and cache it.
  // Otherwise, return the cache.
  return () => (cache === null ? (cache = fn()) : cache);
};

Now we can define a property on our object that calls our memoized getter.

const args = {
  cheap,
};

Object.defineProperty(args, "expensive", {
  get: once(getExpensiveValue),
});

Here is what our getVisualDetails implementation looks like with once at our disposal.

const once = (fn) => {
  let cache = null;
  return () => (cache === null ? (cache = fn()) : cache);
};

const getVisualDetails = (el) => {
  const api = {};

  Object.defineProperty(api, "children", {
    get: once(() =>
      Array.from(el.children || [])
        .map((child) => getVisualDetails(child))
    ),
  });

  Object.defineProperty(api, "styles", {
    get: once(() =>
      (el.classList || []).length === 0 
        ? null 
        : window.getComputedStyle(el)
    ),
  });

  Object.defineProperty(api, "rect", {
    get: once(() => el.getBoundingClientRect()),
  });

  return api;
};

The important thing here, is that regardless of implementation, we want to compute the expensive value once and lazily as needed. If you're wondering how our memoized version performs, its pretty comparable to our self-overwriting implementation.

This computation took:  0.5100000003039895 ms
This computation took:  0.14000000010128133 ms
This computation took:  0.15499999972234946 ms

Summary

JavaScript is a wonderfully (and sometimes terribly) flexible language. Its call by sharing and getter semantics allow us to implement lazy evaluation for field access.

An exercise left for the reader is to implement lazy evaluation using ES2015 Proxys.

This technique of lazy evaluation is sometimes referred to as call by need. To explore this concept further I'd recommend an exploration of Haskell where the entire language is lazily evaluated.