Carlos Caballero

Posted on Feb 22, 2019 • Edited on Jul 12, 2019

Understanding JavaScript/TypeScript Memoization

#memoization #javascript #typescript #performance

Originally published at www.carloscaballero.io on February 8, 2019.

What means Memoization?

The definintion of memoization from the wikipedia is the following:

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.

Memoization is a programming techique which allows reduce the function’s time
cost for space cost. That is, the functions which are memoized gains speed
for a higher use of memory space.

The memoization only can be used in pure functions, so the first point is known
that is a pure function

In the following animation you can see the final result of applied memoization
in our code.

What is a pure function?

A pure function is a function that meets the following criteria:

It is a function that always returns the same result when the arguments are the same. For example, the following functions are impure:

Functions which use random numbers.
Functions which use datetime as seed to generate the result.

It is a function that does not produce side effects in the application:

Data mutation or change application state.
Network request.
Database or file request.
Obtaining user input.
Querying the DOM.

Benefits

The pure functions are being used in the web develop due to several benefits.
Although, the pure functions are not only use in the web develop. Well, the main
pure function’s benefits are:

Your code is more declarative which is focus in what must to do and doest not in how must to do. Also, the functions are focus in how different inputs are related to outputs.
The code is more testability, and find bugs is more easy that in impure functions.

But, in the real life there are side-effects and it is a good part of the code
(for example, when you access to the database or communicate different servers
to request information about the system). So, pure functions are a part of your
code, and you need to know when you can use a pure functions and when you can
use memoization in your code.

Pure functions example

Recursive functions frequently use the pure functions, the most classical
recursive problem is the factorial.

But the imperative version of the function factorial is pure too, because the
pure functions is related with inputs and outputs. In both case when the input
is the same the output will be the same.

Another interesting examples of pure functions are the following:

Memoization in recursive functions

The memoization is the programming technique which allows doesn’t recalculated
the value of the pure function. I.e, the pure functions returns the same value
when have the same inputs. So, the value return can be store in the system using
any cache system (for example a map or array). So, if you calculate the value of
factorial(1) you can store the return value 1 and the same action can be
done in each execution. So, when you run the factorial(100) you take a while the
first time but the second and more times the time will be reduced!

In this case, if you note the recursive factorial version, you can note that
this version execute several times the function factorial which can be cache
in our system (using memoization) but if you use the imperative factorial
version your performance will be worse. For this reason, memoization is a good
known technique in declarative languages.

Memoization Example! — Live code!

In this section I’m going to show you how implement memoization using closure
and the decorator pattern using JavaScript.

The decorator pattern allows add new features to any object in runtime using
composition instead of hierarchy. The pattern goal is avoid create a class
hierarchy of our features.

A good example to understand this pattern can be found in the Addy Osmany’s
Blog.

So, a basic implementation of memoize decorator in JavaScript is the following:

Define the cache in which the execution’s result will be store. We use a object as map to store this results.
The decorator returns a new function which has the same behaviour that original function but memoization is implemented.
The key of the key-value map is generated using the stringify and args from the original function.
The result of the new function will be
The execution of the original function (fn(...args)) whether there is not store in the cache.
The value stored in the cache (whether there is pre-calculated previously).
The result is returned.

How to used our `memoized` decorator ?

The way to used this decorator using JavaScript is very easy:

In this case the add function is the original function without memoization and
the addMemoized function is the new function which has the new feature
(memoization) using the decorator pattern.

A real demo using memoization!

Now, I’m going to show you a real deam using memoization. Imagine a complex
algorithm that indicate you if an array has a unique value (as the
Array.prototype.some) but horribly programmed.

The following step is run the original code and the code using memoization and
compare the time use in each function. It is very important remember that the
original code is not modified but the memoization feature is added.

The following function is used to measure the time used in each execution.

The array are generated at the begin of the script:

And finally, when the user click in a button the functions are execute.

No memoization

Memoization

The result is shown in the following animation:

Conclusions

The memoization has been widely developed in web development using TypeScript
or JavaScript. The following list of resources must be the starting point to
use them in your projects.

Fast-Memoize use this graph to compare different implementations of memoize:

The GitHub project is https://github.com/Caballerog/blog/memoization

Originally published at www.carloscaballero.io on February 8, 2019.

Hi! My name is Carlos Caballero and I’m PhD. in Computer Science from Málaga,
Spain. Teaching developers and degree/master computer science how to be experts!

