Skip to content

Commit 482b19a

Browse files
sindresorhussindresorhus
committed
Improve performance
1 parent 5ec53f9 commit 482b19a

5 files changed

Lines changed: 231 additions & 46 deletions

File tree

‎base.js‎

Lines changed: 73 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -24,15 +24,12 @@ function encoderForArrayFormat(options) {
2424
}
2525

2626
if (value === null) {
27-
return [
28-
...result, [encode(key, options), '[', index, ']'].join(''),
29-
];
27+
result.push([encode(key, options), '[', index, ']'].join(''));
28+
return result;
3029
}
3130

32-
return [
33-
...result,
34-
[encode(key, options), '[', encode(index, options), ']=', encode(value, options)].join(''),
35-
];
31+
result.push([encode(key, options), '[', encode(index, options), ']=', encode(value, options)].join(''));
32+
return result;
3633
};
3734
}
3835

@@ -47,16 +44,12 @@ function encoderForArrayFormat(options) {
4744
}
4845

4946
if (value === null) {
50-
return [
51-
...result,
52-
[encode(key, options), '[]'].join(''),
53-
];
47+
result.push([encode(key, options), '[]'].join(''));
48+
return result;
5449
}
5550

56-
return [
57-
...result,
58-
[encode(key, options), '[]=', encode(value, options)].join(''),
59-
];
51+
result.push([encode(key, options), '[]=', encode(value, options)].join(''));
52+
return result;
6053
};
6154
}
6255

@@ -71,16 +64,12 @@ function encoderForArrayFormat(options) {
7164
}
7265

7366
if (value === null) {
74-
return [
75-
...result,
76-
[encode(key, options), ':list='].join(''),
77-
];
67+
result.push([encode(key, options), ':list='].join(''));
68+
return result;
7869
}
7970

80-
return [
81-
...result,
82-
[encode(key, options), ':list=', encode(value, options)].join(''),
83-
];
71+
result.push([encode(key, options), ':list=', encode(value, options)].join(''));
72+
return result;
8473
};
8574
}
8675

@@ -104,10 +93,12 @@ function encoderForArrayFormat(options) {
10493
value = value === null ? '' : value;
10594

10695
if (result.length === 0) {
107-
return [[encode(key, options), keyValueSeparator, encode(value, options)].join('')];
96+
result.push([encode(key, options), keyValueSeparator, encode(value, options)].join(''));
97+
return result;
10898
}
10999

110-
return [[result, encode(value, options)].join(options.arrayFormatSeparator)];
100+
result.push(encode(value, options));
101+
return result;
111102
};
112103
}
113104

@@ -122,16 +113,12 @@ function encoderForArrayFormat(options) {
122113
}
123114

124115
if (value === null) {
125-
return [
126-
...result,
127-
encode(key, options),
128-
];
116+
result.push(encode(key, options));
117+
return result;
129118
}
130119

131-
return [
132-
...result,
133-
[encode(key, options), '=', encode(value, options)].join(''),
134-
];
120+
result.push([encode(key, options), '=', encode(value, options)].join(''));
121+
return result;
135122
};
136123
}
137124
}
@@ -175,7 +162,12 @@ function parserForArrayFormat(options) {
175162
return;
176163
}
177164

178-
accumulator[key] = [...accumulator[key], value];
165+
if (!Array.isArray(accumulator[key])) {
166+
accumulator[key] = [accumulator[key], value];
167+
return;
168+
}
169+
170+
accumulator[key].push(value);
179171
};
180172
}
181173

@@ -194,7 +186,12 @@ function parserForArrayFormat(options) {
194186
return;
195187
}
196188

197-
accumulator[key] = [...accumulator[key], value];
189+
if (!Array.isArray(accumulator[key])) {
190+
accumulator[key] = [accumulator[key], value];
191+
return;
192+
}
193+
194+
accumulator[key].push(value);
198195
};
199196
}
200197

@@ -226,7 +223,13 @@ function parserForArrayFormat(options) {
226223
return;
227224
}
228225

