Improve SequenceEqual for constant lengths unrolling by EgorBo · Pull Request #84524 · dotnet/runtime

EgorBo · 2023-04-08T20:47:49Z

Slightly improve MemoryExtensions.SequenceEqual shape to expose more "constant length" cases for unrolling. It's a JIT phase ordering issue, in theory, if we run VN again after Assert prop we'll do the same in JIT, unfortunately, JIT's logic to run some phases more than once is currently broken.

After this PR, e.g. TryGetFloatingPointConstant is fully unrolled (all three SequenceEqual in it)

ghost · 2023-04-08T20:48:03Z

Tagging subscribers to this area: @dotnet/area-system-memory
See info in area-owners.md if you want to be subscribed.

Issue Details

Slightly improve MemoryExtensions.SequenceEqual shape to expose more "constant length" cases for unrolling. It's a JIT phase ordering issue, in theory, if we run VN again after Assert prop we'll do the same in JIT, unfortunately, JIT's logic to run some phases more than once is currently broken.

After this PR, e.g. TryGetFloatingPointConstant is fully unrolled (all three SequenceEqual in it)

Author:	EgorBo
Assignees:	-
Labels:	`area-System.Memory`
Milestone:	-

src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.cs

xtqqczze · 2023-04-08T23:54:29Z

@EgorBo In theory, the length in (nuint)span.Length should be recognized as never negative, and the sign-extension elided, but doesn't appear to be the case (at least in R2R), see https://csharp.godbolt.org/z/14oW68fqz.

EgorBo · 2023-04-09T23:45:04Z

@xtqqczze thanks for suggestion but in this case I'm interesting in making SequenceEqual more unrolling friendly since some JIT optimizations are a bit too fragile (to be fixed). So the changes you suggested make sense but they brake that shape.

Current diffs:

Total bytes of base: 58409192
Total bytes of diff: 58409396
Total bytes of delta: 204 (0.00 % of base)
Total relative delta: NaN
    diff is a regression.
    relative diff is a regression.


Total byte diff includes -103 bytes from reconciling methods
        Base had    1 unique methods,      103 unique bytes
        Diff had    0 unique methods,        0 unique bytes

Top file regressions (bytes):
         150 : System.Security.Cryptography.Pkcs.dasm (0.03% of base)
         112 : System.Security.Cryptography.dasm (0.01% of base)
          51 : System.Text.Json.dasm (0.00% of base)
          15 : System.Net.Http.dasm (0.00% of base)
           6 : System.Diagnostics.Process.dasm (0.01% of base)
           6 : System.Net.Security.dasm (0.00% of base)
           6 : System.Security.AccessControl.dasm (0.01% of base)
           3 : System.Text.RegularExpressions.dasm (0.00% of base)
           3 : System.Security.Cryptography.Xml.dasm (0.00% of base)
           1 : System.Private.Xml.dasm (0.00% of base)

Top file improvements (bytes):
        -103 : Microsoft.CodeAnalysis.dasm (-0.01% of base)
         -28 : System.Reflection.MetadataLoadContext.dasm (-0.01% of base)
          -7 : Microsoft.Extensions.Primitives.dasm (-0.03% of base)
          -7 : System.Private.CoreLib.dasm (-0.00% of base)
          -4 : System.Formats.Asn1.dasm (-0.00% of base)

15 total files with Code Size differences (5 improved, 10 regressed), 261 unchanged.

