Add internal Array.Clear(Array), optimize some Array callers + codegen #51548

GrabYourPitchforks · 2021-04-20T05:47:15Z

Optimized some calls to Array.Clear, including adding an internal non-generic Array.Clear(Array) method for common use cases, plus redirecting some existing calls to Array.Clear or Span<T>.Clear (see #51534) or Span<T>.Fill.

This is marked as draft because I'm soliciting feedback on whether to pursue this. It introduces some complexity to the RawArrayData and RawData types (using FieldOffset) in order to knock down the codegen. Whether complicating the C# definitions of these types in order to save some bytes of codegen is worth it I'll leave up to smarter people. :)

The codegen for Array.Clear(Array) is pretty well optimized now:

00007ffa`321721a0 4883ec28             sub     rsp, 28h
00007ffa`321721a4 4885c9               test    rcx, rcx  ; arr != null check
00007ffa`321721a7 745d                 je      System_Private_CoreLib!System.Array.Clear(System.Array)+0xffffffff`a0fc77c6 (00007ffa`32172206)
00007ffa`321721a9 488b11               mov     rdx, qword ptr [rcx]  ; rdx := pMethodTable
00007ffa`321721ac 4c8bc2               mov     r8, rdx
00007ffa`321721af 410fb700             movzx   eax, word ptr [r8]  ; rax := MethodTable::ComponentSize
00007ffa`321721b3 480faf4108           imul    rax, qword ptr [rcx+8]  ; rax := TotalByteLength (ComponentSize * NumElements)
00007ffa`321721b8 8b5204               mov     edx, dword ptr [rdx+4]  ; rdx := MethodTable::BaseSize
00007ffa`321721bb 4883c108             add     rcx, 8  ; ideally would be rolled into line immediately below, but eh, whatever
00007ffa`321721bf 488d4c11f0           lea     rcx, [rcx+rdx-10h]  ; rcx := &Array.FirstElement
00007ffa`321721c4 41f70000000001       test    dword ptr [r8], 1000000h  ; <does the method table contain gc-tracked types?>
; <snip>

jit-diff output for CoreLib below. Not sure what's going on with some methods being deleted + reintroduced. Maybe something weird in my build environment? Codegen for methods which now call Array.Clear(Array) instead of Array.Clear(Array, int, int) is smaller, as expected. Methods like Array.Copy which now rely on the internal NativeLength property instead of LongLength also saw codegen reductions.

Top method regressions (bytes):
         260 (     ∞ of base) : System.Private.CoreLib.dasm - Array:<Sort>g__GenericSort|128_0(Array,Array,int,int) (0 base, 1 diff methods)
         151 (     ∞ of base) : System.Private.CoreLib.dasm - Array:<BinarySearch>g__GenericBinarySearch|82_0(Array,int,int,Object):int (0 base, 1 diff methods)
         151 (     ∞ of base) : System.Private.CoreLib.dasm - Array:<IndexOf>g__GenericIndexOf|107_0(Array,Object,int,int):int (0 base, 1 diff methods)
         151 (     ∞ of base) : System.Private.CoreLib.dasm - Array:<LastIndexOf>g__GenericLastIndexOf|113_0(Array,Object,int,int):int (0 base, 1 diff methods)
         120 (     ∞ of base) : System.Private.CoreLib.dasm - SpanHelpers:ClearWithReferences(byref,long) (0 base, 1 diff methods)
         117 (     ∞ of base) : System.Private.CoreLib.dasm - Array:Clear(Array) (0 base, 1 diff methods)
           5 (     ∞ of base) : System.Private.CoreLib.dasm - Array:get_NativeLength():long:this (0 base, 1 diff methods)
           1 (25.00% of base) : System.Private.CoreLib.dasm - Array:get_LongLength():long:this

Top method improvements (bytes):
        -260 (-100.00% of base) : System.Private.CoreLib.dasm - Array:<Sort>g__GenericSort|125_0(Array,Array,int,int) (1 base, 0 diff methods)
        -151 (-100.00% of base) : System.Private.CoreLib.dasm - Array:<BinarySearch>g__GenericBinarySearch|79_0(Array,int,int,Object):int (1 base, 0 diff methods)
        -151 (-100.00% of base) : System.Private.CoreLib.dasm - Array:<IndexOf>g__GenericIndexOf|104_0(Array,Object,int,int):int (1 base, 0 diff methods)
        -151 (-100.00% of base) : System.Private.CoreLib.dasm - Array:<LastIndexOf>g__GenericLastIndexOf|110_0(Array,Object,int,int):int (1 base, 0 diff methods)
         -62 (-29.81% of base) : System.Private.CoreLib.dasm - String:Ctor(ushort,int):String:this
         -22 (-2.41% of base) : System.Private.CoreLib.dasm - TlsOverPerCoreLockedStacksArrayPool`1:Return(ref,bool):this
         -13 (-6.02% of base) : System.Private.CoreLib.dasm - Array:Copy(Array,int,Array,int,int)
         -10 (-1.34% of base) : System.Private.CoreLib.dasm - Buffer:BlockCopy(Array,int,Array,int,int)
          -9 (-1.01% of base) : System.Private.CoreLib.dasm - Array:Copy(Array,int,Array,int,int,bool)
          -6 (-2.70% of base) : System.Private.CoreLib.dasm - Array:Clear(Array,int,int)
          -6 (-0.59% of base) : System.Private.CoreLib.dasm - TlsOverPerCoreLockedStacksArrayPool`1:Trim():bool:this
          -5 (-1.62% of base) : System.Private.CoreLib.dasm - ConfigurableArrayPool`1:Return(ref,bool):this
          -4 (-1.71% of base) : System.Private.CoreLib.dasm - Array:Copy(Array,Array,int)
          -2 (-1.72% of base) : System.Private.CoreLib.dasm - Array:UnsafeArrayAsSpan(Array,int,int):Span`1
          -2 (-1.13% of base) : System.Private.CoreLib.dasm - Buffer:ByteLength(Array):int
          -2 (-2.99% of base) : System.Private.CoreLib.dasm - Buffer:GetByte(Array,int):ubyte
          -2 (-2.82% of base) : System.Private.CoreLib.dasm - Buffer:SetByte(Array,int,ubyte)

ghost · 2021-04-20T05:47:23Z

Tagging subscribers to this area: @tannergooding
See info in area-owners.md if you want to be subscribed.

Issue Details

Optimized some calls to Array.Clear, including adding an internal non-generic Array.Clear(Array) method for common use cases, plus redirecting some existing calls to Array.Clear or Span<T>.Clear (see #51534) or Span<T>.Fill.

This is marked as draft because I'm soliciting feedback on whether to pursue this. It introduces some complexity to the RawArrayData and RawData types (using FieldOffset) in order to knock down the codegen. Whether complicating the C# definitions of these types in order to save some bytes of codegen is worth it I'll leave up to smarter people. :)

The codegen for Array.Clear(Array) is pretty well optimized now:

00007ffa`321721a0 4883ec28             sub     rsp, 28h
00007ffa`321721a4 4885c9               test    rcx, rcx  ; arr != null check
00007ffa`321721a7 745d                 je      System_Private_CoreLib!System.Array.Clear(System.Array)+0xffffffff`a0fc77c6 (00007ffa`32172206)
00007ffa`321721a9 488b11               mov     rdx, qword ptr [rcx]  ; rdx := pMethodTable
00007ffa`321721ac 4c8bc2               mov     r8, rdx
00007ffa`321721af 410fb700             movzx   eax, word ptr [r8]  ; rax := MethodTable::ComponentSize
00007ffa`321721b3 480faf4108           imul    rax, qword ptr [rcx+8]  ; rax := TotalByteLength (ComponentSize * NumElements)
00007ffa`321721b8 8b5204               mov     edx, dword ptr [rdx+4]  ; rdx := MethodTable::BaseSize
00007ffa`321721bb 4883c108             add     rcx, 8  ; ideally would be rolled into line immediately below, but eh, whatever
00007ffa`321721bf 488d4c11f0           lea     rcx, [rcx+rdx-10h]  ; rcx := &Array.FirstElement
00007ffa`321721c4 41f70000000001       test    dword ptr [r8], 1000000h  ; <does the method table contain gc-tracked types?>
; <snip>

