re: Challenge: Write your worst program VIEW POST


Once, about a year ago (maybe less), I was writing a GreaseMonkey/TamperMonkey script to replace all occurrences of a given string in a web page, and I was treating the list of as-of-yet unscanned nodes as a queue. This was before I learned that Array.prototype.shift is about as ineffecient as you can get for getting elements out of a large array in JS. Suffice to say I learned the hard way just how bad it gets

  nodes = [document.body],
  res = [];

  scanned = 0,

while (n = nodes.shift()) {
  if (!n.scanned) {
    if (n.nodeType === Node.TEXT_NODE && !/^s*$/.test(n.nodeValue)) {
      n.scanned = true;
      const repl = replacers.filter(r => r.willRun(;
      if (repl.length) {
        res.push({ node: n, replacers: repl });
    } else if (
      n.hasChildNodes() &&
      ignoreTags.indexOf(n.tagName.toLowerCase()) === -1 &&
      ignoreClasses.every(c => !n.classList.contains(c))
    ) {

With the amount of work that things like replacers.filter(...) were doing, even after offloading the actual replacing work until after the loop, scanning the page (which at the time had roughly 194,000 nodes on it [and has only grown since then]) took anywhere between 60 and 90 seconds on page load.

After switching from a queue-based array to a stack-based array (by replacing nodes.shift() with nodes.pop(), the same page took about 4 seconds to scan.

I actually had an even worse-designed algorithm before this where I attempted to use nothing but Array.prototype methods and ended up iterating the result arrays multiple times, so the function to scan the page had something like a O(15n) runtime complexity. It was a very readable algorithm, though.

code of conduct - report abuse