Efficiently iterate on Javascript arrays

In Javascript, arrays are one of the most widely used data structures.

Lire l'article en français

 

It is very common to have to iterate on the content of an array and this operation can be costly when handling arrays of several thousand elements.

 

As you know, at Kuzzle we are very careful about the performance of the code we develop for our products and even more so in the "critical code sections” that can potentially be executed several hundred times per second.

 

In this article, we will see the advantages and disadvantages of 3 arrays iteration methods.

 

TLDR;

  • Use Array.forEach in non-critical code areas
  • Use for (let i; ...; ...) in critical code areas

Method 1: Array.forEach

The first method is to use the Array.forEach method.

This method takes as a parameter a function that will be called with each element of the array.

 

array.forEach(item => {
  const foobar = item * 2;
});

 

In Node.js 12, this method offers very good performance and its use in the Kuzzle core is recommended for iterations on non-critical code sections arrays.

Method 2: for (const … of ...)

A second method is based on Javascript iterators accessible through the Symbol.iterator symbol.

 

If you have time, you can consult Keith Cirkel's very good article on symbols: https://www.keithcirkel.co.uk/metaprogramming-in-es6-symbols/

 

It allows you to iterate on all the elements of an array with a syntax that is pleasant to read and easy to understand.

 

for (const item of array) {
  const foobar = item * 2;
}

 

This method is the old favorite method in the core to browse the tables because in Node.js 6, the Array.forEach method was quite slow.

 

This is no longer the case in Node.js 12 and therefore the use of for (const ... of...) is deprecated in the core.

Method 3: for (let i; …; ...)

This method iterate on the array with the index of each element.

 

To do this, we use a for loop and a number i representing the index of the current element.

 

for (let i = 0; i < array.length; ++i) {
  const item = array[i];

  const foobar = item * 2;
}

 

This is the fastest non-destructive method of browsing an array.

 

However, it makes the code more complex to understand what has an impact on maintainability.

It is therefore only used in critical code sections.

Benchmark and conclusion

The benchmark of these methods is performed with Node.js 12.13.0 which we use by default in Kuzzle core:

 

node nodejs/loop-array.js

   for (let i) x          3,117,151 ops/sec ±0.66% (94 runs sampled)

   for (const of) x     817,769 ops/sec ±0.26% (98 runs sampled)

   Array.forEach x 2,297,760 ops/sec ±55.45% (93 runs sampled)

Fastest is while (for (const of))

 

 

 

 

The benchmark of the 3 previous methods is won by the for (let i; ...; ...) method which offers the best iteration performance. However, its complexity limits its use to critical code sections only.

 

In the rest of the Kuzzle core, we will use the Array.forEach method which offers good performance and above all a very good readability of the code.

 

 

All the code of these benchmarks is available on Gist.

Bonus: Create an array from another array

This benchmark is not really comparable to the others because it is only used to create an array from another array.
However, this is a case that occurs often enough to make a benchmark.

We saw together that it was the for method for (let i; ...;...) that brought the best performances.

In the specific case of building an array from another array, the Array.map method is the most efficient.

 

$ node loop-create-array.js

   foreach x             60,450 ops/sec ±8.91% (87 runs sampled)
  for (const of) x 112,013 ops/sec ±1.97% (84 runs sampled)
  for (let i) x        113,350 ops/sec ±2.63% (82 runs sampled)
  map x               153,657 ops/sec ±4.45% (78 runs sampled)
Fastest is map

 

See the benchmark code on Gist.

Adrien Maret

Related posts