Marco Alka

Software Engineer, Technical Consultant & Mentor

Nov 21, 2017

So, first let me sort out your question. Am I correct?

How to optimise JS [..] execution times. I.e. [..] loops [..], strings, objects & arrays, DOM interaction and for/if methods

While you get the most performance out of algorithmic improvements, you can try to write better performance-optimized code even from the start, as long as you are careful to keep the code readable and maintainable. Also, if there is a bottleneck in one place and you don't know how to optimize the algorithm, knowing a few tricks can be beneficial. Though you might want to consider ditching JS for such performance-relevant code and use WASM or native Node modules instead!

Well then, here is what I know :) Some of the stuff below might lead to quite an aggressive optimization at the cost of readability and maintainability, so be sure that you really want to follow my tips.

Prefer built-in functions
- whatever you do, JS is interpreted or JIT compiled, and built-in functions are already compiled
- usually, built-in functions are very optimized
- built-in functions can make use of CPU instructions instead of software algorithms, which is the fastest you can get (usually)
Avoid branches
- branches always mean that a condition has to be evaluated instead of executing meaningful operations
- especially when the branch prediction fails, you will have extra costs
- every compiler has problems optimizing branches
Avoid functions
- functions make your interpreter jump around memory, which takes time
- small functions can easily be inlined
- try not to use functions when it's not necessary (for example enforcing const by putting the mutability into an arrow function)
Avoid recursion
- recursion clutters the memory with lots of function overhead, which means piles of memory have to be allocated and deallocated.
- instead, use an iterative approach, which is better for performance and resource usage
Unroll small loops
- again, unrolling means you get rid of the conditional, so fewer operations, so more speed
- also try to cache as much of the conditional as possible, if unrolling is not an option
Avoid string comparison
- Comparing strings means comparing every character, which is O(n); instead use a number or token, which is O(1)

Examples (ran bench 10 times and took average)

/// Built-In Functions (jsben.ch/fajXS - ~63% faster for me):

const arr = [1,2,3];

// Instead of
let sum = 0;
for (const num of arr) { sum += arr; }
// write
sum = arr.reduce((acc, num) => acc + num);

/// Branches (jsben.ch/h0SWo - ~14% faster for me):

const a = -5;
const b = 3;
let c = 1;

// Instead of
if (a < 0) { c += b * a; }
// write
c += b * Math.min(a, 0);

/// Functions (jsben.ch/thqBL - ~16-20% faster for me):

const obj = { a: 1, b: 2, c: 3, };

// Instead of
const a = (() => {
  let tmp = 0;
  for (const key in obj) {
    tmp += parseInt(obj[key]) || 0;
  }

  return tmp;
})();
// write
let a_tmp = 0;

for (const key in obj) {
  a_tmp += parseInt(obj[key]) || 0;
}

const a = a_tmp; // only if you really want a const...

/// Recursion (jsben.ch/Q1ODq - ~7% faster for me):

const arr = const arr = ((length, max) => [...new Array(length)]
    .map(() => Math.round(Math.random() * max)))(10000, 100);

// Instead of
function bubbleSortRecursive(array, index1, index2) {
    index1 = typeof index1 == 'undefined' ? 0 : index1;
    index2 = typeof index2 == 'undefined' ? array.length : index2;

    if (index1 > index2) {
        return array;
    } else if (index1 == index2 - 1) {
        return bubbleSortRecursive(array, 0, index2 - 1);
    } else if (array[index1] > array[index1 + 1]) {
        const temp = array[index1];
        array[index1] = array[index1 + 1];
        array[index1 + 1] = temp;
        return bubbleSortRecursive(array, index1 + 1, index2);
    } else {
        return bubbleSortRecursive(array, index1 + 1, index2);
    }
}
bubbleSortRecursive(arr);
// write
function bubbleSort(arr) {
  let sorted = false;
  const sort = (element, index, array) => {
    if (element > array[index + 1]) {
      array[index] = array[index + 1];
      array[index + 1] = element;
      sorted = false;
    }
  };

  while (!sorted) {
    sorted = true;
    arr.forEach(sort);
  }
}
bubbleSort(arr);

/// Loops 1 (jsben.ch/re3XJ - ~33% faster for me):

const arr = [1,2,3];

// Instead of
const sum = arr.reduce((acc, num) => acc + num);
// write
const sum = arr[0] + arr[1] + arr[2];

/// Loops 2:

const arr = ((length, max) => [...new Array(length)]
    .map(() => Math.round(Math.random() * max)))(10000, 100);

// Instead of
for (let i = 0; i < getNumSomething(); i++) { doSth(arr[i]); }
// write
const length = getNumSomething();
for (let i = 0; i < length; i++) { doSth(arr[i]); }

/// Strings (jsben.ch/yfNlX - ~8% faster for me)

const costCat = {
  banana: 3.5,
  apple: 1.25,
  salad: 2.76,
};

// Instead of
const price = costCat['banana'];
// write
const price = costCat.banana;

Marcus

Full Stack Developer

Nov 21, 2017

Are you sure you would want to avoid recursion? In every language I have ever worked with you want to avoid loops and the preferred method would be to use recursion.

Marcus To be honest, I have never read about recursion being better from a system-view. Well, it is often a lot easier to write a performant recursion than to write a performant iterative approach, especially for new developers (looking back at my first years, at least), and one could argue that a recursion looks cleaner and is easier to comprehend. However all that is not important when you only want to consider speed. Then it is important to know what your compiler or interpreter does and how things are laid out in memory. Quite the under-the-hood and hardware topic, really.

For example, one of the reasons why the iterative approach is better for performance and resource usage in many languages is in my opinion, that functions have a lot of overhead you can prevent with a clean iterative approach. For example, deep recursion can easily lead to lots of overflows (for example call stack overflow) in certain configurations, while the execution size of an iterative approach likely stays the same no matter the number of iterations. On top of that, every function called has to have its overhead (function stack, extra variables, etc.) initialized and freed in memory, so that's a lot of useless operations during a recursive operation.

As a kind of proof for my statement above, take Tail Call Optimization. It means, that a function returns the result of calling itself, however a compiler optimizes the function into an iterative loop in order to prevent call stack overflow. While that's the major reason for doing so, it also means that the function does not have to be initialized a million times, which means dropping millions times n of operations responsible for that.

// Example for TCO

iAmRecursiveDuh(0);

// This function could be tail call optimized 
function iAmRecursiveDuh(x) {
  if (x > 1000) return x;
  else          return iAmRecursiveDuh(x + 1);
}
// to be executed like this:
function iAmRecursiveDuh(x) { // actually iterative now
  while (x < 1000) x + 1;
  return x;
}

// which means
// -1000 function initializations
// -1000 variable allocations
// -1000 entries on the call stack
// the number of comparisons stays the same
// the number of additions stays the same
// so can you see the profit here?

However, if we can write recursions and use the JS interpreter's TCO, why did I still use recursion as a negative point here? The answer is simple. JS runs on many different interpreters, and most don't do TCO (Safari's interpreter does...). So doing TCO manually, as in writing an iterative approach, yields the same performance boost across all interpreters, no matter if they do TCO or not.

Search Hashnode