alex/ephyra
Watch
1
0
Fork
You've already forked ephyra
 0
Code Issues 2 Pull requests Projects Releases Packages 1 Wiki Activity Actions

A library scan is quadratic in the size of one library: 42 s to conclude 20,000 films have not moved #92

New issue
Closed
opened 2026-08-13 22:40:55 +02:00 by Claude · 1 comment
Claude commented 2026-08-13 22:40:55 +02:00
Collaborator
Copy link

A library scan does not cost linear time in the number of films. Doubling the library multiplies a pass over an unchanged tree by 3.8 — an exponent of 1.9, near enough quadratic. Measured for the first time on 2026-08-13; nothing has been done about it, and it was left where it was found rather than fixed in a hurry.

Correctness stopped being the only metric when M3 exited, and until now the only fixture was six films. This is the first number over a library that is a library.

The measurement

A generated tree of films, one directory and one file each, every file a hard link to the same 98 KB mp4 — so the whole tree costs 96 KB of disk while each path is still stat-ed, resolved and probed on its own. Release build, sixteen cores, thirteen files read at once, one library, one POST /Library/Refresh, timed from the request to the scanned log line.

films first pass pass over the unchanged tree peak RSS
5,000 17.9 s 2.9 s 105 MB
10,000 41.6 s 11.2 s 158 MB
20,000 105.4 s 42.4 s 249 MB

Doubling multiplies the first pass by 2.3 then 2.5, and the unchanged pass by 3.8 both times.

Forty-two seconds to conclude that a library has not moved. At 40,000 films that is not eighty — extrapolating the measured exponent it is around 2.8 minutes, and around 11 at 80,000. This is the number that matters for a running server, because it is what every scheduled pass costs when nothing has changed.

The first pass is roughly half prober: 20,000 ffprobe runs at ~34 ms warm, thirteen at a time, is about 53 s of the 105. The unchanged pass runs no prober at all, so it is the other half measured on its own — and it is the half that is quadratic.

What is already ruled out

Please do not re-derive these; they are measured, and they are why this is narrow.

  • It is quadratic within one library, not across the pass. The same 20,000 films declared as two libraries of 10,000 cost 22.2 s over the unchanged tree, against 42.4 s as one — twice a single 10,000-film library to the tenth of a second. So the cost is in the per-library work, and anything shared by the whole pass is innocent.
  • Not the directory walk: 50 ms warm over all 40,000 entries.
  • Not reading the database: every row, ancestor chain and stream read back out is under 0.2 s.
  • Not the writes: they are the same count in both arrangements.

That leaves the step that turns one library's walk into rows and decides what moved — crates/jellyfin-app/src/scan/ — as the only place the time can be. Look for a per-entry lookup against a Vec (or any repeated linear scan of the filed set) rather than a map: an O(n) probe inside an O(n) loop over one library's entries is exactly the shape that splits in half when the library does.

Reproducing

The tree is not in the repository and must not go in — 20,000 directories is a load, not a fixture. Rebuild it deterministically:

import os, random
random.seed(11)
A = "Blue Red Green Silver Golden Hidden Broken Distant Quiet Burning Frozen Crimson Hollow Rising Falling Endless Silent Bitter Sacred Wild".split()
B = "Field Signal Harbour Beacon Tide Vault Ember Cipher Orbit Anchor Lantern Circuit Meridian Fathom Relay Prism Ledger Compass Grove Vector".split()
C = "Rain Dust Iron Glass Salt Ash Stone Wire Frost Bloom Echo Drift Fable Mire Shard Vein Quill Reef Spire Thread".split()
root, seed = "/home/alex/.cache/bigscan/movies", "/home/alex/.cache/bigscan/seed.mp4"
seen, n = set(), 0
while n < 20000:
    name, year = f"{random.choice(A)} {random.choice(B)} {random.choice(C)}", random.randint(1950, 2025)
    if (name, year) in seen: continue
    seen.add((name, year)); d = f"{name} ({year})"
    os.makedirs(os.path.join(root, d), exist_ok=True)
    try: os.link(seed, os.path.join(root, d, d + ".mp4"))
    except FileExistsError: pass
    n += 1

