In my Binary Decision Diagram Library, the performance bottleneck was the uniqueness cache. By reducing the number of cache lookup, it is possible to greatly improve the performances.

Common pattern

In order to test if the key is already in the cache, the usual pattern is to use key in cache. This leads to the following code:

function cachedValue(key) {
  if (key in cache) {
    return cache[key];
  } else {
    var result;
    /* generate result */
    return cache[key] = result;
  }
}

Ideal cache lookup

The expensive operation with a cache is to traverse the data structure in order to find the position where the element should be. In the previous code, there are three independent lookups: key in cache and 2x cache[key].

In order to improve performance, the ideal would be to make that expensive lookup once, and do the test/get/set directly at that position.

function cachedValue(key) {
  var position = cache.lookup(key);
  if (cache.has(position)) {
    return cache.get(position);
  } else {
    var result;
    /* generate result */
    cache.set(position, result);
  }
}

Javascript Workaround

However, there is no API to directly manipulate the lookup and position. We have to find workarounds.

We remark that cache[key] will either return the value or undefined if not present in the cache. The belonging test no longer requires a full lookup, you only have to compare the value with undefined.

function cachedValue(key) {
  var result = cache[key];
  if (result === undefined) {
    /* generate result */
    cache[key] = result;
  }
  return result;
}

There is only one drawback: it is no longer possible to use undefined as a value in your cache.

Without temporary

If the result can be generated inline and your cache will never contains falsy values, you can use a shorter version. It should not impact performance however.

function cachedValue(key) {
  return cache[key] || (cache[key] = /* generate result */);
}

Conclusion

There are still two lookups done in case of a cache miss. If you find a way to factor the code in a way that removes it, I'm really interested in knowing 🙂

At the time of writing, the described technique is faster on all the tested browsers. As performance in browser rapidly evolve, check out the jsPerf entry before you decide to use it in your application.

If you liked this article, you might be interested in my Twitter feed as well.
 
 

Related Posts

  • September 24, 2011 Javascript: Cyclic Object Detection (13)
    URLON.stringify() suffer from a problem, when passed an object that contains a cycle, it will never stop. This article shows 3 techniques in order to detect if an object is cyclical. Edit the object: Mark In order to detect a cycle in an object, the method we learn at school is to […]
  • September 12, 2015 React Rally: Animated — React Performance Toolbox (4)
    I talk about various strategies to improve the performance of your React app: shouldComponentUpdate, Static Container, Element Caching, Raw DOM Mutations and finally, Data Binding, which is powering the Animated API. I go over their respective trade-offs as sadly there is no perfect […]
  • August 19, 2011 Javascript – Stupid Idea: Hoisting at the end (0)
    JSLint imposes us to do manual hoisting of variables. What if we did it but at the end of the function? :P How you write function print_array (array) { var length = array.length; for (var i = 0; i < length; ++i) { var elem = array[i]; console.log(elem); […]
  • September 25, 2011 Javascript Object Difference (5)
    This article is about a difference algorithm. It extracts changes from one version of an object to another. It helps storing a smaller amount of information. Template In a project, I have a template object with all the default settings for a widget. var template = { […]
  • September 22, 2011 URLON: URL Object Notation (43)
    #json, #urlon, #rison { width: 100%; font-size: 12px; padding: 5px; height: 18px; color: #560061; } I am in the process of rewriting MMO-Champion Tables and I want a generic way to manage the hash part of the URL (#table__search_results_item=4%3A-slot). I no longer […]