Top method regressions (bytes):
          47 ( 3.17% of base) : System.Security.Cryptography.Pkcs.dasm - System.Security.Cryptography.Asn1.PssParamsAsn:Encode(System.Formats.Asn1.AsnWriter,System.Formats.Asn1.Asn1Tag):this
          47 ( 3.16% of base) : System.Security.Cryptography.dasm - System.Security.Cryptography.Asn1.PssParamsAsn:Encode(System.Formats.Asn1.AsnWriter,System.Formats.Asn1.Asn1Tag):this
          28 ( 2.60% of base) : System.Security.Cryptography.Pkcs.dasm - System.Security.Cryptography.Asn1.OaepParamsAsn:Encode(System.Formats.Asn1.AsnWriter,System.Formats.Asn1.Asn1Tag):this
          21 ( 2.03% of base) : System.Security.Cryptography.dasm - Internal.Cryptography.Helpers:AreSamePublicECParameters(System.Security.Cryptography.ECParameters,System.Security.Cryptography.ECParameters):bool
          16 ( 0.64% of base) : System.Security.Cryptography.dasm - System.Security.Cryptography.X509Certificates.Asn1.TbsCertificateAsn:Encode(System.Formats.Asn1.AsnWriter,System.Formats.Asn1.Asn1Tag):this
          16 ( 1.64% of base) : System.Security.Cryptography.dasm - System.Security.Cryptography.X509Certificates.DSACertificateExtensions:CopyWithPrivateKey(System.Security.Cryptography.X509Certificates.X509Certificate2,System.Security.Cryptography.DSA):System.Security.Cryptography.X509Certificates.X509Certificate2
          15 ( 1.94% of base) : System.Net.Http.dasm - System.Net.Http.Http2Connection+Http2Stream:OnHeader(System.ReadOnlySpan`1[ubyte],System.ReadOnlySpan`1[ubyte]):this
          12 ( 3.50% of base) : System.Security.Cryptography.Pkcs.dasm - System.Security.Cryptography.Asn1.Pbkdf2Params:Encode(System.Formats.Asn1.AsnWriter,System.Formats.Asn1.Asn1Tag):this
          12 ( 2.32% of base) : System.Security.Cryptography.Pkcs.dasm - System.Security.Cryptography.Pkcs.Asn1.EssCertIdV2:Encode(System.Formats.Asn1.AsnWriter,System.Formats.Asn1.Asn1Tag):this
          12 ( 0.48% of base) : System.Text.Json.dasm - System.Text.Json.Serialization.Converters.ObjectWithParameterizedConstructorConverter`1[double]:TryLookupConstructorParameter(byref,byref,System.Text.Json.JsonSerializerOptions,byref):bool:this
          12 ( 0.48% of base) : System.Text.Json.dasm - System.Text.Json.Serialization.Converters.ObjectWithParameterizedConstructorConverter`1[int]:TryLookupConstructorParameter(byref,byref,System.Text.Json.JsonSerializerOptions,byref):bool:this
          12 ( 0.48% of base) : System.Text.Json.dasm - System.Text.Json.Serialization.Converters.ObjectWithParameterizedConstructorConverter`1[long]:TryLookupConstructorParameter(byref,byref,System.Text.Json.JsonSerializerOptions,byref):bool:this
          12 ( 0.48% of base) : System.Text.Json.dasm - System.Text.Json.Serialization.Converters.ObjectWithParameterizedConstructorConverter`1[short]:TryLookupConstructorParameter(byref,byref,System.Text.Json.JsonSerializerOptions,byref):bool:this
          12 ( 0.48% of base) : System.Text.Json.dasm - System.Text.Json.Serialization.Converters.ObjectWithParameterizedConstructorConverter`1[System.__Canon]:TryLookupConstructorParameter(byref,byref,System.Text.Json.JsonSerializerOptions,byref):bool:this
          12 ( 0.48% of base) : System.Text.Json.dasm - System.Text.Json.Serialization.Converters.ObjectWithParameterizedConstructorConverter`1[System.Nullable`1[int]]:TryLookupConstructorParameter(byref,byref,System.Text.Json.JsonSerializerOptions,byref):bool:this

Top method improvements (bytes):
        -103 (-100.00% of base) : Microsoft.CodeAnalysis.dasm - Microsoft.CodeAnalysis.SmallDictionary`2[System.__Canon,int]:RightComplex(Microsoft.CodeAnalysis.SmallDictionary`2+AvlNode[System.__Canon,int]):Microsoft.CodeAnalysis.SmallDictionary`2+AvlNode[System.__Canon,int] (1 base, 0 diff methods)
         -40 (-2.95% of base) : System.Text.Json.dasm - System.Text.Json.JsonDocument:TryGetNamedPropertyValue(int,int,System.ReadOnlySpan`1[ubyte],byref):bool:this
         -22 (-0.72% of base) : System.Reflection.MetadataLoadContext.dasm - System.Reflection.TypeLoading.Ecma.EcmaModule:GetTypeCoreNoCache(System.ReadOnlySpan`1[ubyte],System.ReadOnlySpan`1[ubyte],byref):System.Reflection.TypeLoading.RoDefinitionType:this
         -14 (-3.47% of base) : System.Text.Json.dasm - System.Text.Json.JsonReaderHelper:TryGetFloatingPointConstant(System.ReadOnlySpan`1[ubyte],byref):bool (2 methods)
          -8 (-0.58% of base) : System.Private.CoreLib.dasm - System.IO.Path:GetFullPath(System.String,System.String):System.String
          -7 (-3.95% of base) : Microsoft.Extensions.Primitives.dasm - Microsoft.Extensions.Primitives.StringSegment:Equals(System.String):bool:this
          -7 (-4.35% of base) : Microsoft.Extensions.Primitives.dasm - Microsoft.Extensions.Primitives.StringSegment:op_Equality(Microsoft.Extensions.Primitives.StringSegment,Microsoft.Extensions.Primitives.StringSegment):bool
          -7 (-4.05% of base) : Microsoft.Extensions.Primitives.dasm - Microsoft.Extensions.Primitives.StringSegment:op_Inequality(Microsoft.Extensions.Primitives.StringSegment,Microsoft.Extensions.Primitives.StringSegment):bool
          -7 (-2.11% of base) : System.Private.CoreLib.dasm - System.String:MakeSeparatorListAny(System.ReadOnlySpan`1[ushort],System.ReadOnlySpan`1[System.String],byref,byref)
          -6 (-0.32% of base) : System.Reflection.MetadataLoadContext.dasm - System.Reflection.TypeLoading.Ecma.EcmaCustomAttributeHelpers:TypeMatchesNameAndNamespace(System.Reflection.Metadata.EntityHandle,System.ReadOnlySpan`1[ubyte],System.ReadOnlySpan`1[ubyte],System.Reflection.Metadata.MetadataReader):bool
          -6 (-4.51% of base) : System.Security.Cryptography.dasm - System.Security.Cryptography.CngProperty:Equals(System.Security.Cryptography.CngProperty):bool:this
          -4 (-0.38% of base) : System.Private.CoreLib.dasm - System.Enum:TryParseByName[double](System.RuntimeType,System.ReadOnlySpan`1[ushort],bool,bool,byref):bool
          -4 (-0.38% of base) : System.Private.CoreLib.dasm - System.Enum:TryParseByName[int](System.RuntimeType,System.ReadOnlySpan`1[ushort],bool,bool,byref):bool
          -4 (-0.38% of base) : System.Private.CoreLib.dasm - System.Enum:TryParseByName[long](System.RuntimeType,System.ReadOnlySpan`1[ushort],bool,bool,byref):bool
          -4 (-0.37% of base) : System.Private.CoreLib.dasm - System.Enum:TryParseByName[short](System.RuntimeType,System.ReadOnlySpan`1[ushort],bool,bool,byref):bool

Top method regressions (percentages):
           5 ( 7.81% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:EqualsOrdinal(System.ReadOnlySpan`1[ushort],System.ReadOnlySpan`1[ushort]):bool
           2 ( 5.13% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[double](System.ReadOnlySpan`1[double],System.ReadOnlySpan`1[double]):bool
           2 ( 5.13% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[double](System.Span`1[double],System.ReadOnlySpan`1[double]):bool
           2 ( 5.13% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[System.Numerics.Vector`1[float]](System.ReadOnlySpan`1[System.Numerics.Vector`1[float]],System.ReadOnlySpan`1[System.Numerics.Vector`1[float]]):bool
           2 ( 5.13% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[System.Numerics.Vector`1[float]](System.Span`1[System.Numerics.Vector`1[float]],System.ReadOnlySpan`1[System.Numerics.Vector`1[float]]):bool
           2 ( 4.76% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[ubyte](System.ReadOnlySpan`1[ubyte],System.ReadOnlySpan`1[ubyte]):bool
           2 ( 4.76% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[ubyte](System.Span`1[ubyte],System.ReadOnlySpan`1[ubyte]):bool
           7 ( 4.55% of base) : Microsoft.Extensions.Primitives.dasm - Microsoft.Extensions.Primitives.StringSegment:Equals(Microsoft.Extensions.Primitives.StringSegment):bool:this
           2 ( 4.44% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[short](System.ReadOnlySpan`1[short],System.ReadOnlySpan`1[short]):bool
           2 ( 4.44% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[short](System.Span`1[short],System.ReadOnlySpan`1[short]):bool
           2 ( 4.35% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[int](System.ReadOnlySpan`1[int],System.ReadOnlySpan`1[int]):bool
           2 ( 4.35% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[int](System.Span`1[int],System.ReadOnlySpan`1[int]):bool
           2 ( 4.35% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[long](System.ReadOnlySpan`1[long],System.ReadOnlySpan`1[long]):bool
           2 ( 4.35% of base) : System.Private.CoreLib.dasm - System.MemoryExtensions:SequenceEqual[long](System.Span`1[long],System.ReadOnlySpan`1[long]):bool
           3 ( 3.95% of base) : System.Security.AccessControl.dasm - System.Security.AccessControl.CommonAcl:AceOpaquesMatch(System.Security.AccessControl.QualifiedAce,System.Security.AccessControl.QualifiedAce):bool

Top method improvements (percentages):
        -103 (-100.00% of base) : Microsoft.CodeAnalysis.dasm - Microsoft.CodeAnalysis.SmallDictionary`2[System.__Canon,int]:RightComplex(Microsoft.CodeAnalysis.SmallDictionary`2+AvlNode[System.__Canon,int]):Microsoft.CodeAnalysis.SmallDictionary`2+AvlNode[System.__Canon,int] (1 base, 0 diff methods)
          -4 (-5.88% of base) : System.Formats.Asn1.dasm - System.Formats.Asn1.AsnWriter:EncodedValueEquals(System.ReadOnlySpan`1[ubyte]):bool:this
          -6 (-4.51% of base) : System.Security.Cryptography.dasm - System.Security.Cryptography.CngProperty:Equals(System.Security.Cryptography.CngProperty):bool:this
          -7 (-4.35% of base) : Microsoft.Extensions.Primitives.dasm - Microsoft.Extensions.Primitives.StringSegment:op_Equality(Microsoft.Extensions.Primitives.StringSegment,Microsoft.Extensions.Primitives.StringSegment):bool
          -7 (-4.05% of base) : Microsoft.Extensions.Primitives.dasm - Microsoft.Extensions.Primitives.StringSegment:op_Inequality(Microsoft.Extensions.Primitives.StringSegment,Microsoft.Extensions.Primitives.StringSegment):bool
          -7 (-3.95% of base) : Microsoft.Extensions.Primitives.dasm - Microsoft.Extensions.Primitives.StringSegment:Equals(System.String):bool:this
         -14 (-3.47% of base) : System.Text.Json.dasm - System.Text.Json.JsonReaderHelper:TryGetFloatingPointConstant(System.ReadOnlySpan`1[ubyte],byref):bool (2 methods)
         -40 (-2.95% of base) : System.Text.Json.dasm - System.Text.Json.JsonDocument:TryGetNamedPropertyValue(int,int,System.ReadOnlySpan`1[ubyte],byref):bool:this
          -7 (-2.11% of base) : System.Private.CoreLib.dasm - System.String:MakeSeparatorListAny(System.ReadOnlySpan`1[ushort],System.ReadOnlySpan`1[System.String],byref,byref)
         -22 (-0.72% of base) : System.Reflection.MetadataLoadContext.dasm - System.Reflection.TypeLoading.Ecma.EcmaModule:GetTypeCoreNoCache(System.ReadOnlySpan`1[ubyte],System.ReadOnlySpan`1[ubyte],byref):System.Reflection.TypeLoading.RoDefinitionType:this
          -3 (-0.69% of base) : System.Text.Json.dasm - System.Text.Json.JsonSerializer:GetMetadataPropertyName(System.ReadOnlySpan`1[ubyte],System.Text.Json.Serialization.Metadata.PolymorphicTypeResolver):ubyte
          -8 (-0.58% of base) : System.Private.CoreLib.dasm - System.IO.Path:GetFullPath(System.String,System.String):System.String
          -3 (-0.56% of base) : System.Net.Security.dasm - System.Net.Security.TlsFrameHelper:TryGetApplicationProtocolsFromExtension(System.ReadOnlySpan`1[ubyte],byref):bool
          -3 (-0.55% of base) : System.Private.CoreLib.dasm - System.Text.EncodingTable:InternalGetCodePageFromName(System.String):int
          -3 (-0.47% of base) : System.Text.Json.dasm - System.Text.Json.Utf8JsonReader:ValueTextEquals(System.ReadOnlySpan`1[ushort]):bool:this

82 total methods with Code Size differences (26 improved, 56 regressed), 374821 unchanged

This PR triggered 23 new unrollings.

Example: https://www.diffchecker.com/525Bokla/

EgorBo · 2023-04-14T16:07:26Z

@stephentoub any thoughts on this? it triggered 23 new unrollings but in theory jit should be able to handle both patterns, but that will need quite some extra efforts

stephentoub · 2023-04-14T16:56:17Z

I'm fine with it if it doesn't regress anything meaningfully.

EgorBo · 2023-04-17T13:52:04Z

I'm fine with it if it doesn't regress anything meaningfully.

@stephentoub It should not (on all runtimes) and number of new unrollings prove it's better to speculate that "other.Length" is likely to be constant. Can you apporve it? 🙂 I needed it for #84525

ghost added the area-System.Memory label Apr 8, 2023

ghost assigned EgorBo Apr 8, 2023

EgorBo mentioned this pull request Apr 8, 2023

Fold PathString aspnet pattern #84525

Open

MihuBot mentioned this pull request Apr 8, 2023

[EgorBo] Improve SequenceEqual for constant lengths unrolling MihuBot/runtime-utils#31

Open

xtqqczze reviewed Apr 8, 2023

View reviewed changes

Improve SeqEquals shape

3cfb576

EgorBo force-pushed the improve-seq-equals branch from 8d89753 to 3cfb576 Compare April 9, 2023 23:42

xtqqczze mentioned this pull request Apr 10, 2023

Unnecessary sign-extension for (nuint)span.Length #84564

Closed

stephentoub approved these changes Apr 17, 2023

View reviewed changes

stephentoub merged commit 7dbf6a5 into dotnet:main Apr 17, 2023

ghost locked as resolved and limited conversation to collaborators May 17, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Improve SequenceEqual for constant lengths unrolling#84524

Improve SequenceEqual for constant lengths unrolling#84524
stephentoub merged 1 commit intodotnet:mainfrom
EgorBo:improve-seq-equals

EgorBo commented Apr 8, 2023

Uh oh!

ghost commented Apr 8, 2023

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

xtqqczze commented Apr 8, 2023 •

edited

Loading

Uh oh!

EgorBo commented Apr 9, 2023 •

edited

Loading

Uh oh!

EgorBo commented Apr 14, 2023

Uh oh!

stephentoub commented Apr 14, 2023

Uh oh!

EgorBo commented Apr 17, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Conversation

EgorBo commented Apr 8, 2023

Uh oh!

ghost commented Apr 8, 2023

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

xtqqczze commented Apr 8, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

EgorBo commented Apr 9, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

EgorBo commented Apr 14, 2023

Uh oh!

stephentoub commented Apr 14, 2023

Uh oh!

EgorBo commented Apr 17, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

xtqqczze commented Apr 8, 2023 •

edited

Loading

EgorBo commented Apr 9, 2023 •

edited

Loading