NaturalStringComparer builds a new Regex on every Compare call, so sorting large lists is slow and allocation-heavy

[matt-edmondson]

What's wrong

Sorting/NaturalStringComparer.cs:21 defines CreateNaturalChunkRegex() => new(@"(\d+)|(\D+)"). Compare calls it on every comparison (around line 55), then copies both match collections into arrays.

The SYSLIB1045 ("use GeneratedRegex") warning is suppressed with Justification = "<Pending>". That suggests the fix was intended and never made.

A sort makes O(n log n) comparisons. Each one pays for:

• constructing and parsing a Regex
• two MatchCollections plus their Match objects
• two array copies

Measured impact

Release build, sorting 50,000 file names with List.Sort(new NaturalStringComparer()), about 857k comparisons:

Variant	Time	Allocated per compare
Current (new Regex per compare)	4.43 s	≈7.6 KB
Cached static Regex, nothing else changed	3.22 s	≈3.5 KB

A comparer that walks the chunks directly, with no Regex and no Match objects, should do much better again. The comparer is used for things like file lists and UI tables, where multi-second sorts are noticeable.

Suggested fix / acceptance criteria

• At minimum, replace the per-call construction with a [GeneratedRegex] / static instance, and remove the <Pending> suppression.
• Preferably, replace the Regex with a character scanner that walks both strings chunk by chunk using char.IsDigit. This keeps the current semantics, including the leading-zero and very-long-digit-run handling, and allocates nothing per compare.
• Add a benchmark or a coarse perf test, and keep all existing ordering tests passing.
• NaturalStringComparer is intransitive for non-ASCII digits (٥ < 10 < z < ٥), so sort output depends on input order #55 (non-ASCII digits) touches the same code; the two can be fixed together.

[matt-edmondson]

Triage

• Category: Improvement (performance)
• Priority: Medium. Sort results are correct, but a 50k-item sort takes several seconds and allocates about 7.6 KB per compare. The <Pending> SYSLIB1045 suppression shows this was meant to be fixed.
• Area / suggested assignee: NaturalStringComparer.cs (chunking). Owner: @matt-edmondson
• Duplicates / in progress: no duplicate. Open PR Keep NaturalStringComparer transitive across digit scripts #57 ("Keep NaturalStringComparer transitive across digit scripts", for NaturalStringComparer is intransitive for non-ASCII digits (٥ < 10 < z < ٥), so sort output depends on input order #55) changes the same comparer. Rebase this work on Keep NaturalStringComparer transitive across digit scripts #57, or fold the Regex-free scanner into it, so the two changes don't conflict and the non-ASCII digit semantics carry over.
• Next step: at minimum, use a cached [GeneratedRegex]. The better fix is an allocation-free char.IsDigit chunk scanner, with the existing ordering tests plus a coarse perf test.

---

Generated by Claude Code