Subtle art of performance wins

Today I learned more about the subtle art of javascript performance. I have been doing a few algorithm challenges on freeCodeCamp, which is a great resource. Whilst completing one titled “Intermediate Algorithm Scripting: Smallest Common Multiple” I had a look at what other solutions people had posted, and how they compared to mine. A user had put together a CodePen running BenchmarkJS that contained about four solutions. I added my solution (below) to the benchmark test and the results were surprising.

My initial solution

// smallestCommonsOriginal
function smallestCommons(arr) {
  const [smallest, largest] = arr.sort((a, b) => a - b);
  const dividedByAll = (sum, sequence) => {
    for (let i = sequence[0]; i <= sequence[sequence.length - 1]; i++) {
      if (sum % i !== 0) {
        return false;
      }
    }

    return true;
  };

  const sequence = [];
  // Generate numbers between
  for (let i = smallest; i <= largest; i++) {
    sequence.push(i);
  }

  let lowestCommonFound = false;
  let sum = largest * (largest - 1);

  // loop until the common is found
  while (lowestCommonFound === false) {
    lowestCommonFound = dividedByAll(sum, sequence);
    if (lowestCommonFound) {
      return sum;
    }

    sum = sum + largest;
  }
}

smallestCommons([1, 5]); //should return 60
smallestCommons([5, 1]); //should return 60
smallestCommons([2, 10]); //should return 2520
smallestCommons([1, 13]); //should return 360360
smallestCommons([23, 18]); //should return 6056820

The freeCodeCamp advanced solution

const smallestCommonsAdv = arr => {
  let max = Math.max(...arr);
  let min = Math.min(...arr);
  // Initially the solution is assigned to the highest value of the array
  let sol = max;

  for (let i = max - 1; i >= min; i--) {
    // Each time the solution checks (i.e. sol%i===0) it won't be necessary to increment 'max' to our solution and restart the loop
    if (sol % i) {
      sol += max;
      i = max;
    }
  }
  return sol;
};

Against the advanced solution to the challenge, my solution ran approx. 2.5x slower. Which was disappointing!

// Running with benchmark.js
smallestCommons x 1,971,923 ops/sec ±1.55% (61 runs sampled)
smallestCommonsAdv x 5,100,845 ops/sec ±0.58% (63 runs sampled)

So I proceeded to refactor my solution. I tried a few things - running the loops in reverse and not generating an intermediate sequence. There is more I could have done, but I did not want to completely rewrite the function. This refactor had an improvement, but not as much as I hoped.

My refactored solution

// smallestCommonsRefactor
function smallestCommons(arr) {
  const [min, max] = arr.sort((a, b) => a - b);
  const dividedByAll = (sum, min, max) => {
    for (let i = max; i >= min; i--) {
      if (sum % i !== 0) {
        return false;
      }
    }

    return true;
  };

  let lowestCommonFound = false;
  let sum = max * (max - 1);

  // loop until the common is found
  while (lowestCommonFound === false) {
    lowestCommonFound = dividedByAll(sum, min, max);
    if (lowestCommonFound) {
      return sum;
    }

    sum = sum + max;
  }
}

The refactored solution now ran 2.2x slower than the advanced solution. An improvement of approx. 12% over my original solution. A slight win 🎉.

// Running with benchmark.js
smallestCommonsOriginal x 1,971,923 ops/sec ±1.55% (61 runs sampled)
smallestCommonsRefactor x 2,328,185 ops/sec ±0.70% (61 runs sampled)
smallestCommonsAdv x 5,100,845 ops/sec ±0.58% (63 runs sampled)

I looked at the advanced solution. One of the main differences between mine and theirs was the initial sorting of the incoming array. I was using Array.prototype.sort whereas they used native maths functions Math.max() and Math.min(). This got me intrigued. So I refactored once more to include this change.

My final solution

// smallestCommonsMinMax
function smallestCommons(arr) {
  const [min, max] = arr.sort((a, b) => a - b);
  const dividedByAll = (sum, min, max) => {
    for (let i = max; i >= min; i--) {
      if (sum % i !== 0) {
        return false;
      }
    }

    return true;
  };

  let lowestCommonFound = false;
  let sum = max * (max - 1);

  // loop until the common is found
  while (lowestCommonFound === false) {
    lowestCommonFound = dividedByAll(sum, min, max);
    if (lowestCommonFound) {
      return sum;
    }

    sum = sum + max;
  }
}

Running (smallestCommonsMinMax) this solution in the benchmark suite gave these results.

// Running with benchmark.js
smallestCommonsOriginal x 1,971,923 ops/sec ±1.55% (61 runs sampled)
smallestCommonsRefactor x 2,328,185 ops/sec ±0.70% (61 runs sampled)
smallestCommonsMinMax x 4,293,900 ops/sec ±1.34% (62 runs sampled)
smallestCommonsAdv x 5,100,845 ops/sec ±0.58% (63 runs sampled)

My final solution (smallestCommonsMinMax) was now only 1.18x slower than the advanced solution. This was an improvement of 52.8% over my original solution. That is a lot better. Maybe if I continued with this I would eventually write a solution that was faster than the advanced solution, but for now this satisfies my curiousity.

To finish it all off, I wrote a benchmark test to compare sort against min/max. The results speak for themselves.

// Running with benchmark.js
arraySort x 3,183,926 ops/sec ±4.44% (56 runs sampled)
minMax x 10,454,070 ops/sec ±0.52% (63 runs sampled)

The benchmark test

function run() {
  const suite = new Benchmark.Suite();
  const output = document.getElementById("console");
  const winner = document.getElementById("winner");

  // Add functions to test
  function arraySort(arr) {
    return arr.sort((a, b) => a - b);
  }

  function minMax(arr) {
    return [Math.min(...arr), Math.max(...arr)];
  }

  // add tests
  const input = [14, 7];

  suite
    .add("arraySort", function() {
      arraySort(input);
    })
    .add("minMax", function() {
      minMax(input);
    })

    // add listeners
    .on("cycle", function(event) {
      const p = document.createElement("p");

      p.innerText = String(event.target);
      output.append(p);
    })
    .on("complete", function() {
      const p = document.createElement("p");

      p.innerHTML = `✨ 👑 Fastest is <strong>${this.filter("fastest").map(
        "name"
      )}</strong> 🦄 ✨`;
      winner.append(p);
    })

    // run async
    .run({ async: true });
}

window.addEventListener("DOMContentLoaded", event => {
  run();
});

In conclusion

I learnt a lot from this, but there are no specific takeaways. Performance is hard, and you really need to understand a programming language deeply to be able to write fast code. Just writing a function that uses one language feature over another could make the function 2.5x slower.

This is just at the script level. Compound on top of that frameworks, 3rd party plugins, CSS, HTML, browsers, bandwidth, device bottlenecks, etc and it is not surprising that modern web pages can be slow and fair from performant.

But it proves that it is worth it to try and make improvements to the areas you have control over.