jit-diff output for CoreLib below. Not sure what's going on with some methods being deleted + reintroduced. Maybe something weird in my build environment? Codegen for methods which now call Array.Clear(Array) instead of Array.Clear(Array, int, int) is smaller, as expected. Methods like Array.Copy which now rely on the internal NativeLength property instead of LongLength also saw codegen reductions.

Top method regressions (bytes):
         260 (     ∞ of base) : System.Private.CoreLib.dasm - Array:<Sort>g__GenericSort|128_0(Array,Array,int,int) (0 base, 1 diff methods)
         151 (     ∞ of base) : System.Private.CoreLib.dasm - Array:<BinarySearch>g__GenericBinarySearch|82_0(Array,int,int,Object):int (0 base, 1 diff methods)
         151 (     ∞ of base) : System.Private.CoreLib.dasm - Array:<IndexOf>g__GenericIndexOf|107_0(Array,Object,int,int):int (0 base, 1 diff methods)
         151 (     ∞ of base) : System.Private.CoreLib.dasm - Array:<LastIndexOf>g__GenericLastIndexOf|113_0(Array,Object,int,int):int (0 base, 1 diff methods)
         120 (     ∞ of base) : System.Private.CoreLib.dasm - SpanHelpers:ClearWithReferences(byref,long) (0 base, 1 diff methods)
         117 (     ∞ of base) : System.Private.CoreLib.dasm - Array:Clear(Array) (0 base, 1 diff methods)
           5 (     ∞ of base) : System.Private.CoreLib.dasm - Array:get_NativeLength():long:this (0 base, 1 diff methods)
           1 (25.00% of base) : System.Private.CoreLib.dasm - Array:get_LongLength():long:this

