Suboptimal lowering for list patterns that can be handled by `.StartsWith/.EndsWith`
- 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
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