Unrealistic / flawed cache benchmarking

[mfbx9da4]

The cache benchmarking has a few issues:

1. It only benchmarks small integers as keys of the underlying cache. This is my primary issue with the benchmarking. In my experience, I use memoization to avoid processing large in memory data structures. If the memoization function stringifies the incoming argument everytime, the stringification cost is highly likely to outweigh the performance benefits of memoization. Map is ideal for caching based on an object argument because v8 and other engines assign a random ID to every object under the hood and checking if it is the same object is as simple as comparing two ints. The cache benchmarking code should test massive objects as arguments to the memoization function.
2. It does not model key deletion. Map is specifically designed with key deletion in mind whereas hidden classes on objects are not so well suited to this. Keys are likely to be added and deleted a lot in a memoized function so it's important to model this.
3. It does not model the potential non-local performance impacts of using objects. In v8 the "megamorphic" cache system can become overloaded by the number of hidden classes and deoptimize code. I'm no v8 expert but I know enough to beware of microbenchmarking.

[ablakey]

I read this: https://community.risingstack.com/the-worlds-fastest-javascript-memoization-library/ and came to the same conclusion. It seems that almost every memoization library address the hard problems by ignoring them.

Serialization is incredibly expensive if you're trying to memoize non-trivial objects. In my case, megabytes of tens of thousands of GeoJSON features.

A solution I'm looking into is a tree of Map objects:

• Map keys by hash (but actually just a random ID that the JS engine assigns to the object), so it's an incredibly fast lookup.
• Multiple arguments supported where each Map lookup either returns a leaf (the memoized result or nothing), or a branch (another Map of all the second arguments), and then you just walk the tree until you find a leaf or nothing.
• This works based on identity, not equality. So it's very fast for when you're handling objects whose identity doesn't change (functional programming strategies)
• I think there might be a risk that we collect a LOT of Map objects if a memoized function is called with a lot of different arguments
• This doesn't yet consider how to clean up or set a cache maximum. Perhaps a secondary array would be needed to track branches and once n memoized results are recorded, we start culling branches.
• This is also a trade-off: it would give you wicked fast identity memoization, but not equality memoization.

If anyone's interested in chatting about this, I'm all ears. I think I will likely explore this practically and do some comparisons.

[mfbx9da4]

I built one based on a tree of maps as you say, it uses a linked list to know which paths to cleanup but there are several other options.

Memory leaks are definitely a consideration but also picking a good cache size. If you pick a cache size of n-1 and functions are executed in round robin you'll end up with constant cache misses. Often updating the cache size dynamically is important in such cases.

Another consideration is that if you have a very small cache size you might be better off just doing a nested for loop for finding a cache entry.

TL;DR: it really depends on your execution pattern

[ablakey]

Thanks for the details and links. I hadn't seen a few of those options. I found memoizee but just couldn't unravel how they do caching with efficient lookup. Looks like I get to spend my time doing something other than building yet another memo library =)

[ThomasF85]

FYI, we implemented benchmarking with more realistic data (memoized functions are being called with a set of 1000 different arguments over and over again, instead of with just one and the same or just a handful of different arguments). The results for fast-memoize are far from being the fastest: https://github.com/Animus-Blue/sonic-memoize