Top method improvements (bytes):
        -260 (-100.00% of base) : System.Private.CoreLib.dasm - Array:<Sort>g__GenericSort|125_0(Array,Array,int,int) (1 base, 0 diff methods)
        -151 (-100.00% of base) : System.Private.CoreLib.dasm - Array:<BinarySearch>g__GenericBinarySearch|79_0(Array,int,int,Object):int (1 base, 0 diff methods)
        -151 (-100.00% of base) : System.Private.CoreLib.dasm - Array:<IndexOf>g__GenericIndexOf|104_0(Array,Object,int,int):int (1 base, 0 diff methods)
        -151 (-100.00% of base) : System.Private.CoreLib.dasm - Array:<LastIndexOf>g__GenericLastIndexOf|110_0(Array,Object,int,int):int (1 base, 0 diff methods)
         -62 (-29.81% of base) : System.Private.CoreLib.dasm - String:Ctor(ushort,int):String:this
         -22 (-2.41% of base) : System.Private.CoreLib.dasm - TlsOverPerCoreLockedStacksArrayPool`1:Return(ref,bool):this
         -13 (-6.02% of base) : System.Private.CoreLib.dasm - Array:Copy(Array,int,Array,int,int)
         -10 (-1.34% of base) : System.Private.CoreLib.dasm - Buffer:BlockCopy(Array,int,Array,int,int)
          -9 (-1.01% of base) : System.Private.CoreLib.dasm - Array:Copy(Array,int,Array,int,int,bool)
          -6 (-2.70% of base) : System.Private.CoreLib.dasm - Array:Clear(Array,int,int)
          -6 (-0.59% of base) : System.Private.CoreLib.dasm - TlsOverPerCoreLockedStacksArrayPool`1:Trim():bool:this
          -5 (-1.62% of base) : System.Private.CoreLib.dasm - ConfigurableArrayPool`1:Return(ref,bool):this
          -4 (-1.71% of base) : System.Private.CoreLib.dasm - Array:Copy(Array,Array,int)
          -2 (-1.72% of base) : System.Private.CoreLib.dasm - Array:UnsafeArrayAsSpan(Array,int,int):Span`1
          -2 (-1.13% of base) : System.Private.CoreLib.dasm - Buffer:ByteLength(Array):int
          -2 (-2.99% of base) : System.Private.CoreLib.dasm - Buffer:GetByte(Array,int):ubyte
          -2 (-2.82% of base) : System.Private.CoreLib.dasm - Buffer:SetByte(Array,int,ubyte)

