dotnet / dotnet/runtime

Optimize eligible character-set scans in the default regex interpreter

Open
#130,918 2 comments 0 reactions 0 assignees View on GitHub
area-System.Text.RegularExpressions tenet-performance
Dominant language
C#
Stars
18.3k
Forks
5.6k
PR merge metrics
PR metrics pending

Description

### Description

The default regex interpreter performs scalar, per-character `RegexCharClass.CharInClass` work when searching for candidate positions for leading or fixed-distance character sets. Compiled and source-generated regexes can instead use `SearchValues` / `IndexOfAny`-style vectorized scans.

There is a real optimization opportunity for the interpreter when a set scan can skip substantial portions of the input. An experiment in #130602 demonstrated large gains, but that PR is being abandoned rather than merged because its implementation complexity and maintenance cost were disproportionate to the narrow applicable surface, particularly late in the .NET 11 cycle.

#### Scope and impact

This is **not a broad speedup for all interpreted regexes**. The demonstrated opportunity is limited to:

- the default interpreted engine;
- left-to-right leading or fixed-distance character-set searches;
- sets containing more than five extracted characters; and
- inputs where matches are absent or sparse enough for vectorized search to skip long spans.

The strongest demonstrated cases were rare ASCII sets such as `[BFGHJKQVWXZ]` and non-ASCII sets on long no-match or sparse-match inputs. Common ASCII sets such as `[a-zA-Z]` and negated sets require care: depending on the input distribution, vectorization may regress or improve substantially.

The abandoned implementation intentionally excluded common/high-frequency and negated sets, making its practical eligible surface narrow even though the interpreter itself is the default engine.

### Configuration

Local A/B measurements used Apple Silicon and .NET 11 preview builds. Exact binaries were rebuilt from:

- scalar parent: `7aa830a0359`
- pre-guard experiment: `3491e696608`
- final guarded experiment: `369e6e94e30`

BenchmarkDotNet was run in independent SHA-bound `corerun` processes with interleaved rounds to control thermal drift. Standard out-of-process BDN was blocked by its unrecognized `net11` runtime-moniker handling.

### Regression?

No. This is an optimization opportunity in existing interpreter behavior.

### Data

Drift-corrected results from the guarded experiment:

| Scenario | Approximate improvement | Applicability |
|---|---:|---|
| Rare ASCII set, 16-character input | **2.1x** | Eligible |
| Rare ASCII set, medium input | **12x** | Eligible |
| Rare ASCII set, long/huge input | **14–19x** | Eligible |
| Non-ASCII Greek set, long no-match | **~40x** | Eligible |
| `[a-zA-Z]{3}` | ~1.0x | Guarded out; scalar retained |
| `[^A-Za-z0-9_]` | ~1.0x | Guarded out; scalar retained |

Steady-state allocation for eligible scans was **0 B**. The `SearchValues` instance incurred a one-time lazy construction cost.

A three-way scalar / vectorize-all / guarded comparison illustrates why selecting the eligible surface is difficult:

| Scenario | Scalar | Vectorize-all | Guarded | Result |
|---|---:|---:|---:|---|
| `[a-zA-Z]{3}` | 5312 ns | 13907 ns | 5025 ns | Unguarded vectorization was **2.6x slower** |
| `[BFGHJKQVWXZ]` | 1971 ns | 143 ns | 138 ns | ~14x win retained |
| Greek non-ASCII set | 50296 ns | 1141 ns | 1104 ns | ~45x win retained |
| `[^A-Za-z0-9_]` | 1982 ns | 160 ns | 2025 ns | Conservative guard discarded an input-specific ~12x win |

These figures demonstrate both the size of the opportunity and its workload-dependent scope. Controls covering small sets, categories, ranges, right-to-left, NonBacktracking, compiled, and source-generated paths were unchanged.

### Analysis

The abandoned prototype added approximately 138 production lines, including two new find modes, interpreter-specific dispatch, lazy thread-safe `SearchValues` state, and a second scan loop for fixed-distance sets. That is too much foundational complexity for the demonstrated narrow eligibility.

A future attempt, potentially early in .NET 12, should require:

- sponsorship/review from Regex area owners;
- a substantially simpler implementation, ideally avoiding new find modes and duplicated scan logic;
- durable `dotnet/performance` benchmarks across realistic short/long, match/no-match, sparse/dense, ASCII/non-ASCII, negated, culture, timeout, and engine-control cases;
- an eligibility strategy that prevents common-set regressions without unnecessarily excluding sparse negated-set wins; and
- enough development-cycle bake time for this foundational path.

Prior experiment and full discussion: #130602.

> [!NOTE]
> This issue was drafted with the assistance of GitHub Copilot (AI-generated).

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the abandoned implementation and discussion in #130602, including the guarded experiment and its SHA-bound measurements. Run durable dotnet/performance benchmarks covering the listed set, input, match-density, encoding, culture, timeout, and engine-control cases. Done means a substantially simpler implementation with no common-set regressions and evidence across the required scenarios.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.