Skip to content

Fast, small, efficient JavaScript memoization lib to memoize JS functions.

License

Notifications You must be signed in to change notification settings

thinkloop/memoizerific

Repository files navigation

Memoizerific.js

Build Status

Fast (see benchmarks), small (1k min/gzip), efficient, JavaScript memoization lib to memoize JS functions.

Uses JavaScript's Map() object for instant lookups, or a performant polyfill if Map is not available - does not do expensive serialization or string manipulation.

Supports multiple complex arguments. Includes least-recently-used (LRU) caching to maintain only the most recent specified number of results.

Compatible with the browser and nodejs.

Memoization is the process of caching function results so that they may be returned cheaply without re-execution if the function is called again using the same arguments. This is especially useful with the rise of [redux] (https://github.com/rackt/redux), and the push to calculate all derived data on the fly instead of maintaining it in state.

Install

NPM:

npm install memoizerific --save

Or use one of the compiled distributions compatible in any environment (UMD):

Quick Start

const memoizerific = require('memoizerific');

// memoize the 50 most recent argument combinations of our function
const memoized = memoizerific(50)(function(arg1, arg2, arg3) {
    // many long expensive calls here
});

memoized(1, 2, 3); // that took long to process
memoized(1, 2, 3); // this one was instant!

memoized(2, 3, 4); // expensive again :(
memoized(2, 3, 4); // this one was cheap!

Or with complex arguments:

const 
    complexArg1 = { a: { b: { c: 99 }}}, // hairy nested object
    complexArg2 = [{ z: 1}, { q: [{ x: 3 }]}], // funky objects within arrays within arrays
    complexArg3 = new Set(); // weird set object, anything goes

memoized(complexArg1, complexArg2, complexArg3); // slow
memoized(complexArg1, complexArg2, complexArg3); // instant!

Arguments

There are two required arguments:

limit (required): the max number of items to cache before the least recently used items are removed.

fn (required): the function to memoize.

The arguments are specified like this:

memoizerific(limit)(fn);

Examples:

// memoize only the last argument combination
memoizerific(1)(function(arg1, arg2){});

// memoize the last 10,000 unique argument combinations
memoizerific(10000)(function(arg1, arg2){}); 

// memoize infinity results (not recommended)
memoizerific(0)(function(arg1){}); 

The cache works using LRU logic, purging the least recently used results when the limit is reached. For example:

// memoize 1 result
const myMemoized = memoizerific(1)(function(arg1) {});

myMemoized('a'); // function runs, result is cached
myMemoized('a'); // cached result is returned
myMemoized('b'); // function runs again, new result is cached, old cached result is purged
myMemoized('b'); // cached result is returned
myMemoized('a'); // function runs again

Equality

Arguments are compared using strict equality, while taking into account small edge cases like NaN !== NaN (NaN is a valid argument type). A complex object will only trigger a cache hit if it refers to the exact same object in memory, not just another object that has similar properties. For example, the following code will not produce a cache hit even though the objects look the same:

const myMemoized = memoizerific(1)(function(arg1) {});

myMemoized({ a: true });
myMemoized({ a: true }); // not cached, the two objects are different instances even though they look the same

This is because a new object is being created on each invocation, rather than the same object being passed in.

A common scenario is when providing options like this: do({opt1: 10000, op2: 'abc'}).

If that function were memoized, it would never hit the cache because the options object would be newly created on each invocation.

To get around this you can:

Store Arguments Separately

Store complex arguments separately for use later on:

const do = memoizerific(1)(function(opts) {
    // function body
});

// store the options object
const opts = { opt1: 10000, opt2: 'abc' };

do(opts);
do(opts); // cache hit

Destructure

Destructure complex objects into simple properties then use the simple properties inside the memoized function to re-create the complex object:

const callDo = memoizerific(1)(function(prop1, prop2) {
  return do({prop1, prop2}); 
});

callDo(1000, 'abc');
callDo(1000, 'abc'); // cache hit

Internals

Meta properties are available for introspection for debugging and informational purposes. They should not be manipulated directly, only read. The following properties are available:

memoizedFn.limit       : The cache limit that was passed in. This will never change.
memoizedFn.wasMemoized : Returns true if the last invocation was a cache hit, otherwise false.
memoizedFn.cache       : The cache object that stores all the memoized results.
memoizedFn.lru         : The lru object that stores the most recent arguments called.

For example:

const myMemoized = memoizerific(1)(function(arg1) {});

myMemoized(1000, 'abc');
console.log(myMemoized.wasMemoized); // false
myMemoized(1000, 'abc');
console.log(myMemoized.wasMemoized); // true

Principles

There are many memoization libs available for JavaScript. Some of them have specialized use-cases, such as memoizing file-system access or server async requests. While others, such as this one, tackle the more general case of memoizing standard synchronous functions. Some criteria to look for when shopping for a lib like this:

  • Support for multiple arguments
  • Support for complex arguments: Including large arrays, complex objects, arrays-within-objects, objects-within-arrays, and any object structure, not just primitives like strings or numbers.
  • Controlled cache: A cache that grows unimpeded will quickly become a memory leak and source of bugs.
  • Consistent performance profile: Performance should degrade linearly and predictably as parameters become less favorable.

Two libs with traction that meet the criteria are:

✔️ Memoizee (@medikoo)

✔️ LRU-Memoize (@erikras)

Benchmarks

Benchmarks were performed with complex data. Example arguments look like:

myMemoized(
    { a: 1, b: [{ c: 2, d: { e: 3 }}] }, // 1st argument
    [{ x: 'x', q: 'q', }, { b: 8, c: 9 }, { b: 2, c: [{x: 5, y: 3}, {x: 2, y: 7}] }, { b: 8, c: 9 }, { b: 8, c: 9 }], // 2nd argument
    { z: 'z' }, // 3rd argument
    ... // 4th, 5th... argument
);

Tests involved calling the memoized functions thousands times using varying numbers of arguments (between 2-8) and with varying amounts of data repetition (more repetion means more cache hits and vice versa).

Measurements

Following are measurements from 5000 iterations of each combination of number of arguments and variance on firefox 44:

Cache Size Num Args Approx. Cache Hits (variance) LRU-Memoize Memoizee Memoizerific % Faster
10 2 99% 19ms 31ms 10ms 90%
10 2 62% 212ms 319ms 172ms 23%
10 2 7% 579ms 617ms 518ms 12%
100 2 99% 137ms 37ms 20ms 85%
100 2 69% 696ms 245ms 161ms 52%
100 2 10% 1,057ms 649ms 527ms 23%
500 4 95% 476ms 67ms 62ms 8%
500 4 36% 2,642ms 703ms 594ms 18%
500 4 11% 3,619ms 880ms 725ms 21%
1000 8 95% 1,009ms 52ms 65ms 25%
1000 8 14% 10,477ms 659ms 635ms 4%
1000 8 1% 6,943ms 1,501ms 1,466ms 2%
Cache Size                    : The maximum number of results to cache.
Num Args                      : The number of arguments the memoized function accepts, ex. fn(arg1, arg2, arg3) is 3.
Approx. Cache Hits (variance) : How varied the passed in arguments are. If the exact same arguments are always used, the cache would be hit 100% of the time. If the same arguments are never used, the cache would be hit 0% of the time.
% Faster                      : How much faster the 1st best performer was from the 2nd best performer (not against the worst performer).
Results

LRU-Memoize performed well with few arguments and lots of cache hits, but degraded quickly as the parameters became less favorable. At 4+ arguments it was up to 20x slower, enough to cause material concern.

Memoizee performed reliably with good speed.

Memoizerific was fastest by about 30% with predictable decreases in performance as tests became more challenging.

License

Released under an MIT license.

Related

  • Map or Similar: A JavaScript (JS) Map or Similar object polyfill if Map is not available.
  • Multi Key Cache: A JavaScript (JS) cache that can have multiple complex values as keys.

Other

  • todo-app: Example todo app of extreme decoupling of react, redux and selectors
  • link-react: A generalized link component that allows client-side navigation while taking into account exceptions

Like it, star it.