奇妙なJavaScript/Node.jsパフォーマンスの問題

Question

現在、私は非常に奇妙なパフォーマンスの問題で苦労しています。 SlowHeapの平均は1448.623ms、FastHeapは550.425msしか必要ありません。私はそれを何度も見てきましたが、2つの唯一の違いは、最初の要素が_arrの先頭に "未定義"要素を使用し、2番目の要素が未定義です。しかし、彼らはどちらも同じ操作を行います。私は下のコードで確認しました。

この問題を解明できる人はいますか？

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

私は具体的にどんな知識を持っていないが、それは有効/無効にされていますV8の最適化のようになります。あなたは0.0とundefinedを交換する際に、SlowHeapが、それはだ、実際には（もうその遅いではありません私にとってはFastHeapより速く）。

私は、浮動小数点数（Math.random()）で配列を埋めるので、配列に同じ型の項目が含まれている限り、実行できる最適化があります。

タイプの不一致（undefinedは浮動小数点ではありません）を導入すると、V8はおそらくより一般的なタイプの配列に切り替える必要があり、最適化を控える必要があります。