Title: `new URLSearchParams(string)` is quadratic when the pairs have no `=` · Issue #67652 · nodejs/node · GitHub
Open Graph Title: `new URLSearchParams(string)` is quadratic when the pairs have no `=` · Issue #67652 · nodejs/node
X Title: `new URLSearchParams(string)` is quadratic when the pairs have no `=` · Issue #67652 · nodejs/node
Description: Version v26.13.1. The same line is in lib/internal/url.js on main, v26.x and v24.x. It is not in v22.x or v20.x. Platform Darwin 25.6.0 arm64 (macOS, Apple silicon) Subsystem url What steps will reproduce the bug? node -e 'const t = perf...
Open Graph Description: Version v26.13.1. The same line is in lib/internal/url.js on main, v26.x and v24.x. It is not in v22.x or v20.x. Platform Darwin 25.6.0 arm64 (macOS, Apple silicon) Subsystem url What steps will re...
X Description: Version v26.13.1. The same line is in lib/internal/url.js on main, v26.x and v24.x. It is not in v22.x or v20.x. Platform Darwin 25.6.0 arm64 (macOS, Apple silicon) Subsystem url What steps will re...
Opengraph URL: https://github.com/nodejs/node/issues/67652
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"`new URLSearchParams(string)` is quadratic when the pairs have no `=`","articleBody":"### Version\n\nv26.13.1. The same line is in `lib/internal/url.js` on `main`, `v26.x` and `v24.x`. It is not in `v22.x` or `v20.x`.\n\n### Platform\n\n```text\nDarwin 25.6.0 arm64 (macOS, Apple silicon)\n```\n\n### Subsystem\n\nurl\n\n### What steps will reproduce the bug?\n\n```sh\nnode -e 'const t = performance.now(); new URLSearchParams(\"a&\".repeat(262144)); console.log(performance.now() - t)'\n```\n\nThat is a 512 KB string. It takes about 1.6 s. The same number of pairs written `a=b&` takes 7.5 ms.\n\nA fuller script, median of 5 runs per cell, times in ms:\n\n```js\nimport querystring from \"node:querystring\";\n\nconst median = (run) => {\n const times = [];\n for (let round = 0; round \u003c 5; round += 1) {\n const started = performance.now();\n run();\n times.push(performance.now() - started);\n }\n return times.sort((a, b) => a - b)[2].toFixed(1);\n};\n\nconsole.log(process.version, process.arch, process.platform);\nconsole.log(\"pairs\\t'a&'\\t'a=&'\\t'a=b&'\\t'&'\\tqs.parse('a&')\");\nfor (const pairs of [16_384, 32_768, 65_536, 131_072, 262_144]) {\n console.log(\n [\n pairs,\n median(() => new URLSearchParams(\"a&\".repeat(pairs))),\n median(() => new URLSearchParams(\"a=&\".repeat(pairs))),\n median(() => new URLSearchParams(\"a=b&\".repeat(pairs))),\n median(() => new URLSearchParams(\"&\".repeat(pairs))),\n median(() => querystring.parse(\"a&\".repeat(pairs), \"&\", \"=\", { maxKeys: 0 })),\n ].join(\"\\t\")\n );\n}\n```\n\nOutput on v26.13.1, arm64, darwin:\n\n| pairs | `a&` | `a=&` | `a=b&` | `&` | `querystring.parse` of `a&` |\n| ---: | ---: | ---: | ---: | ---: | ---: |\n| 16,384 | 6.6 | 0.6 | 0.5 | 0.2 | 1.2 |\n| 32,768 | 24.7 | 1.8 | 1.1 | 0.5 | 2.2 |\n| 65,536 | 98.0 | 2.1 | 1.9 | 0.9 | 1.7 |\n| 131,072 | 428.8 | 3.7 | 3.6 | 1.7 | 3.1 |\n| 262,144 | 1631.3 | 7.3 | 7.5 | 3.4 | 6.1 |\n\nOnly the `a&` column grows fourfold when the input doubles.\n\nThe same cost is reachable from a request body, because `formData()` parses an urlencoded body with `URLSearchParams`:\n\n```js\nconst body = \"a&\".repeat(262144);\nconst started = performance.now();\nawait new Request(\"http://localhost/\", {\n method: \"POST\",\n headers: { \"content-type\": \"application/x-www-form-urlencoded\" },\n body,\n}).formData();\nconsole.log(performance.now() - started); // 1552 ms; 21 ms for \"a=b&\".repeat(262144)\n```\n\n### How often does it reproduce? Is there a required condition?\n\nEvery time. The condition is a long run of pairs with no `=` after them in the string. One `=` at the very end does not help: `\"a&\".repeat(262144) + \"a=b\"` takes the same time.\n\n### What is the expected behavior? Why is that the expected behavior?\n\nTime linear in the length of the string, as for `a=&`, `a=b&` and `querystring.parse`. v22 and v20 do not have this loop.\n\n### What do you see instead?\n\nQuadratic time. The parse is synchronous, so the event loop is blocked for all of it. A server that calls `request.formData()` on an urlencoded body of a few MB stops answering every other request for minutes. Extrapolating the table, a 21 MB body is about 10.5 million pairs and about 45 minutes. A 21 MB body of `a&` sent to an HTTP server that calls `request.formData()` held the CPU at 99% for over 4 minutes with no answer, and the run was stopped there.\n\n### Additional information\n\nThe cause is in `parseParams` in `lib/internal/url.js`, added by #65363 (\"url: speed up URLSearchParams\", commit 4b3bba58dd):\n\n```js\nwhile (i \u003c len) {\n let amp = qs.indexOf('&', i);\n if (amp === -1) {\n amp = len;\n }\n if (amp !== i) {\n const eq = qs.indexOf('=', i); // scans to the end of the string when no '=' follows\n if (eq === -1 || eq > amp) {\n out.push(encoded ? decodeFormComponent(qs, i, amp) : qs.slice(i, amp), '');\n } else {\n ...\n```\n\nFor each pair, `qs.indexOf('=', i)` searches from the pair's start to the next `=` anywhere in the string. When there is none, or it is far away, every pair scans the rest of the string.\n\nKeeping the last `=` position across pairs makes it linear, since a position past the current `&` is still the right answer for the next pair:\n\n```js\nlet eq = -2;\nwhile (i \u003c len) {\n let amp = qs.indexOf('&', i);\n if (amp === -1) {\n amp = len;\n }\n if (amp !== i) {\n if (eq !== -1 && eq \u003c i) {\n eq = qs.indexOf('=', i);\n }\n if (eq === -1 || eq > amp) {\n ...\n```\n\nI copied the undecoded branch of the loop into a script and timed both versions, median of 5 runs, in ms. The two return the same array for `a&` and `a=b&` repeated 1,000 times, `a&b=c&&d=&=e&f`, 50 pairs of `a&` followed by `x=y`, and the empty string.\n\n| pairs of `a&` | current loop | with the cached `=` |\n| ---: | ---: | ---: |\n| 65,536 | 97.3 | 1.2 |\n| 131,072 | 385.5 | 2.7 |\n| 262,144 | 1554.4 | 5.0 |\n\nI have not run Node's own test suite or benchmarks against that change.\n","author":{"url":"https://github.com/aayushbtw","@type":"Person","name":"aayushbtw"},"datePublished":"2026-11-20T13:07:43Z","url":"https://github.com/nodejs/node/issues/67652"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:5b318e9a-b26c-78ac-65b8-a4e37ae90b5a |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | A64E:AFBD9:BC443F:F92744:6B01C481 |
| html-safe-nonce | 0f98645a4a3c27c7721d5c32a1ea3709562a5f34c178b668f1c8db85e43af965 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJBNjRFOkFGQkQ5OkJDNDQzRjpGOTI3NDQ6NkIwMUM0ODEiLCJ2aXNpdG9yX2lkIjoiNTI3OTU3MDQ2ODU5MDk2MTc5MyIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9 |
| visitor-hmac | 00c9942844ff3e868878e773279d42e3e7a7168f31356f0aa9e1364510fba548 |
| hovercard-subject-tag | issue:6512030336 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/nodejs/node/67652/issue_layout |
| twitter:image | https://opengraph.githubassets.com/1684d0b9c858a561f4faa22af10df8d4487fa988ceafe5294ce1479ac0f8e0a3/nodejs/node/issues/67652 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/1684d0b9c858a561f4faa22af10df8d4487fa988ceafe5294ce1479ac0f8e0a3/nodejs/node/issues/67652 |
| og:image:alt | Version v26.13.1. The same line is in lib/internal/url.js on main, v26.x and v24.x. It is not in v22.x or v20.x. Platform Darwin 25.6.0 arm64 (macOS, Apple silicon) Subsystem url What steps will re... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | aayushbtw |
| hostname | github.com |
| expected-hostname | github.com |
| None | cc5dfdd32f62ebd3223cab3af3aa2b268d3605218237326a48a99d1efd89495c |
| turbo-cache-control | no-preview |
| go-import | github.com/nodejs/node git https://github.com/nodejs/node.git |
| octolytics-dimension-user_id | 9950313 |
| octolytics-dimension-user_login | nodejs |
| octolytics-dimension-repository_id | 27193779 |
| octolytics-dimension-repository_nwo | nodejs/node |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 27193779 |
| octolytics-dimension-repository_network_root_nwo | nodejs/node |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 8c77c9e8439031ad54c75a250694842892f693e1 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width