seed.mp4 is any small real video — the fixture's reference/var/media/movies/Blue Field (2020)/Blue Field (2020).mp4 does. As of writing the tree is still at ~/.cache/bigscan/movies, and ~/.cache/bigscan/run/ holds the previous scripts and raw numbers.

Point a scratch config at it — a copy of config.toml with its own [paths] and one [[libraries]] — and drive it with POST /Library/Refresh. Do not add it to the repository's config.toml and do not scan it into the reference.

Use --release; the numbers above are release and a debug build is not the same shape.

Done when

There is a number, and it is a better one. Concretely:

  • The pass over an unchanged tree is close to linear in the number of films, so 20,000 costs about twice 10,000 rather than four times.
  • docs/benchmarks.md carries the new table beside the old one — the old numbers stay, so the change is legible.
  • Whatever the fix is, it has a test that pins the shape rather than the seconds: seconds are the machine's, but "one library of 2n costs about twice one library of n" can be asserted on counts (queries issued, comparisons made) in a unit test.
  • JELLYFIN_RS_REQUIRE_FIXTURES=1 cargo nextest run --workspace green (2092 at the time of writing).

If it turns out the shape is inherent rather than accidental, say so with the evidence and write that down instead — an honest "this is why" is a better outcome than a change that moves the constant and leaves the exponent.

Before you start

  • CLAUDE.md is the contract. cargo nextest, not cargo test. Comments describe the current state, never the history, and carry no milestone terminology.
  • Read upstream at upstream/ in this repo — the pinned checkout. Not ../jellyfin, which is on a divergent branch. Upstream's own scan cost over the same tree has never been taken; if you take it, that is a useful number in its own right and belongs in docs/benchmarks.md.
  • Never git add -A, and never symlink reference/var, reference/snapshots, reference/media or reference/published into a worktree — they are gitignored, and committing such a link deletes the real fixture. That has happened.
  • Do not write to, re-provision or re-snapshot the reference on :8096.
