image credit: Pascal van de Vendel

Why is this JavaScript so Slow?

JavaScript

There I was... in day two of performance improvements for a tree control in React. (React wasn't the culprit). This particular control does some processing on the incoming data and builds an internal structure and it was that processing that was taking too long.

I had already reduced the runtime from "I don't know... it crashes Chrome" to about 30 seconds. Infinitely better but still not even in the ballpark of acceptible. but at least at that point I could get something -- anything -- out of the Performance profiler in Dev Tools. With the help of the profiler, I had made a few more adjustments and had the runtime down to ~12 - 14 seconds.

Today, however, the profiler led me to something unexpected.

I had already anticipated having 'large' data sets... It was designed and tested to support 10,000 nodes (which would be rare but still possible in production) I had built it using react-virtualized to ensure that only the visible nodes are rendered.

But somehow, QA managed to break it. It turns out they were only sending about 2,500 items.

Now, I should point out that the data itself isn't strictly a tree structure. There's a lot of repetition in some of the leafs (meaning multiple branches contain any given leaf node) The proper name for it is a directed acyclic graph it just happens to be represented as a tree on the UI.

I ran some quick calculations... QA's input of 2500 items generated about 100,000 nodes overall. But 100,000 is not really a lot of data. Even JavaScript should be able to handle that amount of data very quickly.

Getting back to the profiler... Dev Tools was telling me that one particular function was basically taking all the time. Well, that's a good sign probably because it means I'm almost done.

Except, when I first looked at the code, I didn't see any obvious problems. See the function below. It takes a tree structure and builds a lookup map from a item's ID to itself.

makeMap = (items: Item[]) => {    const queue = [ ...items ];    const map = {};    while (queue.length > 0) {        const item = queue.shift()!;        map[item.id] = item;        if (item.children) {            queue.push(...item.children);        }    }    return map;}

Even now, looking back at the code, it doesn't appear to be that bad. There's nothing apparently sinister about it.

Maybe the redundancy was the issue, I thought. Surely, skipping duplicates would bring down the run time.

Wrong!

It had essentially the same run time with 2,500 vs 100,000 nodes.

Honestly, I was shocked. Dev Tools had taken me as far as it could. It was saying the function was the bottleneck but would get more specific. Other profilers I've used with other languages give line-by-line break downs.

Luckily it was only a few lines... so I instrumented the code myself.

makeMap = (items: Item[]) => {    const queue = [ ...items ];    const map = {};    const lines = [ 0, 0, 0 ];    const measure = (line: number, fn: Function) => {        const start = performance.now();        fn();        const delta = performance.now() - start;        lines[line] += delta;    };    while (queue.length > 0) {        let item: Item;        measure(0, () => {            item = queue.shift()!;        });        measure(1, () => {            map[item.id] = item;        });        measure(2, () => {            if (item.children) {                queue.push(...item.children);            }        });    }    console.table(lines);    return map;}

To my complete surprise (surprised that I should have known better), the table of timings had magnitudes roughly like this

(index) Value
0 10000
1 100
2 100

/facepalm

measure(0, () => {    item = queue.shift()!;});

Of course Array.prototype.shift() is the problem. Duh! It's great that JavaScript has methods like push(), pop(), shift(), and unshift() so you can use an array like a stack or a queue. But it's important to be mindful of the underlying implementation. JavaScript does a lot of work every time the head element is shifted out.

The solution was to use an incrementing index into the 'queue' instead of removing from it.

makeMap = (items: Item[]) => {    const queue = [ ...items ];    const map = {};    let i = 0;    while (i < queue.length) {        const item = queue[i++];        map[item.id] = item;        if (item.children) {            queue.push(...item.children);        }    }    return map;}

Measured again and all my timings are now in the ~100ms range.

Much better!

Level up Your React + Redux + TypeScript

for free with articles, tutorials, sample code, and Q&A.