Description
slugify() function keeps the cache of previously created slugs so it can append -1, -2 and soo on to duplicates. To check if any slug has been displayed, it builds an array of every cached key and scans it linearly once per heading:
|
let count = cache[slug]; |
|
|
|
count = Object.keys(cache).includes(slug) ? count + 1 : 0; |
|
cache[slug] = count; |
let count = cache[slug];
count = Object.keys(cache).includes(slug) ? count + 1 : 0;
cache[slug] = count;
Object.keys(cache) assigns a new array of every slug displayed so far and Array.includes() traverse it. For a page with n headings that is n(n+1)/2 string comparisons plus n array allocations totalling n^2/2 strings. Value being searched for is already read on the line above (cache[slug]), so the scan is not needed to obtain it only to distinguish displayed from the ones not displayed.
This runs once per heading during compile and again for every heading of every page while the search plugin builds its index.
Expected behavior
slug generation scales linearly with the number of headings on a page.
Actual behavior
It scales quadratically and because docsify renders markdown in the browser at page load so the cost lands on the main thread on every visit.
I have measured in Chromium with real docsify build, timing from the beforeEach hook to doneEach (markdown compile + DOM render, content supplied by a virtual route so no network latency is involved).
| headings on the page |
render time |
| 250 |
57 ms |
| 500 |
104 ms |
| 1000 |
236 ms |
| 2000 |
740 ms |
| 4000 |
2498 ms |
Isolating slugify() itself with the repro below shows where that time goes
| headings |
time to slugify one page |
vs. n=250 |
| 250 |
2.96 ms |
0.4x |
| 500 |
25.96 ms |
3.7x |
| 1000 |
100.31 ms |
14.3x |
| 2000 |
404.87 ms |
57.7x |
| 4000 |
2401.56 ms |
342.4x |
16x the headings costs 342x the time; linear would be ~16x and quadratic ~256x.
At 4000 headings, slugify() alone accounts for roughly 2.4 s of the 2.5 s total render
Use Case:
Large single-page API references.
Steps to reproduce
I have created a sandbox here Sandbox
The sandbox loads docsify@5.0.0 from jsDelivr and generates the page content in memory through a virtual route, so nothing but docsify's own render work is being timed no markdown file is fetched.
Steps:
- Open the sandbox.
- Click Run all sizes.
- Read the table: render time against heading count, alongside what linear growth would look like.
Results:
| headings |
render (ms) |
vs. 250 |
linear would be |
| 250 |
56.1 |
1.0x |
1x |
| 500 |
134.8 |
2.4x |
2x |
| 1000 |
337.6 |
6.0x |
4x |
| 2000 |
927.3 |
16.5x |
8x |
| 4000 |
3049.7 |
54.4x |
16x |
**
16x the headings took 342.4x the time (linear would be ~16x, quadratic ~256x).
**
Environment
- Your OS: Windows 11 Pro (10.0.26200)
- Node.js version: v22.13.1
- npm/yarn version: npm 11.15.0
- Browser version: Chrome on Windows
- Docsify version: 5.0.0 reproduces on the published build (`cdn.jsdelivr.net/npm/docsify@5.0.0/dist/docsify.js`) as well as `develop` @ 030652c. Not present in v4.
- Docsify plugins (if the bug happens when plugins enabled, please try to isolate the issue): none, this reproduces in core and that too with no plugins loaded
Additional Information
Description
slugify()function keeps the cache of previously created slugs so it can append-1,-2and soo on to duplicates. To check if any slug has been displayed, it builds an array of every cached key and scans it linearly once per heading:Object.keys(cache)assigns a new array of every slug displayed so far andArray.includes()traverse it. For a page withnheadings that isn(n+1)/2string comparisons plusnarray allocations totallingn^2/2strings. Value being searched for is already read on the line above (cache[slug]), so the scan is not needed to obtain it only to distinguish displayed from the ones not displayed.This runs once per heading during compile and again for every heading of every page while the search plugin builds its index.
Expected behavior
slug generation scales linearly with the number of headings on a page.
Actual behavior
It scales quadratically and because docsify renders markdown in the browser at page load so the cost lands on the main thread on every visit.
I have measured in Chromium with real docsify build, timing from the
beforeEachhook todoneEach(markdown compile + DOM render, content supplied by a virtual route so no network latency is involved).Isolating
slugify()itself with the repro below shows where that time goes16x the headings costs 342x the time; linear would be ~16x and quadratic ~256x.
At 4000 headings,
slugify()alone accounts for roughly 2.4 s of the 2.5 s total renderUse Case:
Large single-page API references.
Steps to reproduce
I have created a sandbox here Sandbox
The sandbox loads
docsify@5.0.0from jsDelivr and generates the page content in memory through a virtual route, so nothing but docsify's own render work is being timed no markdown file is fetched.Steps:
Results:
**
**
Environment
Additional Information