6 different array flattening methods in JavaScript, performance testing included

What is array flattening?

Array flattening is process of converting multi-dimensional array to single-dimensional array.

Single-dimensional array:

const arr = [1, 2, 3]

Multi-dimensional array:

const arr_2 = [1, [2, [3]]]

When you flatten arr_2 you get:

const arr_2_flattened = [1, 2, 3];

Performance testing

I have done a performance testing for each of the implementations that will follow.

function generateNestedArray(itemsPerLevel, levelsCount) {
    return new Array(itemsPerLevel)
        .fill(levelsCount < 2
            ? 0
            : generateNestedArray(
                itemsPerLevel,
                levelsCount - 1
            )
        );
}

Using generateNestedArray() method I have always tested 3 arrays with the following settings:

const arr_small = generateNestedArray(2, 10);
const arr_medium = generateNestedArray(2, 15);
const arr_big = generateNestedArray(2, 25);

It basically creates a nested array structure, where all the array elements are either an array or number 0. The first argument dictates how many elements each array has, the second argument how many levels (depth) the array has.

generateNestedArray(2, 2)
-> [ [ 0, 0 ], [ 0, 0 ] ]
-------------------------
generateNestedArray(2, 3)
-> [ [ [ 0, 0 ], [ 0, 0 ] ], [ [ 0, 0 ], [ 0, 0 ] ] ]
-------------------------
generateNestedArray(3, 3)
-> 
[
  [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ],
  [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ],
  [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]
]

I’ll be running the tests on Macbook Pro (15-inch, 2018), 2.2 GHz 6-core Intel Core i7, 16 GB 2400 Mhz DDR 4.

Array.prototype.flat

const arr1 = [1, 2, [3], [4, [5, [6]]]];
arr1.flat(); // [1, 2, 3, 4, [5, [6]]]
arr1.flat(2); // [1, 2, 3, 4, 5, [6]]
arr1.flat(Infinity); // [1, 2, 3, 4, 5, 6]
arr1.flat(0) // [1, 2, [3], [4, [5, [6]]]]; (no change)

Array.prototype.flat was introduced as part of ES2019.

It has one parameter which is depth and defaults to 1. If you pass 0 as depth, it makes no changes. If you want to flatten the array to the last level, pass Infinity as an argument.

Array.prototype.flat is not supported in Internet Explorer, but you can use a polyfill.

Array.prototype.flat browser support

⏱️ Performance testing:

arr_small ->  sec: 0, ms: 0.292118,   heap used: 2.63 MB
arr_medium -> sec: 0, ms: 8.264493,   heap used: 3.68 MB
arr_big ->    sec: 6, ms: 796.766301, heap used: 642.41 MB

Recursion + reduce + spread

function flatten(arr) {
    return arr.reduce((acc, cur) => {
        return Array.isArray(cur) 
            ? [...acc, ...flatten(cur)] 
            : [...acc, cur]
    }, [])
}

Main building blocks:

• Recursion
• Array.prototype.reduce
• Spread operator (…)

⏱️ Performance testing:

arr_small ->  sec: 0,  ms: 2.310682,  heap used: 2.43 MB
arr_medium -> sec: 0,  ms: 25.060814, heap used: 4.83 MB
arr_big ->    sec: 14, ms: 588.88459, heap used: 1977.12 MB

Recursion + IIFE

function flatten(arr) {
    const flattened = []

    !(function flat(arr) {
        arr.forEach(function (el) {
            if (Array.isArray(el)) flat(el)
            else flattened.push(el)
        })
    })(arr)

    return flattened
}

Main building blocks:

• Recursion
• IIFE (Immediately Invoked Function Expression)

⏱️ Performance testing:

arr_small ->  sec: 0, ms: 0.408722,   heap used: 2.7 MB
arr_medium -> sec: 0, ms: 5.537698,   heap used: 3.68 MB
arr_big ->    sec: 1, ms: 617.720973, heap used: 1149.33 MB

Recursion + no IIFE

If for some reason you don’t like IIFEs, you can extract the inner flat function out.

function flat(arr, target) {
    arr.forEach(function (el) {
        if (Array.isArray(el)) flat(el, target)
        else target.push(el)
    })
}

function flatten(arr) {
    const flattened = []
    flat(arr, flattened)
    return flattened
}

Main building blocks:

• Recursion
• Extracted flat function

⏱️ Performance testing:

arr_small ->  sec: 0, ms: 0.39932,    heap used: 2.71 MB
arr_medium -> sec: 0, ms: 8.302983,   heap used: 4.38 MB
arr_big ->    sec: 1, ms: 384.183185, heap used: 1149.1 MB

Stack

Every recursion has a loop equivalent, using stack data structure.

function flatten(arr) {
    const stack = [...arr]
    const flattened = []

    while (stack.length) {
        const next = stack.pop()

        if (Array.isArray(next)) {
            stack.push(...next)
        } else {
            flattened.unshift(next)
        }
    }

    return flattened
}

Main building blocks:

• while loop
• stack data structure

Stack is basically a data structure providing push() and pop() methods. It’s a Last In, First Out (LIFO) data structure. You add to and take things from only the top of the stack.

⏱️ Performance testing:

arr_small ->  sec: 0, ms: 0.345442,  heap used: 2.61 MB
arr_medium -> sec: 0, ms: 71.374404, heap used: 3.16 MB
arr_big ->    hasn't finished after 10 minutes

Recursion + generator

function* flatten(arr) {
    if (Array.isArray(arr)) for (const a of arr) yield* flatten(a)
    else yield arr
}

Main building blocks:

• recursion
• generator
• generator delegation (yield*)

Because generator functions return generator objects and because generators are lazy, you must collect the data manually.

const flattened = [...flatten(arr)];

or

const flattened = Array.from(flatten(arr));

⏱️ Performance testing:

arr_small ->  sec: 0,  ms: 4.160638,  heap used: 3.05 MB
arr_medium -> sec: 0,  ms: 30.807359, heap used: 4.85 MB
arr_big ->    sec: 33, ms: 33.095764, heap used: 858.01 MB

Summary

The performance results heavily depend on the input arrays. I’ve used arrays that are 10, 15 and 25 levels deep and only have two items per array, since I was more concerned in the depth than the breadth of the array.

For this input data the fastest implementations are:

• Recursion + no IIFE
• Recursion + IIFE

and the slowest implementations:

• Stack
• Recursion + generator

Resources

• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/flat
• https://humanwhocodes.com/snippets/2019/02/flatten-array-javascript-generator/