Bundle provider: memoise directory name sets per Load in FileSystemBundleProvider (flat-directory O(n²))

Open
#205 0 comments 0 reactions 0 assignees View on GitHub

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

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

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from jchable/okf4net

All issues in jchable/okf4net

Similar issues

More C# issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.