229-
accumulator[key] = [...accumulator[key], ...arrayValue];
226+
if (!Array.isArray(accumulator[key])) {
227+
accumulator[key] = [accumulator[key]];
228+
}
229+
230+
for (const item of arrayValue) {
231+
accumulator[key].push(item);
232+
}
230233
};
231234
}
232235

@@ -237,7 +240,12 @@ function parserForArrayFormat(options) {
237240
return;
238241
}
239242

240-
accumulator[key] = [...[accumulator[key]].flat(), value];
243+
if (Array.isArray(accumulator[key])) {
244+
accumulator[key].push(value);
245+
return;
246+
}
247+
248+
accumulator[key] = [accumulator[key], value];
241249
};
242250
}
243251
}
@@ -298,6 +306,12 @@ function getHash(url) {
298306
return hash;
299307
}
300308

309+
function getUrlWithoutQuery(url) {
310+
// Avoid `split('?')` so query-heavy URLs don't allocate large arrays.
311+
const queryStart = url.indexOf('?');
312+
return queryStart === -1 ? url : url.slice(0, queryStart);
313+
}
314+
301315
function parseValue(value, options, type) {
302316
if (type === 'string' && typeof value === 'string') {
303317
return value;
@@ -381,11 +395,21 @@ export function parse(query, options) {
381395
return returnValue;
382396
}
383397

384-
for (const parameter of query.split('&')) {
385-
if (parameter === '') {
398+
// Avoid `split('&')` so separator-heavy inputs don't allocate large arrays of empty strings.
399+
let parameterStart = 0;
400+
401+
for (let index = 0; index <= query.length; index++) {
402+
if (index < query.length && query[index] !== '&') {
403+
continue;
404+
}
405+
406+
if (index === parameterStart) {
407+
parameterStart = index + 1;
386408
continue;
387409
}
388410

411+
const parameter = query.slice(parameterStart, index);
412+
parameterStart = index + 1;
389413
const parameter_ = options.decode ? parameter.replaceAll('+', ' ') : parameter;
390414

391415
let [key, value] = splitOnFirst(parameter_, '=');
@@ -498,9 +522,9 @@ export function stringify(object, options) {
498522
).filter(item => item !== undefined);
499523
}
500524

501-
return processedArray
502-
.reduce(formatter(key), [])
503-
.join('&');
525+
const result = processedArray.reduce(formatter(key), []);
526+
const arrayFormatSeparator = ['comma', 'separator', 'bracket-separator'].includes(options.arrayFormat) ? options.arrayFormatSeparator : '&';
527+
return result.join(arrayFormatSeparator);
504528
}
505529

506530
return encode(key, options) + '=' + encode(value, options);
@@ -520,7 +544,7 @@ export function parseUrl(url, options) {
520544
}
521545

522546
return {
523-
url: url_?.split('?')?.[0] ?? '',
547+
url: getUrlWithoutQuery(url_ ?? ''),
524548
query: parse(extract(url), options),
525549
...(options && options.parseFragmentIdentifier && hash ? {fragmentIdentifier: decode(hash, options)} : {}),
526550
};
@@ -534,7 +558,7 @@ export function stringifyUrl(object, options) {
534558
...options,
535559
};
536560

537-
const url = removeHash(object.url).split('?')[0] || '';
561+
const url = getUrlWithoutQuery(removeHash(object.url)) || '';
538562
const queryFromUrl = extract(object.url);
539563

540564
const query = {
@@ -572,7 +596,10 @@ export function pick(input, filter, options) {
572596
}
573597

574598
export function exclude(input, filter, options) {
575-
const exclusionFilter = Array.isArray(filter) ? key => !filter.includes(key) : (key, value) => !filter(key, value);
599+
if (Array.isArray(filter)) {
600+
const filterSet = new Set(filter);
601+
return pick(input, key => !filterSet.has(key), options);
602+
}
576603

577-
return pick(input, exclusionFilter, options);
604+
return pick(input, (key, value) => !filter(key, value), options);
578605
}

‎test/exclude.js‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,25 @@ test('handles empty filter array', t => {
2424
t.is(queryString.exclude('http://example.com/?a=1&b=2&c=3', []), 'http://example.com/?a=1&b=2&c=3');
2525
});
2626

27+
test('handles large exclusion arrays without quadratic slowdown', t => {
28+
const count = 20_000;
29+
const query = Array.from({length: count}, (_, index) => `a${index}=1`).join('&');
30+
const url = `https://example.com/?${query}`;
31+
const filter = Array.from({length: count}, (_, index) => `b${index}`);
32+
const filterSet = new Set(filter);
33+
34+
const predicateStartTime = performance.now();
35+
queryString.exclude(url, key => filterSet.has(key));
36+
const predicateElapsedTime = performance.now() - predicateStartTime;
37+
38+
const arrayStartTime = performance.now();
39+
const result = queryString.exclude(url, filter);
40+
const arrayElapsedTime = performance.now() - arrayStartTime;
41+
42+
t.true(result.startsWith('https://example.com/?a0=1&a1=1'));
43+
t.true(arrayElapsedTime < (predicateElapsedTime * 5) + 50, `Expected exclusion array filtering to stay near the Set predicate baseline. Array: ${arrayElapsedTime}ms. Predicate: ${predicateElapsedTime}ms.`);
44+
});
45+
2746
test('handles excluding non-existent parameters', t => {
2847
t.is(queryString.exclude('http://example.com/?a=1&b=2', ['c', 'd']), 'http://example.com/?a=1&b=2');
2948
});

‎test/parse-url.js‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,17 @@ test('handles strings with query string that contain =', t => {
1919
t.deepEqual(queryString.parseUrl('https://foo.bar?foo=bar=&foo=baz='), {url: 'https://foo.bar', query: {foo: ['bar=', 'baz=']}});
2020
});
2121

22+
test('handles query-heavy URLs without splitting the whole URL', t => {
23+
const count = 10_000_000;
24+
const url = `https://foo.bar?${'?'.repeat(count)}`;
25+
const startTime = performance.now();
26+
const parsed = queryString.parseUrl(url, {sort: false});
27+
const elapsedTime = performance.now() - startTime;
28+
29+
t.is(parsed.url, 'https://foo.bar');
30+
t.true(elapsedTime < 120, `Expected URL parsing to avoid splitting the whole URL. Took ${elapsedTime}ms.`);
31+
});
32+
2233
test('handles strings with fragment identifier', t => {
2334
t.deepEqual(queryString.parseUrl('https://foo.bar?top=foo#bar', {parseFragmentIdentifier: true}), {url: 'https://foo.bar', query: {top: 'foo'}, fragmentIdentifier: 'bar'});
2435
t.deepEqual(queryString.parseUrl('https://foo.bar?foo=bar&foo=baz#top', {parseFragmentIdentifier: true}), {url: 'https://foo.bar', query: {foo: ['bar', 'baz']}, fragmentIdentifier: 'top'});

‎test/parse.js‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -94,6 +94,85 @@ test('handle multiple of the same key', t => {
9494
t.deepEqual(queryString.parse('foo=bar&foo=baz'), {foo: ['bar', 'baz']});
9595
});
9696

97+
test('handles many duplicate keys without quadratic slowdown', t => {
98+
const count = 20_000;
99+
const duplicateQuery = Array.from({length: count}, () => 'a=1').join('&');
100+
const uniqueQuery = Array.from({length: count}, (_, index) => `a${index}=1`).join('&');
101+
102+
const uniqueStartTime = performance.now();
103+
queryString.parse(uniqueQuery);
104+
const uniqueElapsedTime = performance.now() - uniqueStartTime;
105+
106+
const duplicateStartTime = performance.now();
107+
const parsed = queryString.parse(duplicateQuery);
108+
const duplicateElapsedTime = performance.now() - duplicateStartTime;
109+
110+
t.is(parsed.a.length, count);
111+
t.true(parsed.a.every(value => value === '1'));
112+
t.true(duplicateElapsedTime < (uniqueElapsedTime * 20) + 100, `Expected duplicate-key parsing to stay near the unique-key baseline. Duplicate: ${duplicateElapsedTime}ms. Unique: ${uniqueElapsedTime}ms.`);
113+
});
114+
115+
test('handles many explicit array items without quadratic slowdown', t => {
116+
const count = 20_000;
117+
const cases = [
118+
{
119+
arrayFormat: 'bracket',
120+
duplicateQuery: Array.from({length: count}, () => 'a[]=1').join('&'),
121+
uniqueQuery: Array.from({length: count}, (_, index) => `a${index}[]=1`).join('&'),
122+
},
123+
{
124+
arrayFormat: 'colon-list-separator',
125+
duplicateQuery: Array.from({length: count}, () => 'a:list=1').join('&'),
126+
uniqueQuery: Array.from({length: count}, (_, index) => `a${index}:list=1`).join('&'),
127+
},
128+
{
129+
arrayFormat: 'bracket-separator',
130+
duplicateQuery: Array.from({length: count}, () => 'a[]=1').join('&'),
131+
uniqueQuery: Array.from({length: count}, (_, index) => `a${index}[]=1`).join('&'),
132+
},
133+
];
134+
135+
for (const {arrayFormat, duplicateQuery, uniqueQuery} of cases) {
136+
const uniqueStartTime = performance.now();
137+
queryString.parse(uniqueQuery, {arrayFormat});
138+
const uniqueElapsedTime = performance.now() - uniqueStartTime;
139+
140+
const duplicateStartTime = performance.now();
141+
const parsed = queryString.parse(duplicateQuery, {arrayFormat});
142+
const duplicateElapsedTime = performance.now() - duplicateStartTime;
143+
144+
t.is(parsed.a.length, count);
145+
t.true(parsed.a.every(value => value === '1'));
146+
t.true(duplicateElapsedTime < (uniqueElapsedTime * 10) + 100, `Expected ${arrayFormat} parsing to stay near the unique-key baseline. Duplicate: ${duplicateElapsedTime}ms. Unique: ${uniqueElapsedTime}ms.`);
147+
}
148+
});
149+
150+
test('handles large bracket-separator chunks without argument spread overflow', t => {
151+
const count = 200_000;
152+
const query = `a[]=0&a[]=${Array.from({length: count}, () => '1').join(',')}`;
153+
const parsed = queryString.parse(query, {arrayFormat: 'bracket-separator'});
154+
155+
t.is(parsed.a.length, count + 1);
156+
t.is(parsed.a[0], '0');
157+
t.is(parsed.a.at(-1), '1');
158+
});
159+
160+
test('handles scalar values before explicit array entries', t => {
161+
t.deepEqual(queryString.parse('a=one&a[]=two', {arrayFormat: 'bracket'}), {a: ['one', 'two']});
162+
t.deepEqual(queryString.parse('a=one&a:list=two', {arrayFormat: 'colon-list-separator'}), {a: ['one', 'two']});
163+
t.deepEqual(queryString.parse('a=one&a[]=two,three', {arrayFormat: 'bracket-separator'}), {a: ['one', 'two', 'three']});
164+
});
165+
166+
test('handles many empty parameters without allocating split results', t => {
167+
const query = '&'.repeat(5_000_000);
168+
const startTime = performance.now();
169+
const parsed = queryString.parse(query, {sort: false});
170+
const elapsedTime = performance.now() - startTime;
171+
172+
t.deepEqual(parsed, {});
173+
t.true(elapsedTime < 50, `Expected empty parameter parsing to avoid split allocation. Took ${elapsedTime}ms.`);
174+
});
175+
97176
test('handle multiple values and preserve appearence order', t => {
98177
t.deepEqual(queryString.parse('a=value&a='), {a: ['value', '']});
99178
t.deepEqual(queryString.parse('a=&a=value'), {a: ['', 'value']});

0 commit comments

Comments
 (0)