Raphael Herouart
8899b945f6
This CL replaces the TimSort implementation in V8's Torque builtins with PowerSort. The case for switching rests on algorithmic merits rather than raw speed, as macrobenchmarks are neutral. The key advantages are: - PowerSort's merge cost is provably near-optimal with respect to the entropy of run lengths, whereas TimSort can be ~50% above optimal on adversarial shapes. - The invariant is local and stateless, removing TimSort's "uncomfortably subtle" two-inequality stack invariant which caused bugs in other engines historically. - PowerSort weakly dominates: same behavior on trivially-sorted inputs, strictly better on a nontrivial set, and simpler to prove. This work follows the CPython precedent (PR #28108). The intended source of truth for this implementation is the CPython commit 5cb4c672d8. Bug: 500322223 Change-Id: Ic7ea2c427092e3b474f46cfc2b5f4e3204b84acd Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7742184 Commit-Queue: Raphael Herouart <rherouart@chromium.org> Auto-Submit: Raphael Herouart <rherouart@chromium.org> Reviewed-by: Jakob Linke <jgruber@chromium.org> Commit-Queue: Jakob Linke <jgruber@chromium.org> Cr-Commit-Position: refs/heads/main@{#106599}
57 lines
1.3 KiB
JavaScript
57 lines
1.3 KiB
JavaScript
// Copyright 2026 the V8 project authors. All rights reserved.
|
|
// Use of this source code is governed by a BSD-style license that can be
|
|
// found in the LICENSE file.
|
|
|
|
// Test that Array.prototype.sort is stable.
|
|
|
|
function TestStability() {
|
|
const size = 100;
|
|
let arr = new Array(size);
|
|
|
|
// Fill array with objects.
|
|
// We use a small range of keys to ensure many equal keys.
|
|
for (let i = 0; i < size; i++) {
|
|
arr[i] = {
|
|
key: i % 10,
|
|
orig_idx: i
|
|
};
|
|
}
|
|
|
|
// Sort by key.
|
|
arr.sort((a, b) => a.key - b.key);
|
|
|
|
// Verify stability.
|
|
for (let i = 1; i < size; i++) {
|
|
if (arr[i].key === arr[i-1].key) {
|
|
assertTrue(arr[i].orig_idx > arr[i-1].orig_idx,
|
|
`Stability violated at index ${i}`);
|
|
}
|
|
}
|
|
}
|
|
|
|
TestStability();
|
|
|
|
// Test with strings as well.
|
|
function TestStringStability() {
|
|
const size = 100;
|
|
let arr = new Array(size);
|
|
|
|
for (let i = 0; i < size; i++) {
|
|
arr[i] = {
|
|
key: String.fromCharCode(65 + (i % 5)), // A, B, C, D, E
|
|
orig_idx: i
|
|
};
|
|
}
|
|
|
|
arr.sort((a, b) => a.key.localeCompare(b.key));
|
|
|
|
for (let i = 1; i < size; i++) {
|
|
if (arr[i].key === arr[i-1].key) {
|
|
assertTrue(arr[i].orig_idx > arr[i-1].orig_idx,
|
|
`String stability violated at index ${i}`);
|
|
}
|
|
}
|
|
}
|
|
|
|
TestStringStability();
|