DEV Community

Discussion on: Big-O Notation Cheatsheet

Collapse
 
qm3ster profile image
Mihail Malo • Edited

How is slice so much faster?

function buildSquareMatrix2(items) {
    const len = items.length
    let matrix = []

    for (let i = 0; i < len; i++) {
        const next = []

        for (let j = 0; j < len; j++) {
            next[j] = items[j]
        }

        matrix[i] = next
    }
    return matrix
}

function buildSquareMatrix3(items) {
    const len = items.length
    let matrix = []

    for (let i = 0; i < len; i++) {
        matrix[i] = items.slice()
    }
    return matrix
}
buildSquareMatrix        9818
buildSquareMatrix2       9162
buildSquareMatrix3       733
Collapse
 
kbariotis profile image
Kostas Bariotis • Edited

Most of JavaScript's functions on objects (Array objects included) are using some sort of a hashing algorithm to iterate over their properties [Citation needed]. It's not just a for loop as in your example.

Collapse
 
qm3ster profile image
Mihail Malo • Edited

And WOW, creating the array at the correct size really makes a huge difference:

function buildSquareMatrix2(items) {
    const len = items.length
    let matrix = new Array(len)

    for (let i = 0; i < len; i++) {
        const next = new Array(len)

        for (let j = 0; j < len; j++) {
            next[j] = items[j]
        }

        matrix[i] = next
    }
    return matrix
}
buildSquareMatrix        9504
buildSquareMatrix2       1528
buildSquareMatrix3       678

Less than 3x slowdown over .slice() while still allowing you to modify each value!

Collapse
 
qm3ster profile image
Mihail Malo

Yeah, in theory. But V8 does a lot of runtime optimization. A for loop incrementing by 1 over specifically a continuous array surely doesn't actually do hashmap lookups with the integer at every iteration. I'm sure that no kind of SIMD is taking place, but when it sees that there are no break/continue branches, surely it at least iterates over the values directly?