A library scan does not cost linear time in the number of films. Doubling the library multiplies a pass over an **unchanged** tree by 3.8 — an exponent of 1.9, near enough quadratic. Measured for the first time on 2026-08-13; nothing has been done about it, and it was left where it was found rather than fixed in a hurry. Correctness stopped being the only metric when M3 exited, and until now the only fixture was six films. This is the first number over a library that is a library. ## The measurement A generated tree of films, one directory and one file each, every file a hard link to the same 98 KB mp4 — so the whole tree costs 96 KB of disk while each path is still stat-ed, resolved and probed on its own. Release build, sixteen cores, thirteen files read at once, one library, one `POST /Library/Refresh`, timed from the request to the `scanned` log line. | films | first pass | pass over the unchanged tree | peak RSS | |---|---|---|---| | 5,000 | 17.9 s | 2.9 s | 105 MB | | 10,000 | 41.6 s | 11.2 s | 158 MB | | 20,000 | 105.4 s | 42.4 s | 249 MB | Doubling multiplies the first pass by 2.3 then 2.5, and the unchanged pass by 3.8 both times. **Forty-two seconds to conclude that a library has not moved.** At 40,000 films that is not eighty — extrapolating the measured exponent it is around 2.8 minutes, and around 11 at 80,000. This is the number that matters for a running server, because it is what every scheduled pass costs when nothing has changed. The first pass is roughly half prober: 20,000 `ffprobe` runs at ~34 ms warm, thirteen at a time, is about 53 s of the 105. The unchanged pass runs **no** prober at all, so it is the other half measured on its own — and it is the half that is quadratic. ## What is already ruled out Please do not re-derive these; they are measured, and they are why this is narrow. - **It is quadratic within one library, not across the pass.** The same 20,000 films declared as *two* libraries of 10,000 cost **22.2 s** over the unchanged tree, against **42.4 s** as one — twice a single 10,000-film library to the tenth of a second. So the cost is in the per-library work, and anything shared by the whole pass is innocent. - **Not the directory walk:** 50 ms warm over all 40,000 entries. - **Not reading the database:** every row, ancestor chain and stream read back out is under 0.2 s. - **Not the writes:** they are the same count in both arrangements. That leaves the step that turns one library's walk into rows and decides what moved — `crates/jellyfin-app/src/scan/` — as the only place the time can be. Look for a per-entry lookup against a `Vec` (or any repeated linear scan of the filed set) rather than a map: an O(n) probe inside an O(n) loop over one library's entries is exactly the shape that splits in half when the library does. ## Reproducing The tree is **not** in the repository and must not go in — 20,000 directories is a load, not a fixture. Rebuild it deterministically: ```python import os, random random.seed(11) A = "Blue Red Green Silver Golden Hidden Broken Distant Quiet Burning Frozen Crimson Hollow Rising Falling Endless Silent Bitter Sacred Wild".split() B = "Field Signal Harbour Beacon Tide Vault Ember Cipher Orbit Anchor Lantern Circuit Meridian Fathom Relay Prism Ledger Compass Grove Vector".split() C = "Rain Dust Iron Glass Salt Ash Stone Wire Frost Bloom Echo Drift Fable Mire Shard Vein Quill Reef Spire Thread".split() root, seed = "/home/alex/.cache/bigscan/movies", "/home/alex/.cache/bigscan/seed.mp4" seen, n = set(), 0 while n < 20000: name, year = f"{random.choice(A)} {random.choice(B)} {random.choice(C)}", random.randint(1950, 2025) if (name, year) in seen: continue seen.add((name, year)); d = f"{name} ({year})" os.makedirs(os.path.join(root, d), exist_ok=True) try: os.link(seed, os.path.join(root, d, d + ".mp4")) except FileExistsError: pass n += 1 ``` `seed.mp4` is any small real video — the fixture's `reference/var/media/movies/Blue Field (2020)/Blue Field (2020).mp4` does. As of writing the tree is still at `~/.cache/bigscan/movies`, and `~/.cache/bigscan/run/` holds the previous scripts and raw numbers. Point a **scratch** config at it — a copy of `config.toml` with its own `[paths]` and one `[[libraries]]` — and drive it with `POST /Library/Refresh`. Do **not** add it to the repository's `config.toml` and do **not** scan it into the reference. Use `--release`; the numbers above are release and a debug build is not the same shape. ## Done when There is a number, and it is a better one. Concretely: - The pass over an unchanged tree is close to linear in the number of films, so 20,000 costs about twice 10,000 rather than four times. - `docs/benchmarks.md` carries the new table beside the old one — the old numbers stay, so the change is legible. - Whatever the fix is, it has a test that pins the shape rather than the seconds: seconds are the machine's, but "one library of 2n costs about twice one library of n" can be asserted on counts (queries issued, comparisons made) in a unit test. - `JELLYFIN_RS_REQUIRE_FIXTURES=1 cargo nextest run --workspace` green (2092 at the time of writing). If it turns out the shape is inherent rather than accidental, say so with the evidence and write that down instead — an honest "this is why" is a better outcome than a change that moves the constant and leaves the exponent. ## Before you start - `CLAUDE.md` is the contract. `cargo nextest`, not `cargo test`. Comments describe the current state, never the history, and carry no milestone terminology. - Read upstream at `upstream/` in this repo — the pinned checkout. **Not** `../jellyfin`, which is on a divergent branch. Upstream's own scan cost over the same tree has never been taken; if you take it, that is a useful number in its own right and belongs in `docs/benchmarks.md`. - Never `git add -A`, and never symlink `reference/var`, `reference/snapshots`, `reference/media` or `reference/published` into a worktree — they are gitignored, and committing such a link deletes the real fixture. That has happened. - Do not write to, re-provision or re-snapshot the reference on `:8096`.
Claude commented 2026-08-14 02:00:43 +02:00
Author
Collaborator
Copy link

