Collection expressions: optimize List<T> construction by cston · Pull Request #70197 · dotnet/roslyn

cston · 2023-09-30T06:59:30Z

When constructing a List<T> instance when the collection length is known and the collection satisfies certain heuristics:

Use CollectionsMarshal.SetCount<T>(List<T>, int) and CollectionsMarshal.AsSpan<T>(List<T>) if available
Fall back to List<T>..ctor(int capacity) if CollectionsMarshal is not available.

Initial commits are from #69875.

Relates to test plan #66418

… have known length

…ngth

CyrusNajmabadi · 2023-09-30T07:18:23Z

src/Compilers/CSharp/Portable/Lowering/LocalRewriter/LocalRewriter_CollectionExpression.cs

+            // while also allowing using the known length for common cases. In particular, this allows
+            // using the known length for simple concatenation of two elements [e, ..y] or [..x, ..y].
+            // Temporaries are only needed up to the last spread, so this also allows [..x, e1, e2, ...].
+            const int maxTemporaries = 3;


cston · 2023-09-30T21:06:11Z

src/Compilers/CSharp/Portable/Lowering/LocalRewriter/LocalRewriter_CollectionExpression.cs

+                                indexTemp,
+                                _factory.Binary(BinaryOperatorKind.Addition, indexTemp.Type, indexTemp, _factory.Literal(1)),
+                                isRef: false,
+                                indexTemp.Type));


Before the first spread element, the compiler should emit constants indices rather than using an index variable.

jcouv · 2023-10-04T20:48:12Z

src/Compilers/Core/Portable/WellKnownMembers.cs

                    (byte)SignatureTypeCode.TypeHandle, (byte)SpecialType.System_Int32,

+                // System_Collections_Generic_List_T__ctor
+                (byte)MemberFlags.Constructor,                                                                                               // Flags


nit: the indent on comments below is messed up

RikkiGibson · 2023-10-04T20:49:21Z

Here are the commits introduced after #69875: https://github.com/dotnet/roslyn/pull/70197/files/2f4cd81c92dfe4a6bb58ed4bcd011ba6f64e4589..acaacd8483cbe34ee6d6f880f6d1c62eb257c3b3

@333fred and I should be able to sign off on this PR just by reviewing those 3 commits.

jcouv · 2023-10-04T20:51:52Z

src/Compilers/CSharp/Portable/Binder/Semantics/Conversions/ConversionsBase.cs

+                return includesIEnumerable(compilation, interfaces);
+            }
+
+            static bool includesIEnumerable(CSharpCompilation compilation, ImmutableArray<NamedTypeSymbol> allInterfaces)


This refactoring (extracting a local function) doesn't seem particularly useful... #Closed

The refactoring occurred before extracting GetAllInterfacesOrEffectiveInterfaces(). Merged.

RikkiGibson · 2023-10-04T20:54:36Z

src/Compilers/CSharp/Portable/Binder/Binder_Conversions.cs

                    _ = GetWellKnownTypeMember(WellKnownMember.System_Collections_Generic_List_T__ctorInt32, diagnostics, syntax: syntax);
-                    _ = GetWellKnownTypeMember(WellKnownMember.System_Collections_Generic_List_T__ToArray, diagnostics, syntax: syntax);
+
+                    if (collectionTypeKind is CollectionExpressionTypeKind.List)


I didn't understand why we need Add but not ToArray when targeting to List and ToArray but not Add when targeting to list interface. #Resolved

For list interface, we may use List<T>.Add. Updated.

jcouv · 2023-10-04T21:02:24Z

src/Compilers/CSharp/Portable/Lowering/LocalRewriter/LocalRewriter_CollectionExpression.cs

+                localsBuilder,
+                numberIncludingLastSpread,
+                sideEffects,
+                (ArrayBuilder<BoundExpression> expressions, BoundExpression arrayTemp, BoundExpression rewrittenValue) =>


nit: On the other hand, the refactoring here (inlining of the local function) seems negative to me as it makes the main body of the method harder to follow (much logic inside the lambda now). Consider keeping original structure.
I'd probably also use a local function for the other call to AddCollectionExpressionElements below (line 592) #Closed

Will keep as is, since there are three separate callers of AddCollectionExpressionElements() that each pass a lambda expression with inline method.

jcouv · 2023-10-04T21:09:10Z

src/Compilers/CSharp/Portable/Lowering/LocalRewriter/LocalRewriter_CollectionExpression.cs

