dotnet / dotnet/roslyn

Suboptimal lowering for list patterns that can be handled by `.StartsWith/.EndsWith`

Open
#77,908 3 comments 1 reaction 0 assignees View on GitHub
Area-Compilers Code Gen Quality
Dominant language
C#
Stars
20.7k
Forks
4.3k
PR merge metrics
PR metrics pending

Description

Given
```cs
static bool Test(ReadOnlySpan data)
{
if (data.Length < 8)
return false;

return data
is [0x01, 0x02, 0x03, 0x04, ..]
or [0x05, 0x06, 0x07, 0x08, ..]
or [0x09, 0x0A, 0x0B, 0x0C, ..]
or [0x0D, 0x0E, 0x0F, 0x10, ..]
or [0x11, 0x12, 0x13, 0x14, ..]
or [0x15, 0x16, 0x17, 0x18, ..]
or [0x19, 0x1A, 0x1B, 0x1C, ..];
}
```
it appears that Roslyn compiles such patterns to
```
static bool Test(ReadOnlySpan data)
{
if (data.Length < 8)
{
return false;
}
if (data.Length >= 4)
{
byte b = data[0];
if ((uint)b <= 9u)
{
if (b != 1)
{
if (b != 5)
{
if (b == 9 && data[1] == 10 && data[2] == 11 && data[3] == 12)
{
goto IL_01ad;
}
}
else if (data[1] == 6 && data[2] == 7 && data[3] == 8)
{
goto IL_01ad;
}
}
else if (data[1] == 2 && data[2] == 3 && data[3] == 4)
{
goto IL_01ad;
}
}
else if ((uint)b <= 17u)
{
if (b != 13)
{
if (b == 17 && data[1] == 18 && data[2] == 19 && data[3] == 20)
{
goto IL_01ad;
}
}
else if (data[1] == 14 && data[2] == 15 && data[3] == 16)
{
goto IL_01ad;
}
}
else if (b != 21)
{
if (b == 25 && data[1] == 26 && data[2] == 27 && data[3] == 28)
{
goto IL_01ad;
}
}
else if (data[1] == 22 && data[2] == 23 && data[3] == 24)
{
goto IL_01ad;
}
}
return false;
IL_01ad:
return true;
}
```

This is not efficient as it results in a multitude of byte-by-byte comparisons which are not required here (and no, JIT will not optimize these away because it is a complex set of conditions).

It would be great if Roslyn could emit the following instead:
```cs
...
return
data.StartsWith((ReadOnlySpan)[0x01, 0x02, 0x03, 0x04]) ||
data.StartsWith((ReadOnlySpan)[0x05, 0x06, 0x07, 0x08]) ||
data.StartsWith((ReadOnlySpan)[0x09, 0x0A, 0x0B, 0x0C]) ||
data.StartsWith((ReadOnlySpan)[0x0D, 0x0E, 0x0F, 0x10]) ||
data.StartsWith((ReadOnlySpan)[0x11, 0x12, 0x13, 0x14]) ||
data.StartsWith((ReadOnlySpan)[0x15, 0x16, 0x17, 0x18]) ||
data.StartsWith((ReadOnlySpan)[0x19, 0x1A, 0x1B, 0x1C]);
```
which results in a much more efficient codegen (and could be a subject to further and better JIT optimization).

They key defining factor is that primitive comparisons up to a machine word size would be more efficient if simply merged together (or even beyond that, to an extent), which is what happens when .StartsWith is called - it's just a single `uint` comparison (even if the codegen is not perfect currently). It is massively cheaper than doing byte-by-byte reads.

Contributor guide

Open the contributing guide

Research direction

The issue names no source files or tests. Start by locating Roslyn’s lowering implementation for list patterns and its compiler tests, then compare the generated code for the shown ReadOnlySpan patterns. Done means the eligible patterns lower to StartsWith-equivalent behavior and tests cover the generated output and semantics.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
compilers
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.