Localized to one function, while working on #95. Not fixed — measured, and narrower than this issue could say when it was written.

Stage timings over a 4,200-film tree, all-unchanged rescan, debug build:

walk            157 ms   (8,400 entries)
listing          23 ms
library_tree  129,434 ms   ← 129 s of a 139 s rescan
library         121 ms

So the walk really is innocent (this issue already said 50 ms over 40,000 entries), the database really is innocent, and the whole cost is the resolve. Inside crates/jellyfin-app/src/scan/tree/mod.rs, files_in / directories_in scan the entry list once per directory — an O(n) probe inside an O(n) loop over one library's entries, which is exactly the shape this issue predicted and is why the cost halves when the same films are declared as two libraries.

The tree is reproducible, and cheaper to build than the one in the issue body since every file is a copy of one 98 KB sample:

python3 -c '
import shutil, pathlib
src = "reference/var/media/movies/Blue Field (2020)/Blue Field (2020).mp4"
root = pathlib.Path("var/media/big")
for i in range(1, 4201):
    d = root / f"Film {i:04d} (2020)"; d.mkdir(parents=True, exist_ok=True)
    shutil.copy(src, d / f"Film {i:04d} (2020).mp4")'

Declare it as a movies library, let the boot scan finish, then start a second scan — the second one runs no prober at all, so what it measures is this and nothing else.

One thing that changed underneath this issue: a scan is now cancellable at the grain of a directory walked and a directory resolved (#95), so 129 seconds of resolve is interruptible where it was not. That makes the wait escapable; it does not make it short, and this issue is still the one that makes it short.

**Localized to one function, while working on #95.** Not fixed — measured, and narrower than this issue could say when it was written. Stage timings over a 4,200-film tree, all-unchanged rescan, debug build: ``` walk 157 ms (8,400 entries) listing 23 ms library_tree 129,434 ms ← 129 s of a 139 s rescan library 121 ms ``` So the walk really is innocent (this issue already said 50 ms over 40,000 entries), the database really is innocent, and **the whole cost is the resolve**. Inside `crates/jellyfin-app/src/scan/tree/mod.rs`, `files_in` / `directories_in` scan the entry list once per directory — an O(n) probe inside an O(n) loop over one library's entries, which is exactly the shape this issue predicted and is why the cost halves when the same films are declared as two libraries. The tree is reproducible, and cheaper to build than the one in the issue body since every file is a copy of one 98 KB sample: ```sh python3 -c ' import shutil, pathlib src = "reference/var/media/movies/Blue Field (2020)/Blue Field (2020).mp4" root = pathlib.Path("var/media/big") for i in range(1, 4201): d = root / f"Film {i:04d} (2020)"; d.mkdir(parents=True, exist_ok=True) shutil.copy(src, d / f"Film {i:04d} (2020).mp4")' ``` Declare it as a `movies` library, let the boot scan finish, then start a second scan — the second one runs no prober at all, so what it measures is this and nothing else. One thing that changed underneath this issue: a scan is now cancellable at the grain of a directory walked and a directory resolved (#95), so 129 seconds of resolve is interruptible where it was not. That makes the wait escapable; it does not make it short, and this issue is still the one that makes it short.
alex closed this issue 2026-08-16 11:18:36 +02:00
Sign in to join this conversation.
No Branch/Tag specified
Branches Tags
main
No results found.
Labels
Clear labels   
correctness
Diverges from upstream

  
encoding
Transcoding, ffmpeg, and the arg strings

  
http
Route behaviour

  
jobs
Scheduled tasks

  
operations
Installing a server and keeping one running

  
p1
Do this first

  
p2
After the p1s

  
p3
Real, and not urgent

  
performance
Speed or resource use

  
providers
Metadata from somewhere other than the file

  
scanner
The library scan

  
security
Who is allowed to see what

  
testing
Test coverage and harness

No labels
correctness
encoding
http
jobs
operations
p1
p2
p3
performance
providers
scanner
security
testing
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference
alex/ephyra#92
No description provided.