Author:	GrabYourPitchforks
Assignees:	-
Labels:	`area-System.Runtime`, `optimization`
Milestone:	6.0.0

GrabYourPitchforks · 2021-04-20T05:59:42Z

Note to reviewers - test failures suggest that there are scenarios where the padding inside the array object is non-zero. However, browsing through the sources, I can't find any examples of where this might be the case. Thoughts?

src/mono/System.Private.CoreLib/src/System/Array.Mono.cs

jkotas · 2021-04-20T06:24:04Z

...coreclr/System.Private.CoreLib/src/System/Runtime/CompilerServices/RuntimeHelpers.CoreCLR.cs

I do not see the improvement here. Is this just a micro-optimization to compensate for missing JIT optimization? I would much preffer to fix the JIT instead of this.

jkotas · 2021-04-20T06:37:26Z

test failures suggest that there are scenarios where the padding inside the array object is non-zero.

Whatever it is, I do not think we should be introducing code that depends on this padding.

jkotas · 2021-04-20T06:41:57Z

src/coreclr/System.Private.CoreLib/src/System/Array.CoreCLR.cs

I like the NativeLength property to make these casts go away.

Part of this was trying to reduce codegen and save a register allocation by having a qword comparison directly against the NativeLength field rather than first requiring zero-extension from a dword field into a qword register. Might have to give up that optimization if we can't assume the padding is all-zero, though.

I do not think it is worth it to complicate the code to save a few bytes of codegen. It is very x86/64 specific code-size micro-optimization.

We could just have NativeLength be => Unsafe.As<RawArrayData>(this).Length to force the zero-extension to nuint.

That would make it easier to switch to properly be NativeLength if we ever decide to make the switch in the future and would avoid the potential problems here while keeping things as is (not requiring more complex changes to actually track nuint in the Array metadata today).

stephentoub · 2021-04-20T10:57:19Z

src/libraries/Common/src/Interop/Unix/System.Native/Interop.ForkAndExecProcess.cs

This can't actually overflow, can it? arr.Length <= Array.MaxLength < int.MaxValue

Mono isn't bound by this same constraint. It also seems fragile to depend on the runtime never allowing this value to increase in the future.

stephentoub · 2021-04-20T10:58:40Z

src/libraries/Common/src/Interop/Unix/System.Native/Interop.ForkAndExecProcess.cs

This comment is out of date.

stephentoub · 2021-04-20T11:02:43Z

src/libraries/System.Private.DataContractSerialization/src/System/Xml/XmlBaseReader.cs

Should we open an issue to expose Array.Clear(Array) publicly?

Pulled out into #51581.

gfoidl · 2021-04-20T12:17:42Z

src/coreclr/System.Private.CoreLib/src/System/Array.CoreCLR.cs

Suggested change

if (index < lowerBound || offset < 0 || length < 0 || (uint)(offset + length) > array.NativeLength)

if (index < lowerBound || (offset | length) < 0 || (uint)(offset + length) > array.NativeLength)

Ideally the JIT could do this optimization.

Happily, already in progress! :)
#13573

jkotas · 2021-04-20T12:41:04Z

src/coreclr/System.Private.CoreLib/src/System/Array.CoreCLR.cs

It may be more convenient to just turn this into no-op if the array is null.

jkotas · 2021-04-20T12:45:21Z

src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Match.cs

What is the typical matchcount.Length? Is this going to be an improvement in typical case?

