Optimizing Search in JavaScript
Tags: agile, tdd, javascript, skiplist
Published: 2018-09-10 12:40:31

---
title: Optimizing Search in JavaScript
published: true
description: JavaScript is like a zombie virus. The language has taken over everything. And, my hand has a bite. Do I embrace my inner JavaScript kitty, become what I have always feared, or should I chop it off while I have a chance?
tags: agile, tdd, javascript, skiplist
---

*[Originally Posted on Skiplist blog](https://www.skiplist.com/blog/optimizing-search-in-javascript)*

[Skiplist](https://www.skiplist.com/) is JavaScript all the way down.

It is like a zombie virus. The language has taken over everything. And, my hand has a bite. Do I embrace my inner JavaScript kitty, become what I have always feared, or should I chop it off while I have a chance?

This week I optimized an in memory cache lookup. The customer dataset was a few orders of magnitude larger than anticipated. As a result, we had to refactor an in memory cache data structure.

The initial version of the cache was pair programmed and driven via TDD. *I like to embrace my inner agile technical coach when I can.* It may only be a coincidence, but it was easy to refactor the implementation details such that lookups now occur in constant time. **Some technical details of the optimization trick are described below.**

---

The source for example below can be found [here in GitHub](https://github.com/DEV3L/node-kata/tree/master/search-optimization/src).

# Declarative Programming

Imperative tells the how. Declarative code tells the what.

Let's look at an example, gathering the ages of three people:

```javascript
const people = [
  {id: 1, name: "Jason", age: 38},
  {id: 2, name: "Justin", age: 34},
  {id: 3, name: "Josh", age: 33}
]

// imperative
const ages = []
for(let person of people) {
	ages.push(person.age);
}

// declarative 
const ages = people.map(person => person.age)
```

JavaScript offers a few of built in declarative helper functions: 

- **[map()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map)**
- **[reduce()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce)**
- **[filter()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/filter)**
- **[forEach()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/forEach)**
- **[find()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/find)**

The indoctrinated claim, declarative code is expressive, elegant, and functional... "[clean](https://www.pluralsight.com/blog/software-development/7-reasons-clean-code-matters)". I agree, not caring how the sausage is made allows you to enjoy it that much better! Yet, there are times when the how is important.

# Using Find to Search for a Value

What about a similar scenario where you are looking up a person by id in list of a million entries?

```javascript
const idToFind = 1000000
person = people.find(person => person.id === idToFind);
```

The above statement is clean, find the first person whose id is 1000000. In contrast, the imperative approach to the same linear search is about half a dozen more lines of code. Simple is awesome. Simple is clean. But, Big(O) notation ("[Big O Notation](https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/)") tells us [linear search](http://www.bradoncode.com/blog/2012/04/big-o-algorithm-examples-in-javascript.html) is literally the worse. **We sacrifice performance for cleanliness, which is the trade off I pesonally will pick 99.8% of the time.** #empatheticprogramming

If the keys are unique and our data set is of a manageable size, we can increase performance by turning our list of people into a map of people by id, then perform a hash lookup, O(1), on the id! We have at worse, a one time O(n) arrangement step, and then O(1) lookup on each record.

# Code Example

As good stuarts of [software craftsmanship](http://manifesto.softwarecraftsmanship.org/), let's start off with a failing [JavaScript Unit Test](https://codeburst.io/javascript-unit-testing-using-mocha-and-chai-1d97d9f18e71) to assert the expected behavior.

```javascript
const assert = require('assert');
const Search = require("./search");

describe('Search', function () {
  const people = [];

  before(() => {
    people.push({id: 1, name: "Jason", age: 38});
    people.push({id: 2, name: "Justin", age: 34});
    people.push({id: 3, name: "Josh", age: 33});
  });

  it('should return the correct element', function () {
    const expectedName = "Justin";
    const search = new Search(people);
    
    const person = search.find(2);
    
    assert.equal(expectedName, person.name);
  });
});
```

### Imperative 

At this point, we have a red test. Let's implement our first approach, a traditional imperative search using a for loop.

```javascript
class Search {
  constructor(people) {
    this.people = people;
  }

  find(id) {
    for(let person of this.people) {
      if(person.id === id) {
        return person;
      }
    }
  }
}

module.exports = Search;
```

I setup a test harness to evaluate performance.

```
// performance output:
// >>> Average time for find for 3 records: 0.001 ms
// >>> Total time for find for 3 records: 2 ms
// >>> Average time for find for 1000000 records: 2.617 ms
// >>> Total time for find for 1000000 records: 2906 ms
```


### Declarative

We have a green test that asserts the behavior and a performance test harness, we are free to move about the cabin (*refactor the internals of the `find` method*)! **Moving from imperative to declarative looks like:**


```javascript
// ...

  find(id) {
    return this.people.find(person => person.id === id);
  }

// ...
```
```
// performance output:
// >>> Average time for find for 3 records: 0.001 ms
// >>> Total time for find for 3 records: 2 ms
// >>> Average time for find for 1000000 records: 2.356 ms
// >>> Total time for find for 1000000 records: 2690 ms
```

Our search time on a million records is relatively unchanged. With the move from imperative to declarative, we gain code cleanliness. The code now "tells the what" in such a way that swapping in a different data structure, like a map, is easier to conceptualize. We have a reduction in cognitive load.


### Optimized

Finally, what if we were performing this search within a nested loop of a large collection (this *never* happens!)? Two and a half milliseconds each on a search of even a few hundred records could easily degrade customer experience. So, let's look at our example using a map. An [array in JavaScript](https://www.w3schools.com/js/js_arrays.asp) is an associative array, so we can easily `map` the id as the key to the object.

```javascript
class Search {
  constructor(people) {
    const peopleMap = [];
    people.forEach(person => peopleMap[person.id] = person);
    this.people = peopleMap
  }

  find(id) {
    return this.people[id]
  }
}

module.exports = Search;

// performance output:
// Average time for find for 3 records: 0.001 ms
// Total time for find for 3 records: 2 ms
// Average time for find for 1000000 records: 0 ms
// Total time for find for 1000000 records: 302 ms
```

# Conclusion

I think my problem with JavaScript is not that I don't like it. I hate that I like it. I am scared with memories of pre browser standardization (IE6 ~2005 w/ ActiveX) JavaScript web development. I respect its current position within the development community and look forward to finding a common platform option at every layer of a solution.