Bundle provider: memoise directory name sets per Load in FileSystemBundleProvider (flat-directory O(n²))
Maintainers usually reply within 1 day
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 25/100
- Issue type
- Refactor
- Clarity
- Mostly clear
- Activity status
- Active
- Tech stack
- csharp
- Domain
- backend, performance
Research direction
Start with FileSystemBundleProvider.ResolveExact, which lists each directory and compares names per segment, and with BundleLoadPerformanceTests, which does not expose the flat-directory cost. Read the trade-off in plan r5 and spec §2 before changing when the exact-case check runs, since the issue asks for a decision on that first. Done means a per-load directory memo bounded by BundleLimits, with a benchmark on a flat directory of a few thousand concepts showing the cost is no longer quadratic.
Written by the indexing model from the issue text.
Description
Follow-up of lot A (#139, branch feat/bundle-provider-a), from the final whole-branch review.
Problem. FileSystemBundleProvider.ResolveExact decides each segment by listing the directory and comparing names ordinally (exact-case matching on Windows/macOS). On .NET the listing is a full NtQueryDirectoryFile / readdir with the pattern matched in managed code, so every level of every Read/Exists/Enumerate(prefix) costs O(entries in that directory). Loading a bundle reads every concept, so a flat bundle of n concepts costs O(n²) entry comparisons per load. BundleLoadPerformanceTests (2 001 concepts, 4×5×100 tree) hides it; a flat directory of a few thousand concepts would show it.
Option. Memoise each directory's entry-name set for the duration of one Bundle.Load (or of one provider snapshot), so a directory is listed once per load. BCL-only code cannot ask the kernel for one exact name (that would be FindFirstFileEx with a filter, i.e. P/Invoke, excluded by the zero-dependency rule).
Trade-off to rule on. Today the exact-case correspondence is established at the moment of each access (plan r5, spec §2 "before reading"). With a memo it is established at listing time: a case-only rename between the listing and the read could open the twin on a case-folding volume. The STRICT reparse-point guard would still run at access time, so no escape outside the root — the weakening is inside the inter-process window already accepted in #178. The memo must also stay bounded by BundleLimits and must not outlive the load.
Out of scope here: the incremental guard in ResolveExact (each traversed directory inspected once per call), done in lot A.
- Dominant language
- C#
- Stars
- 4
- Forks
- 1
- Avg merge
- 1d 4h
- Merged PRs (30d)
- 32
Getting set up
- No Dockerfile or Docker Compose file
- Has a pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from jchable/okf4net
-
documentation
Difficulty 2/5 1-3 hours Newbie friendliness 85/100
Maintainers usually reply within 1 day
-
.NET bug
Difficulty 2/5 1-3 hours Newbie friendliness 85/100
Maintainers usually reply within 1 day
-
test
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 1 day
-
documentation good first issue
Difficulty 1/5 1-3 hours Newbie friendliness 90/100
Maintainers usually reply within 1 day
-
documentation good first issue
Difficulty 1/5 Under an hour Newbie friendliness 82/100
Maintainers usually reply within 1 day
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
-
area/backend type/bug
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
umbraco/Umbraco-CMS#24668 · 1 comment ·
Maintainers usually reply within 1 day
-
Pri3
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
MicrosoftDocs/windows-dev-docs#6205 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
Maintainers usually reply within 1 day
-
area-ai untriaged
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
dotnet/extensions#7956 ·
Maintainers usually reply within 1 day