Javascript looping through large dictionary yields unresponsive script

Question

I'm making a firefox addon that appends words with other words in html text. This code works, but when iterating through an enormous dictionary, I get an unresponsive script error.

What is the best way to improve the speed of this loop?

Splitting up the dictionary into smaller objects? Or setting a timeout function?

var brands = {"manykeys" : "manyvalues"};

function replaceWord(){
    for (var key in brands){
        htmlreplace(key, key + " (" + brands[key] + ")");
    }
}
function htmlreplace(a, b, element) {    
    if (!element) element = document.body;    
    var nodes = element.childNodes;
    for (var n=0; n<nodes.length; n++) {
        if (nodes[n].nodeType == Node.TEXT_NODE) {
            var r = new RegExp(a, 'g');
            nodes[n].textContent = nodes[n].textContent.replace(r, b);
        } else {
            htmlreplace(a, b, nodes[n]);
        }
    }
}

replaceWord();

I strongly suspect what's slowing it down is the regex. Try it without it to see speed difference. — Noitidart, Mar 24 '14 at 04:46

score 0 · Answer 1 · answered Mar 24 '14 at 03:17

I haven't tried, but doing this might work:

function replaceWord(){
    for (var key in brands){
        (function(key) {
            setTimeout(function() {
                htmlreplace(key, key + " (" + brands[key] + ")");
            }, 0);
        })(key);
    }
}

The idea is that you postpone the replacing for when the browser has time for it, instead of doing it monolithically and making the browser freeze while it's thinking.

user13500 · Accepted Answer · 2014-03-24T07:09:25.293

There are some considerations to take. It depends a lot on what you can change or not. One of the bigger improvements you can do is using array instead of key/value object.

var brands = [
['manykeys0000','manyvalues0000'],
['manykeys0001','manyvalues0001'],
['manykeys0002','manyvalues0002'],
['manykeys0003','manyvalues0003'],
['manykeys0004', ...
];

function replaceWord(){
    var i, n = brands.length;
    for (i = 0; i < n; ++i) {
        htmlreplace(brands[i][0], brands[i][0] + " (" + brands[i][1] + ")");
    }
}

A couple of other changes should also give a tiny improvement:

1.) Move nodes.length outside the loop.
2.) If suitable pass document.body from replaceWord()

var body = document.body;

...
    htmlreplace(brands[i][0], brands[i][0] + " (" + brands[i][2] + ")", body);

function htmlreplace(a, b, element) {    
    var nodes = element.childNodes, len = nodes.length;
    for (var n=0; n < len; ++n) {

Combined quick benchmark on Chrome and Firefox gave a 30-40% increase in speed.

Other edits to test out:

Move var r = new RegExp(a, 'g'); to replaceWord(), and pass it as first argument to htmlreplace() instead of a.

function replaceWord(){
    var i, n = brands.length;
    for (i = 0; i < n; ++i) {
        var r = new RegExp(brands[i][0], 'g');
        htmlreplace(r, brands[i].join(' (') + ')', elem);
    }
}

If you play with timeout this article might be of interest. It uses

window.postMessage();

to implement a custom setZeroTimeout() but not sure how it will impact your case.

Beside JSPerf etc. use profiling tools in browser, for example in Chrome, which might be better suited for what you do in your code.

Err. That Chrome mangling is perhaps rather unsuited as this is for an Firefox addon. — user13500, Mar 25 '14 at 03:38
thanks. i'm wondering if my dictionary is just too big because my code still freezes. but this is a good answer. — user27524, Apr 08 '14 at 20:02

score 0 · Answer 3 · answered Mar 24 '14 at 07:36

The bottleneck in your code is not the dictionary size, unless it is really big, but the DOM traversal.

Get the text nodes once and then work with them.

var textnodes = $x("//text()", document.body)

function $x(p, context) {
  if (!context) context = document;
  var i, arr = [], xpr = document.evaluate(p, context, null, XPathResult.UNORDERED_NODE_SNAPSHOT_TYPE, null);
  for (i = 0; item = xpr.snapshotItem(i); i++) arr.push(item);
  return arr;
}

You should see a considerable speed improvement.

Javascript looping through large dictionary yields unresponsive script

3 Answers3