GrabYourPitchforks · 2021-04-20T19:25:29Z

Latest commit explicitly zeroes out the padding in AllocateSzArray. This is experimental and per #51548 (comment) we might be well-advised to chuck the dependency anyway.

GrabYourPitchforks · 2021-04-21T19:27:20Z

Force-push because I undid most of the work in this PR. The PR is now greatly slimmed:

Adds internal Array.Clear method
Redirects some internal calls of the old Array.Clear method to the new method
Adds unit tests verifying that IList.Clear (which previously failed for large MDArrays) now succeeds
Reverted all other changes w.r.t. spanifying other callers, assuming arrays are zero-padded, etc. This is now focused just on Array.Clear and its immediate callers.

jkotas

Thanks!

GrabYourPitchforks added area-System.Runtime optimization labels Apr 20, 2021

GrabYourPitchforks added this to the 6.0.0 milestone Apr 20, 2021

GrabYourPitchforks requested review from jkotas and tannergooding April 20, 2021 05:47

jkotas reviewed Apr 20, 2021

View reviewed changes

src/mono/System.Private.CoreLib/src/System/Array.Mono.cs Outdated Show resolved Hide resolved

jkotas reviewed Apr 20, 2021

View reviewed changes

stephentoub reviewed Apr 20, 2021

View reviewed changes

src/libraries/Common/src/Interop/Unix/System.Native/Interop.ForkAndExecProcess.cs Outdated

Copy link

Member

stephentoub Apr 20, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This comment is out of date.

stephentoub reviewed Apr 20, 2021

View reviewed changes

gfoidl reviewed Apr 20, 2021

View reviewed changes

jkotas reviewed Apr 20, 2021

View reviewed changes

This was referenced Apr 20, 2021

API proposal: Array.Clear(Array) #51581

Closed

Add internal Array.NativeLength property #51589

Merged

JIT doesn't always fold 'add' instructions into 'lea' which immediately follows it #51599

Closed

runfoapp bot mentioned this pull request Apr 21, 2021

System.Tests.GCTests.LatencyRoundtrips failing in CI #51635

Closed

Add internal Array.Clear method

9b65c32

GrabYourPitchforks force-pushed the span_calls branch from 7008bdd to 9b65c32 Compare April 21, 2021 19:24

GrabYourPitchforks marked this pull request as ready for review April 21, 2021 19:27

GrabYourPitchforks requested a review from marek-safar as a code owner April 21, 2021 19:27

jkotas approved these changes Apr 21, 2021

View reviewed changes

GrabYourPitchforks merged commit fd2e564 into dotnet:main Apr 21, 2021

GrabYourPitchforks deleted the span_calls branch April 21, 2021 22:38

ghost locked as resolved and limited conversation to collaborators May 21, 2021

	if (index < lowerBound \|\| offset < 0 \|\| length < 0 \|\| (uint)(offset + length) > array.NativeLength)
	if (index < lowerBound \|\| (offset \| length) < 0 \|\| (uint)(offset + length) > array.NativeLength)

Add internal Array.Clear(Array), optimize some Array callers + codegen #51548

Add internal Array.Clear(Array), optimize some Array callers + codegen #51548

Uh oh!

Conversation

GrabYourPitchforks commented Apr 20, 2021

Uh oh!

ghost commented Apr 20, 2021

Uh oh!

GrabYourPitchforks commented Apr 20, 2021

Uh oh!

Uh oh!

jkotas Apr 20, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jkotas commented Apr 20, 2021

Uh oh!

Choose a reason for hiding this comment

Uh oh!

GrabYourPitchforks Apr 20, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

stephentoub Apr 20, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

GrabYourPitchforks commented Apr 20, 2021

Uh oh!

GrabYourPitchforks commented Apr 21, 2021

Uh oh!

jkotas left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

jkotas Apr 20, 2021 •

edited

Loading

GrabYourPitchforks Apr 20, 2021 •

edited

Loading

stephentoub Apr 20, 2021 •

edited

Loading