Reuse length check when matching multiple constant strings #101184

jnyrup · 2024-04-17T14:30:30Z

jnyrup
Apr 17, 2024

When looking at the generated ASM for M1, s is null checked a single time, but its Length is checked before each comparison with the constant strings.

static bool M1(string s) => s is "ABCD" or "EFGH" or "IJKL" or "MNOP" or "QRST" or "UVWX";

L0000: test rcx, rcx
L0003: je L0091
L0009: mov eax, [rcx+8]
L000c: cmp eax, 4
L000f: jne short L0021
L0011: mov rdx, 0x44004300420041
L001b: cmp [rcx+0xc], rdx
L001f: je short L008a
L0021: cmp eax, 4
L0024: jne short L0036
L0026: mov rdx, 0x48004700460045
L0030: cmp [rcx+0xc], rdx
L0034: je short L008a
L0036: cmp eax, 4
L0039: jne short L004b
L003b: mov rdx, 0x4c004b004a0049
L0045: cmp [rcx+0xc], rdx
L0049: je short L008a
L004b: cmp eax, 4
L004e: jne short L0060
L0050: mov rdx, 0x50004f004e004d
L005a: cmp [rcx+0xc], rdx
L005e: je short L008a
L0060: cmp eax, 4
L0063: jne short L0075
L0065: mov rdx, 0x54005300520051
L006f: cmp [rcx+0xc], rdx
L0073: je short L008a
L0075: cmp eax, 4
L0078: jne short L0091
L007a: mov rax, 0x58005700560055
L0084: cmp [rcx+0xc], rax
L0088: jne short L0091
L008a: mov eax, 1
L008f: jmp short L0093
L0091: xor eax, eax
L0093: ret

As all the constant strings are of length 4, we can make a single length check on s.
Doing this generates ASM where we only have a single null check and a single length check.

static bool M2(string s) => s is { Length: 4 } and ("ABCD" or "EFGH" or "IJKL" or "MNOP" or "QRST" or "UVWX");

L0000: test rcx, rcx
L0003: je short L0070
L0005: cmp dword ptr [rcx+8], 4
L0009: jne short L0070
L000b: mov rax, [rcx+0xc]
L000f: mov rcx, 0x44004300420041
L0019: cmp rax, rcx
L001c: je short L0069
L001e: mov rcx, 0x48004700460045
L0028: cmp rax, rcx
L002b: je short L0069
L002d: mov rcx, 0x4c004b004a0049
L0037: cmp rax, rcx
L003a: je short L0069
L003c: mov rcx, 0x50004f004e004d
L0046: cmp rax, rcx
L0049: je short L0069
L004b: mov rcx, 0x54005300520051
L0055: cmp rax, rcx
L0058: je short L0069
L005a: mov rcx, 0x58005700560055
L0064: cmp rax, rcx
L0067: jne short L0070
L0069: mov eax, 1
L006e: jmp short L0072
L0070: xor eax, eax
L0072: ret

It is possible for the JIT to perform a similar reasoning?

// * Summary *

BenchmarkDotNet v0.13.12, Windows 10 (10.0.19045.4291/22H2/2022Update)
Intel Core i7-10750H CPU 2.60GHz, 1 CPU, 12 logical and 6 physical cores
.NET SDK 9.0.100-preview.3.24204.13
[Host] : .NET 9.0.0 (9.0.24.17209), X64 RyuJIT AVX2
DefaultJob : .NET 9.0.0 (9.0.24.17209), X64 RyuJIT AVX2

Method	Value	Mean	Error	StdDev	Ratio	RatioSD
M1	ABCD	0.3123 ns	0.0136 ns	0.0121 ns	1.00	0.00
M2	ABCD	0.2515 ns	0.0109 ns	0.0091 ns	0.80	0.04

M1	UVWX	2.1046 ns	0.0168 ns	0.0149 ns	1.00	0.00
M2	UVWX	1.3229 ns	0.0189 ns	0.0168 ns	0.63	0.01

M1	UVWZ	1.3901 ns	0.0206 ns	0.0193 ns	1.00	0.00
M2	UVWZ	1.2863 ns	0.0526 ns	0.0492 ns	0.93	0.03

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkRunner.Run<Benchmark>();

public class Benchmark
{
    [Params("ABCD", "UVWX", "UVWZ")]
    public string Value { get; set; }

    [Benchmark(Baseline = true)]
    public bool M1() => Value is "ABCD" or "EFGH" or "IJKL" or "MNOP" or "QRST" or "UVWX";