+            // Do not use optimizations in async method since the optimizations require Span<T>.
+            if (useKnownLength && elements.Length > 0 && _factory.CurrentFunction?.IsAsync == false)
+            {
+                setCount = ((MethodSymbol?)_compilation.GetWellKnownTypeMember(WellKnownMember.System_Runtime_InteropServices_CollectionsMarshal__SetCount_T))?.Construct(typeArguments);


In a custom BCL scenario, we'd want to check constraints. I'm okay to leave as-is as long as this was an explicit choice. It feels like the team has been more comfortable making assumptions about the well-known BCL APIs recently...

Also obsolete

333fred · 2023-10-04T21:16:29Z

It looks like @RikkiGibson and @jcouv are looking at this one, so I'll look at a different PR.

jcouv · 2023-10-04T21:40:57Z

src/Compilers/CSharp/Portable/Lowering/LocalRewriter/LocalRewriter_CollectionExpression.cs

+            MethodSymbol? asSpan = null;
+
+            // Do not use optimizations in async method since the optimizations require Span<T>.
+            if (useKnownLength && elements.Length > 0 && _factory.CurrentFunction?.IsAsync == false)


elements.Length > 0

Do we have a test for this condition (empty collection)?
Same question for useKnownLength. I assume that's covered, but couldn't easily spot the test for that #Resolved

ListConstruction_02 includes a test for the empty collection. We had several existing tests that hit the unknown length but added an explicit test: ListConstruction_03.

jcouv

Done with review pass (iteration 15). Only reviewed from commit 12. Minor comments/questions only

MIsc.

jcouv

LGTM Thanks (iterations 12 to 16)

jjonescz

LGTM (commits 13-16)

jjonescz · 2023-10-05T12:45:12Z

src/Compilers/CSharp/Portable/Lowering/LocalRewriter/LocalRewriter_CollectionExpression.cs

+
+        private BoundExpression GetKnownLengthExpression(ImmutableArray<BoundExpression> elements, int numberIncludingLastSpread, ArrayBuilder<BoundLocal> rewrittenExpressions)
+        {
+            Debug.Assert(rewrittenExpressions.Count >= numberIncludingLastSpread);


nit: consider adding a comment why rewrittenExpressions can have more items

cston added 13 commits September 11, 2023 15:19

Collection expressions: avoid intermediate List<T> if spread elements…

fa59b04

… have known length

Merge remote-tracking branch 'upstream/main' into known-length

e2cf69b

Updates following merge

904e3d4

Fix formatting

e0a0737

Address feedback

696f50d

Merge remote-tracking branch 'upstream/main' into known-length

039a0c1

Construct internal List<T> instances using well-known members

c2f78db

Limit number of temporaries

df3c63f

Merge remote-tracking branch 'upstream/release/dev17.8' into known-le…

dee3f44

…ngth

Fix attribute test

9815dd4

Test struct Length property with side effects

4590e93

Address feedback

2f4cd81

Use List<T>..ctor(int capacity) when no spread elements

2564a6f

ghost added Area-Compilers untriaged Issues and PRs which have not yet been triaged by a lead labels Sep 30, 2023

cston added the Feature - Collection Expressions label Sep 30, 2023

CyrusNajmabadi reviewed Sep 30, 2023

View reviewed changes

cston force-pushed the list-construct branch 3 times, most recently from 7a673c6 to d2928db Compare September 30, 2023 20:42

cston mentioned this pull request Sep 30, 2023

Implement optimizations for constructing collections from collection literals #68785

Open

17 tasks

Collection expressions: optimize List<T> construction

7dbca2a

cston force-pushed the list-construct branch from d2928db to 7dbca2a Compare September 30, 2023 20:50

cston commented Sep 30, 2023

View reviewed changes

cston marked this pull request as ready for review September 30, 2023 22:29

cston requested a review from a team as a code owner September 30, 2023 22:29

This was referenced Oct 2, 2023

Collection expressions: avoid intermediate List<T> if spread elements have known length #69875

Closed

Collection expressions: use applicable EnsureCapacity() when length is known #70181

Draft

RikkiGibson mentioned this pull request Oct 3, 2023

Collection expressions: ImmutableArray optimization #70222

Merged

Add GetAllInterfacesOrEffectiveInterfaces

acaacd8

cston mentioned this pull request Oct 4, 2023

Collection expressions: update rules for conversion to IEnumerable collection #69956

Merged

jaredpar assigned 333fred and jcouv Oct 4, 2023

jcouv reviewed Oct 4, 2023

View reviewed changes

RikkiGibson reviewed Oct 4, 2023

View reviewed changes

jcouv reviewed Oct 4, 2023

View reviewed changes

333fred assigned RikkiGibson and unassigned 333fred Oct 4, 2023

jcouv reviewed Oct 4, 2023

View reviewed changes

cston mentioned this pull request Oct 4, 2023

Collection expressions: analyze nullability of element assignments #70192

Merged

Address feedback

0ce08c6

MIsc.

jcouv approved these changes Oct 4, 2023

View reviewed changes

jcouv requested a review from RikkiGibson October 5, 2023 00:00

jjonescz approved these changes Oct 5, 2023

View reviewed changes

cston changed the base branch from release/dev17.8 to features/CollectionLiterals October 5, 2023 16:49

cston merged commit b04edcf into dotnet:features/CollectionLiterals Oct 5, 2023

Conversation

cston commented Sep 30, 2023 • edited by jcouv Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

CyrusNajmabadi Sep 30, 2023

Choose a reason for hiding this comment

Uh oh!

cston Sep 30, 2023

Choose a reason for hiding this comment

Uh oh!

jcouv Oct 4, 2023

Choose a reason for hiding this comment

Uh oh!

RikkiGibson commented Oct 4, 2023

Uh oh!

jcouv Oct 4, 2023 • 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!

cston Oct 4, 2023

Choose a reason for hiding this comment

Uh oh!

RikkiGibson Oct 4, 2023 • edited by cston Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

cston Oct 4, 2023 • 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!

jcouv Oct 4, 2023 • 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!

cston Oct 4, 2023

Choose a reason for hiding this comment

Uh oh!

jcouv Oct 4, 2023 • 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!

333fred commented Oct 4, 2023

Uh oh!

jcouv Oct 4, 2023 • edited by cston Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

cston Oct 4, 2023

Choose a reason for hiding this comment

Uh oh!

jcouv left a comment

Choose a reason for hiding this comment

Uh oh!

jcouv left a comment

Choose a reason for hiding this comment

Uh oh!

jjonescz left a comment

Choose a reason for hiding this comment

Uh oh!

jjonescz Oct 5, 2023

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

cston commented Sep 30, 2023 •

edited by jcouv

Loading

jcouv Oct 4, 2023 •

edited

Loading

RikkiGibson Oct 4, 2023 •

edited by cston

Loading

cston Oct 4, 2023 •

edited

Loading

jcouv Oct 4, 2023 •

edited

Loading

jcouv Oct 4, 2023 •

edited

Loading

jcouv Oct 4, 2023 •

edited by cston

Loading