Top comments (11)

Enrique Moreno Tent • Feb 23 '19 • Edited

Good job, important concepts explained with easy words.

Small improvements to your memoize method:

You rewrite the content of cache, even if the value was already saved. This is unnecessary, since the value does not change.
undefined is actually a valid value for a function response. Probably should use hasOwnProperty instead of cache[stringifiedParams] === undefined

Thanks for the article.

Carlos Caballero • Feb 24 '19

Hi Enrique!

Thanks for your words, the intend in this post is show the memoization concept (I think that you can find in your language/framework/tool this technique to applied in your project).

Respect your words in the memoize method:

Yes, It is not necessary re-saved the same value.
Yes, I think that is better use hasOwnProperty as you said!

At the moment, I could to do a new version to teach in my class. Thanks very much for your comments :-).

Mihail Malo • Feb 25 '19

I find it's best to use a Map or, for functions and other objects, a WeakMap.
The way I write my code, structural comparison will give almost no advantage, but JSON.stringify of huge objects will add overhead to every call (even a cache hit)

Carlos Caballero • Feb 25 '19

Hi Mihail!

Good catch! In fact, the lodash implementation (github.com/lodash/lodash/blob/508d...) use map.

In my article, I only wanted show the memoization technique when you've a pure function!

In case that you want use it in a real project, I think that lodash implementation is a good option.

Mihail Malo • Feb 25 '19 • Edited

I have so many comments about that function :/

Line 58 is redundant if they also do line 62. It seems they kept this redundancy through the last commit to that function
You can only set memoize.Cache, but can't set it in the call to memoize (like memoize(fn, resolver, cacheClass))
You can't pass in an existing cache like memoize(fn, resolver, cacheInstance), which would be more flexible and no less ergonomic.
Line 55: memoized.cache = cache.set(key, result) || cache What if my custom cache returns a truthy value that isn't itself? For example if it returns result value? Why not just set it to cache, what does this achieve? Supporting an immutable cache?

The closest I'd go with is something like this:

export const memoize = ({
  resolver,
  cacheClass = Map,
  cacheFactory = () => new cacheClass()
} = {}) => func => {
  const cache = cacheFactory()
  return typeof resolver === "undefined"
    ? arg => {
        if (cache.has(arg)) return cache.get(arg)
        const result = func(arg)
        cache.set(arg, result)
        return result
      }
    : (...args) => {
        const key = resolver(...args)
        if (cache.has(key)) return cache.get(key)
        const result = func(...args)
        cache.set(key, result)
        return result
      }
}

I don't think this support should be there by default, especially passing this both to the resolver and the function.
Maybe this 😂👌:

export const memoize = ({
  resolver,
  cacheClass = Map,
  cacheFactory = () => new cacheClass()
} = {}) => func => {
  const cache = cacheFactory()
  return typeof resolver === "undefined"
    ? func.hasOwnProperty("prototype")
      ? function(arg) {
          if (cache.has(arg)) return cache.get(arg)
          const result = func.call(this, arg)
          cache.set(arg, result)
          return result
        }
      : arg => {
          if (cache.has(arg)) return cache.get(arg)
          const result = func(arg)
          cache.set(arg, result)
          return result
        }
    : func.hasOwnProperty("prototype")
      ? resolver.hasOwnProperty("prototype")
        ? function(...args) {
            const key = resolver.apply(this, args)
            if (cache.has(key)) return cache.get(key)
            const result = func.apply(this, args)
            cache.set(key, result)
            return result
          }
        : function(...args) {
            const key = resolver(...args)
            if (cache.has(key)) return cache.get(key)
            const result = func.apply(this, args)
            cache.set(key, result)
            return result
          }
      : (...args) => {
          const key = resolver(...args)
          if (cache.has(key)) return cache.get(key)
          const result = func(...args)
          cache.set(key, result)
          return result
        }
}

Obviously a combinatorial explosion, but that is my point - most of the time you won't use most of the features anywhere in your entire project, so it's better to write your own function. Maybe you want to use a WeakMap of Maps, or vice versa, instead of a resolver.

Memoization is already not a business logic requirement but a performance optimization. So why waste performance on a suboptimal generic solution instead of improving your algorithm by inlining a cache?

Ritikesh • Mar 9 '19

Hey, nice article. I've implemented a slightly tweaked version of memoization as well, you can read more about that here: dev.to/ritikesh/why-just-cache-whe....