    [Benchmark]
    public bool M2() => Value is { Length: 4 } and ("ABCD" or "EFGH" or "IJKL" or "MNOP" or "QRST" or "UVWX");
}

And similarly when doing unrolled case-insensitive string comparisons M3 has 6 or, while M4 has a single.

using static System.StringComparison;

static bool M3(string s) =>
    "ABCD".Equals(s, OrdinalIgnoreCase) ||
    "EFGH".Equals(s, OrdinalIgnoreCase) ||
    "IJKL".Equals(s, OrdinalIgnoreCase) ||
    "MNOP".Equals(s, OrdinalIgnoreCase) ||
    "QRST".Equals(s, OrdinalIgnoreCase) ||
    "UVWX".Equals(s, OrdinalIgnoreCase);

static bool M4(string s) => s is { Length: 4} && (
    "ABCD".Equals(s, OrdinalIgnoreCase) ||
    "EFGH".Equals(s, OrdinalIgnoreCase) ||
    "IJKL".Equals(s, OrdinalIgnoreCase) ||
    "MNOP".Equals(s, OrdinalIgnoreCase) ||
    "QRST".Equals(s, OrdinalIgnoreCase) ||
    "UVWX".Equals(s, OrdinalIgnoreCase));

Program.<<Main>$>g__M3|0_0(System.String)
    L0000: test rcx, rcx
    L0003: je L00e6
    L0009: mov eax, [rcx+8]
    L000c: cmp eax, 4
    L000f: jne short L0032
    L0011: mov rdx, 0x20002000200020
    L001b: or rdx, [rcx+0xc]
    L001f: mov r8, 0x64006300620061
    L0029: cmp rdx, r8
    L002c: je L00e9
    L0032: cmp eax, 4
    L0035: jne short L0058
    L0037: mov rdx, 0x20002000200020
    L0041: or rdx, [rcx+0xc]
    L0045: mov r8, 0x68006700660065
    L004f: cmp rdx, r8
    L0052: je L00e9
    L0058: cmp eax, 4
    L005b: jne short L007a
    L005d: mov rdx, 0x20002000200020
    L0067: or rdx, [rcx+0xc]
    L006b: mov r8, 0x6c006b006a0069
    L0075: cmp rdx, r8
    L0078: je short L00e9
    L007a: cmp eax, 4
    L007d: jne short L009c
    L007f: mov rdx, 0x20002000200020
    L0089: or rdx, [rcx+0xc]
    L008d: mov r8, 0x70006f006e006d
    L0097: cmp rdx, r8
    L009a: je short L00e9
    L009c: cmp eax, 4
    L009f: jne short L00be
    L00a1: mov rdx, 0x20002000200020
    L00ab: or rdx, [rcx+0xc]
    L00af: mov r8, 0x74007300720071
    L00b9: cmp rdx, r8
    L00bc: je short L00e9
    L00be: cmp eax, 4
    L00c1: jne short L00e6
    L00c3: mov rax, 0x20002000200020
    L00cd: or rax, [rcx+0xc]
    L00d1: mov rcx, 0x78007700760075
    L00db: cmp rax, rcx
    L00de: sete al
    L00e1: movzx eax, al
    L00e4: jmp short L00e8
    L00e6: xor eax, eax
    L00e8: ret
    L00e9: mov eax, 1
    L00ee: ret

Program.<<Main>$>g__M4|0_1(System.String)
    L0000: test rcx, rcx
    L0003: je short L007e
    L0005: cmp dword ptr [rcx+8], 4
    L0009: jne short L007e
    L000b: mov rax, 0x20002000200020
    L0015: or rax, [rcx+0xc]
    L0019: mov rcx, 0x64006300620061
    L0023: cmp rax, rcx
    L0026: je short L0078
    L0028: mov rcx, 0x68006700660065
    L0032: cmp rax, rcx
    L0035: je short L0078
    L0037: mov rcx, 0x6c006b006a0069
    L0041: cmp rax, rcx
    L0044: je short L0078
    L0046: mov rcx, 0x70006f006e006d
    L0050: cmp rax, rcx
    L0053: je short L0078
    L0055: mov rcx, 0x74007300720071
    L005f: cmp rax, rcx
    L0062: je short L0078
    L0064: mov rcx, 0x78007700760075
    L006e: cmp rax, rcx
    L0071: sete al
    L0074: movzx eax, al
    L0077: ret
    L0078: mov eax, 1
    L007d: ret
    L007e: xor eax, eax
    L0080: ret

