V8 Sorting

References: https://v8.js.cn/blog/array-sort/

这篇文章聊了V8对于排序的解释。因为排序算法已经相对稳定，但是对于复杂对象的排序，尤其是JavaScript这种动态类型语言来说，内存的访问成为性能最大的瓶颈。

这是一种最简单的情况：


const array = [4, 2, 5, 3, 1];
function compare(a, b) {
  // Arbitrary code goes here, e.g. `array.push(1);`.
  return a - b;
}
// A “typical” sort call.
array.sort(compare);

对于复杂的一些的情况：


const array = [0, 1, 2];
Object.defineProperty(array, '0', {
  get() { console.log('get 0'); return 0; },
  set(v) { console.log('set 0'); }
});
Object.defineProperty(array, '1', {
  get() { console.log('get 1'); return 1; },
  set(v) { console.log('set 1'); }
});
array.sort();

可以看到，不同引擎的实现中，这种内存访问是随机的，且不是一致的。V8对于数组的排序，用了两次的预处理。首先，它会从原型链复制原有的对象：

然后，数组的“空洞”被检测出来并被清除：

后面就开始讨论一种被称为Torque的算法。这种算法用于实现排序功能：

Load<FastDoubleElements>(
    context: Context, sortState: FixedArray, elements: HeapObject,
    index: Smi): Object {
  try {
    const elems: FixedDoubleArray = UnsafeCast<FixedDoubleArray>(elements);
    const value: float64 =
        LoadDoubleWithHoleCheck(elems, index) otherwise Bailout;
    return AllocateHeapNumberWithValue(value);
  }
  label Bailout {
    // The pre-processing step removed all holes by compacting all elements
    // at the start of the array. Finding a hole means the cmp function or
    // ToString changes the array.
    return Failure(sortState);
  }
}

# V8 Sorting

V8 Sorting