Skip to content
loading...

re: Big-O Notation Cheatsheet VIEW POST

FULL DISCUSSION
 

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
 

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.

 

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!

 

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?

code of conduct - report abuse