hez2010 · 2024-04-17T15:45:19Z

hez2010
Apr 17, 2024

/cc: @EgorBo

0 replies

jnyrup · 2024-09-23T10:02:52Z

jnyrup
Sep 23, 2024
Author

For comparison StartsWith only does a single length check

static bool StartsWith(string s) => s is { } && (s.StartsWith("ABCD", Ordinal) || s.StartsWith("EFGH", Ordinal));

Program.<<Main>$>g__StartsWith|0_0(System.String)
    L0000: test rcx, rcx
    L0003: je short L003c
    L0005: cmp dword ptr [rcx+8], 4
    L0009: jl short L0033
    L000b: mov rax, [rcx+0xc]
    L000f: mov rcx, 0x44004300420041
    L0019: cmp rax, rcx
    L001c: je short L0036
    L001e: mov rcx, 0x48004700460045
    L0028: cmp rax, rcx
    L002b: sete al
    L002e: movzx eax, al
    L0031: jmp short L0035
    L0033: xor eax, eax
    L0035: ret
    L0036: mov eax, 1
    L003b: ret
    L003c: xor eax, eax
    L003e: ret

And EndsWith (since it explicitly wasn't handled in #65288 I presume) does multiple length checks

static bool EndsWith(string s) => s is { } && (s.EndsWith("ABCD", Ordinal) || s.EndsWith("EFGH", Ordinal));

static bool EndsWith2(string s) => s is { Length: >= 4 } && (s.EndsWith("ABCD", Ordinal) || s.EndsWith("EFGH", Ordinal));

Program.<<Main>$>g__EndsWith|0_1(System.String)
    L0000: push rbx
    L0001: sub rsp, 0x20
    L0005: mov rbx, rcx
    L0008: test rbx, rbx
    L000b: je short L0066
    L000d: mov rdx, 0x1e280070938
    L0017: mov rdx, [rdx]
    L001a: mov rcx, rbx
    L001d: mov r8d, 4
    L0023: mov rax, 0x7ffcbcde6130
    L002d: call qword ptr [rax]
    L002f: test eax, eax
    L0031: jne short L005b
    L0033: mov rdx, 0x1e280070968
    L003d: mov rdx, [rdx]
    L0040: mov rcx, rbx
    L0043: mov r8d, 4
    L0049: mov rax, 0x7ffcbcde6130
    L0053: add rsp, 0x20
    L0057: pop rbx
    L0058: jmp qword ptr [rax]
    L005b: mov eax, 1
    L0060: add rsp, 0x20
    L0064: pop rbx
    L0065: ret
    L0066: xor eax, eax
    L0068: add rsp, 0x20
    L006c: pop rbx
    L006d: ret

Program.<<Main>$>g__EndsWith2|0_2(System.String)
    L0000: push rbx
    L0001: sub rsp, 0x20
    L0005: mov rbx, rcx
    L0008: test rbx, rbx
    L000b: je short L006c
    L000d: cmp dword ptr [rbx+8], 4
    L0011: jl short L006c
    L0013: mov rdx, 0x1e280070938
    L001d: mov rdx, [rdx]
    L0020: mov rcx, rbx
    L0023: mov r8d, 4
    L0029: mov rax, 0x7ffcbcde6130
    L0033: call qword ptr [rax]
    L0035: test eax, eax
    L0037: jne short L0061
    L0039: mov rdx, 0x1e280070968
    L0043: mov rdx, [rdx]
    L0046: mov rcx, rbx
    L0049: mov r8d, 4
    L004f: mov rax, 0x7ffcbcde6130
    L0059: add rsp, 0x20
    L005d: pop rbx
    L005e: jmp qword ptr [rax]
    L0061: mov eax, 1
    L0066: add rsp, 0x20
    L006a: pop rbx
    L006b: ret
    L006c: xor eax, eax
    L006e: add rsp, 0x20
    L0072: pop rbx
    L0073: ret

0 replies

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Reuse length check when matching multiple constant strings #101184

{{title}}

{{editor}}'s edit

{{editor}}'s edit

Replies: 2 comments

{{title}}

{{title}}

Select a reply

Reuse length check when matching multiple constant strings #101184

jnyrup Apr 17, 2024

Replies: 2 comments

hez2010 Apr 17, 2024

jnyrup Sep 23, 2024 Author

jnyrup
Apr 17, 2024

hez2010
Apr 17, 2024

jnyrup
Sep 23, 2024
Author