CODEWITHSUNDEEP
javascriptnode.jsperformance
user7636880
user7636880

Reputation:

Strange JavaScript / Node.js Performance Issue

At the moment I am struggeling with a very strange performance issue. The average it takes for the SlowHeap is 1448.623ms while the FastHeap only required 550.425ms. I've looked at it multiple times, but the only difference between the two is that the first is using an "undefined" element at the beginning of _arr and the second one doesn't. But, they both do the same operations and so on. That I have verified with the code underneath.

Is there someone who could shed a light on this problem?

let slowHeapOperationCount = 0
let fastHeapOperationCount = 0

let slowHeapExchanged = []
let fastHeapExchanged = []

function SlowHeap(cmp = (a, b) => a > b ? 1 : a < b ? -1 : 0) {
    this.cmp = cmp
    this._arr = [undefined]
    this.size = 0
}
function FastHeap(cmp = (a, b) => a > b ? 1 : a < b ? -1 : 0) {
    this.cmp = cmp
    this._arr = []
    this.size = 0
}

SlowHeap.prototype.bubbleUp = function (cmp, _arr, val) {
    let idxNr = this.size, parentIdxNr = idxNr >> 1
    while (idxNr > 0 && cmp(_arr[parentIdxNr], val) > 0) {
        slowHeapExchanged.push([_arr[parentIdxNr], val])

        _arr[idxNr] = _arr[parentIdxNr]
        _arr[parentIdxNr] = val

        idxNr = parentIdxNr
        parentIdxNr = idxNr >> 1

        slowHeapOperationCount++
    }
}
FastHeap.prototype.bubbleUp = function (cmp, _arr, val) {
    var idxNr = this.size,
        parentIdxNr = ((idxNr - 1) / 2) | 0;

    while (idxNr > 0 && cmp(_arr[parentIdxNr], val) > 0) {
        fastHeapExchanged.push([_arr[parentIdxNr], val])

        _arr[idxNr] = _arr[parentIdxNr];
        _arr[parentIdxNr] = val;

        idxNr = parentIdxNr;
        parentIdxNr = ((idxNr - 1) / 2) | 0;

        fastHeapOperationCount++
    }
}

SlowHeap.prototype.push = function (val) {
    ++this.size
    this._arr.push(val)
    this.bubbleUp(this.cmp, this._arr, val)
    return this.size
}
FastHeap.prototype.push = function (val) {
    this._arr.push(val);
    this.bubbleUp(this.cmp, this._arr, val);
    return ++this.size;
}

const itemCount = 4000000

const slowHeap = new SlowHeap()
const fastHeap = new FastHeap()

//
// Append the same Number Collection to each Heap:
const numberCollection = []

for (let idxNr = 0; idxNr < itemCount; idxNr++) numberCollection.push(Math.random())

//
// Benchmark for the Slow Heap:
console.time('SlowHeap')

for (let idxNr = 0; idxNr < itemCount; idxNr++) {
    slowHeap.push(numberCollection[idxNr])
}

console.timeEnd('SlowHeap')

//
// Benchmark for the Fast Heap:
console.time('FastHeap')

for (let idxNr = 0; idxNr < itemCount; idxNr++) {
    fastHeap.push(numberCollection[idxNr])
}

console.timeEnd('FastHeap')

//
// Verify the "_arr" from the Slow Heap against the Fast Heap:
for (let idxNr = 0; idxNr < itemCount; idxNr++) {
    if (slowHeap._arr[idxNr + 1] !== fastHeap._arr[idxNr]) console.log('Unequal value found!')
}

if (slowHeapExchanged.length !== fastHeapExchanged.length) console.log('Help! Comp. is not equal.')

for (let idxNr = 0, maxNr = slowHeapExchanged.length; idxNr < maxNr; idxNr++) {
    if (slowHeapExchanged[idxNr][0] !== fastHeapExchanged[idxNr][0] || slowHeapExchanged[idxNr][1] !== fastHeapExchanged[idxNr][1]) {
        console.log('Help!')
    }
}

console.log(slowHeapOperationCount)
console.log(fastHeapOperationCount)

Upvotes: 2

Views: 81

Answers (1)

robertklep
robertklep

Reputation: 203231

I don't have any knowledge on the specifics, but it looks like a V8 optimization that's being enabled/disabled: when you replace undefined with 0.0, SlowHeap isn't that slow anymore (in fact, it's faster than FastHeap for me).

My guess is that because you're filling the array with floats (Math.random()), as long as the array contains items that are all the same type, there's an optimization that can be performed.

Once you introduce a type mismatch (undefined isn't a float), V8 might have to switch to perhaps a more generic type of array, and forego on the optimization.

Upvotes: 2

Related Questions