Commit dd7235cb6a5 for nodejs
commit dd7235cb6a55e9987551719ee57de9c3ff59d115
Author: Roberto Bianchi <rbianchidev@gmail.com>
Date: Wed Oct 14 10:51:58 2026 +0200
url: reduce search params sort buffering
URLSearchParams.sort() copies both merge runs into temporary arrays.
Buffer only the left run and read the right run from the output array,
removing one scratch-array allocation and the right-run copying.
While left-side elements remain, the output cursor stays behind unread
right-side elements. Once the left run is exhausted, the right remainder
is already in place. Taking the left key on equality preserves
stability. The insertion-sort path below 50 pairs is unchanged.
Signed-off-by: Roberto Bianchi <roberto.bianchi@spendesk.com>
PR-URL: https://github.com/nodejs/node/pull/66665
Reviewed-By: Xuguang Mei <meixuguang@gmail.com>
Reviewed-By: Matteo Collina <matteo.collina@gmail.com>
Reviewed-By: Ilyas Shabi <ilyasshabi94@gmail.com>
Reviewed-By: Gürgün Dayıoğlu <hey@gurgun.day>
diff --git a/benchmark/url/url-searchparams-sort-scaling.js b/benchmark/url/url-searchparams-sort-scaling.js
new file mode 100644
index 00000000000..ae1873faf60
--- /dev/null
+++ b/benchmark/url/url-searchparams-sort-scaling.js
@@ -0,0 +1,43 @@
+'use strict';
+
+const common = require('../common.js');
+const assert = require('node:assert');
+
+const bench = common.createBenchmark(main, {
+ n: [1e4],
+ size: [49, 50, 65, 256, 1024],
+ order: ['sorted', 'reversed', 'shuffled', 'duplicates'],
+});
+
+function main({ n, size, order }) {
+ const entries = Array.from({ length: size }, (_, index) => [
+ `key-${String(order === 'duplicates' ? index % 7 : index).padStart(8, '0')}`,
+ String(index),
+ ]);
+ if (order === 'reversed') {
+ entries.reverse();
+ } else if (order === 'shuffled') {
+ let seed = 12345;
+ for (let index = entries.length - 1; index > 0; index--) {
+ seed = (Math.imul(seed, 1664525) + 1013904223) >>> 0;
+ const other = seed % (index + 1);
+ [entries[index], entries[other]] = [entries[other], entries[index]];
+ }
+ }
+ const base = new URLSearchParams(entries);
+ const expected = entries.slice().sort(([first], [second]) =>
+ (first < second ? -1 : first > second ? 1 : 0));
+
+ for (let index = 0; index < 1000; index++) {
+ new URLSearchParams(base).sort();
+ }
+ let result;
+ bench.start();
+ for (let index = 0; index < n; index++) {
+ result = new URLSearchParams(base);
+ result.sort();
+ }
+ bench.end(n);
+ assert.deepStrictEqual([...result], expected);
+ assert.deepStrictEqual([...base], entries);
+}
diff --git a/lib/internal/url.js b/lib/internal/url.js
index 471df4db439..c97295d4d69 100644
--- a/lib/internal/url.js
+++ b/lib/internal/url.js
@@ -738,7 +738,6 @@ class URLSearchParams {
} else {
// Bottom-up iterative stable merge sort
const lBuffer = new Array(len);
- const rBuffer = new Array(len);
for (let step = 2; step < len; step *= 2) {
for (let start = 0; start < len - 2; start += 2 * step) {
const mid = start + step;
@@ -746,7 +745,7 @@ class URLSearchParams {
end = end < len ? end : len;
if (mid > end)
continue;
- merge(a, start, mid, end, lBuffer, rBuffer);
+ merge(a, start, mid, end, lBuffer);
}
}
}
@@ -1428,32 +1427,25 @@ function serializeParams(array) {
}
// for merge sort
-function merge(out, start, mid, end, lBuffer, rBuffer) {
+function merge(out, start, mid, end, lBuffer) {
const sizeLeft = mid - start;
- const sizeRight = end - mid;
- let l, r, o;
-
- for (l = 0; l < sizeLeft; l++)
- lBuffer[l] = out[start + l];
- for (r = 0; r < sizeRight; r++)
- rBuffer[r] = out[mid + r];
-
- l = 0;
- r = 0;
- o = start;
- while (l < sizeLeft && r < sizeRight) {
- if (lBuffer[l] <= rBuffer[r]) {
- out[o++] = lBuffer[l++];
- out[o++] = lBuffer[l++];
+ for (let index = 0; index < sizeLeft; index++)
+ lBuffer[index] = out[start + index];
+
+ let left = 0;
+ let right = mid;
+ let output = start;
+ while (left < sizeLeft && right < end) {
+ if (lBuffer[left] <= out[right]) {
+ out[output++] = lBuffer[left++];
+ out[output++] = lBuffer[left++];
} else {
- out[o++] = rBuffer[r++];
- out[o++] = rBuffer[r++];
+ out[output++] = out[right++];
+ out[output++] = out[right++];
}
}
- while (l < sizeLeft)
- out[o++] = lBuffer[l++];
- while (r < sizeRight)
- out[o++] = rBuffer[r++];
+ while (left < sizeLeft)
+ out[output++] = lBuffer[left++];
}
function domainToASCII(domain) {
diff --git a/test/parallel/test-whatwg-url-searchparams-sort-merge.js b/test/parallel/test-whatwg-url-searchparams-sort-merge.js
new file mode 100644
index 00000000000..4f0a7690486
--- /dev/null
+++ b/test/parallel/test-whatwg-url-searchparams-sort-merge.js
@@ -0,0 +1,54 @@
+'use strict';
+
+require('../common');
+const assert = require('node:assert');
+
+for (const size of [0, 1, 2, 49, 50, 51, 63, 64, 65, 127, 128, 129,
+ 255, 256, 257, 1023, 1024, 1025]) {
+ const ascending = Array.from({ length: size }, (_, index) => [
+ String(index).padStart(8, '0'), String(index),
+ ]);
+ const descending = ascending.slice().reverse();
+ const duplicates = ascending.map(([, value], index) => [
+ String(index % 7), value,
+ ]);
+ const shuffled = ascending.slice();
+ let seed = 12345;
+ for (let index = size - 1; index > 0; index--) {
+ seed = (Math.imul(seed, 1664525) + 1013904223) >>> 0;
+ const other = seed % (index + 1);
+ [shuffled[index], shuffled[other]] = [shuffled[other], shuffled[index]];
+ }
+
+ for (const entries of [ascending, descending, duplicates, shuffled]) {
+ const expected = entries.slice().sort(([first], [second]) =>
+ (first < second ? -1 : first > second ? 1 : 0));
+ const params = new URLSearchParams(entries);
+ const iterator = params.entries();
+ params.toString();
+ assert.strictEqual(params.sort(), undefined);
+ assert.deepStrictEqual([...params], expected);
+ assert.deepStrictEqual([...iterator], expected);
+ assert.strictEqual(params.size, size);
+ assert.strictEqual(params.toString(), new URLSearchParams(expected).toString());
+ params.sort();
+ assert.deepStrictEqual([...params], expected);
+ }
+}
+
+{
+ const entries = Array.from({ length: 65 }, (_, index) => [
+ ['\u00e9', 'e\u0301', '\ud83d\ude00', '\uffff', ''][index % 5],
+ `value ${index}`,
+ ]);
+ const expected = entries.slice().sort(([first], [second]) =>
+ (first < second ? -1 : first > second ? 1 : 0));
+ const url = new URL('https://example.org/');
+ for (const [name, value] of entries) url.searchParams.append(name, value);
+ assert.strictEqual(url.search, `?${new URLSearchParams(entries)}`);
+ const params = url.searchParams;
+ params.sort();
+ assert.strictEqual(url.searchParams, params);
+ assert.deepStrictEqual([...params], expected);
+ assert.strictEqual(url.search, `?${new URLSearchParams(expected)}`);
+}