Merkwürdiges JavaScript/Node.js Performance-Problem

Question

Momentan kämpfe ich mit einem sehr seltsamen Leistungsproblem. Der Durchschnitt für den SlowHeap beträgt 1448.623 ms, während der FastHeap nur 550.425 ms benötigt. Ich habe es mehrmals betrachtet, aber der einzige Unterschied zwischen den beiden ist, dass der erste ein "undefined" Element am Anfang von _arr verwendet und der zweite nicht. Aber sie machen beide die gleichen Operationen und so weiter. Das habe ich mit dem Code darunter verifiziert.

Gibt es jemanden, der ein Licht auf dieses Problem werfen könnte?

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) 

Answer 1

ich auf die Besonderheiten keine Kenntnisse haben, aber es sieht aus wie ein V8-Optimierung, die aktiviert/deaktiviert ist wird: Wenn Sie undefined mit 0.0 ersetzen ist SlowHeap nicht so langsam mehr (in der Tat, es ist schneller als FastHeap für mich).

Meine Vermutung ist, dass, weil Sie das Array mit Schwimmern füllen (Math.random()), solange das Array Elemente enthält, die alle vom gleichen Typ sind, gibt es eine Optimierung, die ausgeführt werden kann.

Sobald Sie einen Typkonflikt eingeführt haben (undefined ist kein Float), muss V8 möglicherweise zu einem allgemeineren Arraytyp wechseln und auf die Optimierung verzichten.