Part 1: Discovery
Learning JavaScript after JAVA was like entering Hogwarts after living in the muggle world — shifting staircases, talking portraits, elusive “this” context, functions that are objects and classes that are functions…. My head spun for a while, but at last with the basics out of the way I began to see the beauty of JavaScript — the spread operator, the infinite ease of functional programming, the up-and-go nature of the language. I was slowly falling in love. But no relationships exist without quarrels, and JavaScript and I just had our first one.
It started with a review of a blog post my friend has been working on about using memoization for optimizing recursive algorithms. In this post, Shmuel was talking about a memoization technique for caching results of a function based on arguments (link to be added once his post is live). He gave an example of a common pattern that utilizes higher order functions to “upgrade” the original function and enable an internal storage (or cache) that is queried every time the function is called. If the set of arguments already exist in the cache, the cached value is returned. Otherwise, the function is run and the results are persisted in the cache before being returned to the caller.
The code for the function is this:
function memoize(funcToCache) {
const cache = {};
return function(...args) {
if(cache[args]) return cache[args];
const result = funcToCache.apply(this, args);
cache[args] = result;
return result;
}
}It seemed like a reasonable approach at first, but something didn’t feel right. The “cache” in the snippet above is a JavaScript object. And JavaScript objects have a very serious limitation — all their keys are, in essence, strings. No doubt experienced JavaScript developers are well familiar with this “feature”. For me, however, it was a bit of a shock. I spent the next 30 minutes on repl.it trying to convince JavaScript objects that not all object-type keys are created equal. It didn’t work.
Experimentation showed that if an instance of an object is being passed as a key to another object — the instance will have its toString method invoked, and the result of THAT invocation will be used as the key. That lead to a glaring shortcoming — any instance of any object will always return the same value from the default Object.prototype.toString implementation. Specifically, Object.prototype.toString always returns ‘[object: Object]’. Therefore, the result of the following code:
const test = {};const key1 = { prop1: "Prop1" };
const key2 = { prop2: "Prop2" };
const key3 = { prop3: "Prop3" };//Setting objects as keystest[key1]="object1";
test[key2]="object2";
test[key3]="object3";console.log(test);
Is this:
{ ‘[object Object]’: ‘object3’ }
All three different objects were mapped to the same key! How did the memoize function work to begin with? Well, there is a chain of toString methods that is being called. args is an array-like object whose string representation will include the toString values of all items it holds. If the items being held are primitive types — such as strings or numbers, then their toString representation will be the value itself. For an algorithm that works exclusively on primitives, memoize allows proper caching since the only time toString will return equal string representations is when the underlying values are the same. Thus, 5 and 2 will never become the same key.
const cache = {};
cache [5] = "5";
cache [2] = "2";
console.log(cache);The result shows that numbers:
{ 2: '2', 5: '5' }If a recursive function accepts objects, however, then caching using the above pattern is completely wrong. It will hold only one key:value pair regardless of how many values we try to cache. Certainly not our goal.
Part 2: Possible solutions
What is our goal? To properly cache multiple objects. Seems easy enough, until we actually try it. When creating a cache able to handle multiple objects as keys we are faced with two major problems:
- We cannot use an object as cache, because all keys in an object are stringified. This results in all keys of type object being converted to the same string, leaving our cache unable to discern between multiple objects.
- We do not have a uniform way for comparing two distinct objects other than the loose equality and strict equality operators (== and ===). As of ECMAScript 6, there is an
Object.ismethod. However, it is a static method intended to complement strict equals (===) with respect to NAN and +/-0 and does not provide extendable functionality for instances of Object.
How can we address these issues?
1. Object.prototype.toString
If the caching functionality is specific to a particular project, it is possible to override the default Object.prototype.toString behavior to return a String that represents an object more specifically than ‘[object: Object]’. Thus, we can allow each object’s own toString method to return something that will be unique for this specific object instance. Modifying code from above, we get:
const test = {};const key1 = { prop1: "Prop1" };
const key2 = { prop2: "Prop2" };
const key3 = { prop3: "Prop3" };Object.prototype.toString = function () {
const keys = Object.keys(this);
let ret = "";
for (let i in keys) ret += ` ${keys[i}: ${this[keys[i]]}`;
return ret;
}test[key1]="object1";
test[key2]="object2";
test[key3]="object3";console.log(test);
Notice the overridden Object.prototype.toString method. Also, notice the desired output! All three objects have now been properly cached.
{ ‘ prop1: Prop1’: ‘object1’,
‘ prop2: Prop2’: ‘object2’,
‘ prop3: Prop3’: ‘object3’ }Modifying the default behavior of Object.prototype.toString might not be optimal, however. Every object in the program will now have the custom toString implementation and might produce unpredictable results in other parts of the program that rely on default implementation of Object.prototype.toString functionality.
2. Wrapper class
An alternative approach is to create a special wrapper class to store the objects that are planned to be cached and to override the toString method only for that particular class. This will achieve similar results as above, but without global modification of all instances of Objects.
//Creating a wrapper for the key that will return object's key: //value pairs from toString method.class KeyObject {
constructor (obj) {
this.obj = obj;
} toString () {
const keys = Object.keys(this.obj);
let ret = "";
for (let i in keys)
ret += ` ${keys[i]}: ${this.obj[keys[i]]}`;
return ret;
}
}//modifying our example from above, using custom class as a wrapper
//for the object keyconst test = {};
const key1 = new KeyObject ({ prop1: "Prop1" });
const key2 = new KeyObject ({ prop2: "Prop2" });
const key3 = new KeyObject ({ prop3: "Prop3" });test[key1]="object1";
test[key2]="object2";
test[key3]="object3";console.log(test);
Still three objects in cache, but no global Object.prototype.toString modifications.
3. Map as cache
There is yet another approach! With ECMAScript 6, core JavaScript has added two new classes — Map and Set. Since we’re looking to cache key:value pairs, Map is our class. Let’s try the following code:
const map = new Map ();//Check what happens when we use primitive keys
map.set (1, 1);
map.set (1, 2);//Check what happens when we use object keys
map.set ({1:1}, 1);
map.set ({1:1}, 2);
The output is as follows:
Map { 1 => 2, { 1: 1 } => 1, { 1: 1 } => 2 }For primitive types, the second entry overrode the first. For object types — both were preserved. This is certainly better. We expect overriding behavior for primitives — after all, a 1 is a 1. And having each object treated as a unique key is a step in the right direction.
Let’s note that the objects that were used as keys have the same properties, however, they were treated as distinct keys. We can draw a reasonable conclusion that the equality of two object keys is determined by a mechanism that is very similar to a strict equals (===) and relies on memory addresses. In this case, two objects will always be treated as distinct unless they are one and the same object in memory.
At this point we need to determine the degree of “uniqueness” our object-keyed cache requires. Using default toString method of an object was not enough. However, comparing object keys by memory addresses might be way too much. Specifically, the memoize function uses args object as the key which is a new array-like object at every call. So even if we pass the same object into memoize function twice, it will be stored twice because it comes into the function as an item in a new args object. Consider the following example:
function memoize(funcToCache) {
const cache = new Map();
return function(...args) {
if(cache.has(args)) return cache.get(args);
//output for testing purposes
console.log('NOT FOUND: ', args); const result = funcToCache.apply(this, args);
cache.set(args, result);
return result;
}
}function fib (n) {
if (n <= 1) return 1;
return fib (n-1) + fib (n-2);
}fib = memoize (fib);
fib (5);
Output:
NOT FOUND: [ 5 ]
NOT FOUND: [ 4 ]
NOT FOUND: [ 3 ]
NOT FOUND: [ 2 ]
NOT FOUND: [ 1 ]
NOT FOUND: [ 0 ]
NOT FOUND: [ 1 ]
NOT FOUND: [ 2 ]
NOT FOUND: [ 1 ]
NOT FOUND: [ 0 ]
NOT FOUND: [ 3 ]
NOT FOUND: [ 2 ]
NOT FOUND: [ 1 ]
NOT FOUND: [ 0 ]
NOT FOUND: [ 1 ]We are passing the same number into the function multiple times, however it caches it over and over again! That is, unfortunately, an impractical memoization implementation.
4. Custom cache class
We need a middle ground — to compare two objects based on a custom definition of equality that is more specific than default toString based implementation for cache keys, but not as narrow as comparison by ===. Consider, for example, two objects whose own property keys and values are the same. Can we consider these objects as equal keys? Let’s, and let’s see what happens.
We might still want to leverage the default JavaScript Map class since it probably has space and runtime optimizations that we’d like to take advantage of. However, we can add pre-processing to our key data to allow distinct objects with same property keys and values to be considered as the same key.
The pre-processing method will take an object as a parameter and return a primitive type. That is necessary because the underlying Map class needs a key that could be compared by value, not reference. Otherwise we will never get two equal keys and pre-processing would be useless. For our purposes, we can leverage JSON.stringify function to convert objects into their JSON representations and use that as keys. Since JSON.stringify returns strings and strings are primitive types in JavaScript, we will be able to check equality by value.
Not all methods in Map class require pre-processing. Those that do not deal with keys directly do not need to be modified.
The best way to implement our custom cache is through extension. We will override all methods that deal with keys:
Map.prototype.delete()Map.prototype.get()Map.prototype.has()Map.prototype.set()
Below is one proposed implementation of such cache.
class Cache extends Map{
constructor (array) {
super (array);
} delete (key) {
return super.delete (this.preProcess(key));
} get (key) {
return super.get(this.preProcess(key));
} has (key) {
return super.has(this.preProcess(key));
}
set (key, value) {
return super.set (this.preProcess(key), value);
} /*
This is the method that will convert an object into a custom key. It takes a parameter and returns it's processed key value. If the type of parameter is primitive, it will return it unchanged. Otherwise, the JSON.stringify will be called on the argument and the resulting value will be returned.
*/
preProcess (key) {
if (typeof key === 'object') {
return JSON.stringify(key);
} else {
return key;
}
}
}
Let’s implement the above memoization function with our new Cache class and see how our cache stores objects.
function memoize(funcToCache) {
const cache = new Cache(); //NOTE THE CHANGE HERE!!!
return function(...args) {
if(cache.has(args)) return cache.get(args);
//output for testing purposes
console.log('NOT FOUND: ', args);const result = funcToCache.apply(this, args);
cache.set(args, result);
return result;
}
}function fib (n) {
if (n <= 1) return 1;
return fib (n-1) + fib (n-2);
}fib = memoize (fib);
fib (5);
The result is quite exciting!
NOT FOUND: [ 5 ]
NOT FOUND: [ 4 ]
NOT FOUND: [ 3 ]
NOT FOUND: [ 2 ]
NOT FOUND: [ 1 ]
NOT FOUND: [ 0 ]“NOT FOUND” is printed only once per key, which means that our caching worked! And we know it cached each entry as an object because, as we noted above, memoize passes args, an array-like object, into the cache, not the primitive number itself.
Part 3: Conclusion
Let’s take stock of our approaches and consider benefits and tradeoffs.
- Initial implementation of the memoize function allowed proper caching for primitive types, but could not cache objects correctly.
- Modifying
Object.prototype.toString()allowed for custom string representation of objects but made the change global which could, potentially, adversely affect other parts of a program. - Built-in JavaScript Map class cached primitives properly, but can only compare objects by reference and cannot handle custom equality checks.
- Wrapper class with custom toString implementation was a safer approach than modifying
Object.prototype.toString, and could be used effectively in a memoization function that requires objects as keys. However, a wrapper class inside a memoization function that uses a plain object as cache is limited to converting object keys to strings. - Custom Cache class adds pre-processing of keys that converts an object into a primitive type that can be compared by value by the default Map methods. Unlike the wrapper class implementation, it is not limited to converting objects to strings only (Using
JSON.stringifyfor pre-processing was just one example). Pre-processing can convert an object into any primitive type and is thus more flexible than the wrapper class solution.
Perhaps in one of the futures versions JavaScript will support Maps and Sets with custom comparators, or will allow developers to uniformly define custom compare functionality for objects. JavaScript is rapidly gaining popularity as a backend language and will, I believe, eventually support data structures that reflect the required flexibility and extension.
After spending the day talking to JavaScript about key comparison in objects, I think we hashed out our differences and are on friendly terms once more. Thank you for reading through this! And code on!