-
Notifications
You must be signed in to change notification settings - Fork 4k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Implement optimizations for constructing collections from collection literals #68785
Comments
An additional optimization is that we should use https://learn.microsoft.com/en-us/dotnet/api/system.runtime.interopservices.immutablecollectionsmarshal.asimmutablearray?view=net-8.0 (when present) for immutable arrays. |
@cston The intent here is for all of this to be present in C# 12, correct? This is a core part of the collection-expr story, so i want to make sure it's making the v1 release :) |
Whoops. Reading is fundamental. |
For |
Added the items from the comments above to the list in the issue description. |
AddRange for List should also be specialcased to this Span extension method. |
#69355 offers ad-hoc solution only for arrays instead of generic approach. For instance, compiler might check whether the target type |
@sakno as I mentioned in the lang chat, our pattern allows the type itself to decide what to return. So types can choose to return a .Empty Singleton if they so choose. |
I was thinking about this a bit and thought his was likely discussed elsewhere but I wanted to mention it:
|
We do doc '1'. The overall design also gives the compiler broad leeway to make assumptions and optimize, including in ways that can be observable. There is a general presumption though of good behavior (in line with the same assumptions and optimizations we do in last patterns). For example, presuming that is you enumerate an empty collection that that will not mutate state anywhere and that you will get no elements returned from the enumeration. '2' naturally falls out as we defer to the type to determine what value to return. Types with an Empty in the BCL are doing this already. Types where it is safe to use an empty Singleton will all work this way. Types where it would not be safe (like |
(Examples are decompiling code generated by SDK 8.0.0-preview.7.23375.6, with varying return types and a method body of Could // Emitted by SDK 8.0.0-preview.7.23375.6 and decompiled
private object?[] Example(IEnumerable<object?> enumerable)
{
List<object> objectList = new List<object>();
foreach (object obj in enumerable)
objectList.Add(obj);
return objectList.ToArray();
} Could // Emitted by SDK 8.0.0-preview.7.23375.6 and decompiled
private ImmutableArray<object?> Example(IEnumerable<object?> enumerable)
{
List<object> objectList = new List<object>();
foreach (object obj in enumerable)
objectList.Add(obj);
return ImmutableArray.Create<object>(new ReadOnlySpan<object>(objectList.ToArray()));
} |
Could there be value in calling |
This one may be worth doing for 17.8. I will begin working on it and we'll see if it lands in 17.8 or 17.9. |
Thank you @RikkiGibson ! |
Would it make sense to synthesize a single-element type for |
Yes it would. |
Leaving this weird case here that I've found, in case it useful. Not sure if this is by design 🤔 using System;
static int[] Fast(ReadOnlySpan<int> array)
{
return [0, 1, ..array, 3, 4];
}
static int[] Slow(ReadOnlySpan<int> array)
{
return [0, 1, 2, ..array, 3, 4];
}
Is there some hidden threshold here when you fall off this performance cliff? Should there be (as in, is this expected)? And if so, how can users know when they're going past it, to ensure they don't accidentally introduce performance regressions? |
Additionally, for cases like those, or also this one: static int[] Test(ReadOnlySpan<int> array)
{
return [0, .. array, 1, .. array];
} Ie. when the source is either a span, or something that implements |
Yes. We have approved being allowed to call copyto |
There currently is. But, @cston we really need to rethink it. The threshold is far too small. We need to up it to a much better sweet spot. |
Hey y'all, is there a definitive list of what optimizations have landed for C# 12 and what is on to todo list, or is this issue that list? I can't tell if all of the optimizations made it in time for the GA. |
@slang25 this issue is that list. The items that have made it have check marks on them |
This comment was marked as resolved.
This comment was marked as resolved.
Linq is explicitly defined as just a syntactic transformation. We would need to change the specification to allow the compiler to behave differently. Collection expressions are not done in the same fashion. They're explicitlynot defined to l as syntactic transformations. Instead, the semantics are defined and it is explicitly called out that a compliant implementation is free to emit whatever it wants as long as those semantics are preserved. If you would like linq to be changed, is recommend a new discussion on that topic. Thanks! |
Currently (.NET 8), the following code public static char[] Concat(ReadOnlySpan<char> span1, ReadOnlySpan<char> span2)
=> [..span1, ..span2]; produces public static char[] Concat(ReadOnlySpan<char> span1, ReadOnlySpan<char> span2)
{
ReadOnlySpan<char> readOnlySpan = span1;
ReadOnlySpan<char> readOnlySpan2 = span2;
int num = 0;
char[] array = new char[readOnlySpan.Length + readOnlySpan2.Length];
ReadOnlySpan<char>.Enumerator enumerator = readOnlySpan.GetEnumerator();
while (enumerator.MoveNext())
{
char c = (array[num] = enumerator.Current);
num++;
}
enumerator = readOnlySpan2.GetEnumerator();
while (enumerator.MoveNext())
{
char c = (array[num] = enumerator.Current);
num++;
}
return array;
} The quality of codegen is poor. It cannot be considered as optimal. Why simple concatenation of twos spans cannot be done using |
Concatenation of spans (or anything for that matter) can be done with .CopyTo. And this was explicitly approved by the LDM. @RikkiGibson for visibility on this (unless you're already working on this).
Compiler strategy is an internal implementation detail.
There are a near infinite number of things that can be optimized in the real world. Any particular optimization that is lacking is a non-starter for some customer. As such, if production-ready doesn't mean "sufficient for all customers", it means sufficient for the vast majority. |
When using the combination of On the other hand, when writing to a As the This optimization only seems applicable when the number of elements is a compile-time constant. |
Thanks for the info @jnyrup. Tagging @RikkiGibson and @stephentoub |
It would be nice also to support the following use case: List<object> list = [1, "a", .. items ?? [], "z"];
// ^---^ and skip handling (adding) |
Is using |
No. Using |
I created a proof of concept for this, which likely needs to be redone per the TODO comment: main...jnm2:optimize_foreach_coalesce_empty @333fred raised a concern that skipping Also, he would want to see benchmarks before replacing Is it worth starting a new thread to discuss this? |
@jnm2 What is the defined behavior in .net 1.1 ArrayList items = new ArrayList();
foreach(object item in items) //is the Enumerator required by definition?
{
} |
@RikkiGibson thx, for the link.
|
@Zetanova That would not be as low-overhead as surrounding with an |
@jnm2 simply doing nothing is the best option. the upcoming ´union types´ would resolve the issue. |
I would urge us to still skip creating and enumerating an empty collection in SomeCustomCollection x = [a, .. condition ? [b] : []]; (This may not ship in 13, but hopefully soon. In the meantime, you can write If we can skip creating a non-empty transient collection there as well as an empty one, I would absolutely expect the same here (and we've even touched on this in design discussions): SomeCustomCollection x = [a, .. items ?? []]; Now we're already quite parallel to |
@jnm2 Interesting is that the lowering of |
@Zetanova Same for arrays. Underneath the compiler expansions which showcase the use of enumerators, it says:
|
@jnm2 when the foreach expression has the form For ValueTypes the this optimization should not apply. but this example would break: sharplab An other option is to go the static default why like this: sharplab Don't really see a clean why without an extension. |
@jnm2 I found a partial optimization to get rid of the heap-alloc. Demo: sharplap |
Implement various optimizations for constructing collections from collection literals, including:
Use inline array for the collection builder method
ReadOnlySpan<T>
argument when the span cannot escape. #69227Use inline arrays for collection expressions with span target types #69412
Use existing optimization for
ReadOnlySpan<T>
to blit data into the assembly section when values are constants of primitive type. #69412Emit
[]
asArray.Empty<T>()
when the target type isIEnumerable<T>
orT[]
. #69355Emit
[]
asdefault(Span<T>)
when the target type isSpan<T>
. #70260Avoid intermediate
List<T>
if all spread elements are countable and collection satisfies certain heuristics. #69875Use
EnsureCapacity(int)
for collection initializer types with no spreads; potentially also when length is known and collection satisfies certain heuristics.Use
CollectionsMarshal.SetCount<T>(List<T>, int)
andCollectionsMarshal.AsSpan<T>(List<T>)
to create aList<T>
when length is known and collection satisfies certain heuristics; fallback toList<T>..ctor(int capacity)
ifCollectionsMarshal
is not available. #70197Use
ImmutableCollectionsMarshal.AsImmutableArray<T>(T[])
to create anImmutableArray<T>
. #70222Use
.ctor(int capacity)
for some BCL types whenEnsureCapacity(int)
is not available, or not available downlevel.Emit
Enumerable.TryGetNonEnumeratedCount()
and avoid intermediateList<T>
at runtime. Poor codegen for collection expression spread (IEnumerable<T> -> ImmutableArray<T>) #71296Use
List<T>.AddRange(IEnumerable<T>)
when adding a spread to aList<T>
if the spread implementsICollection<T>
, or if the spread implementsIEnumerable<T>
and does not have astruct
enumerator; useCollectionExtensions.AddRange<T>(List<T>, ReadOnlySpan<T>)
if the spread is a span; otherwise useforeach
andList<T>.Add(T)
.Use
CollectionsMarshal.AsSpan<T>(List<T>)
to create aReadOnlySpan<T>
from the temporaryList<T>
when creating a[CollectionBuilder]
collection from a collection literal of unknown length.emit
foreach (var x in y ?? [])
as a lifted null check that executes nothing if 'y' is null.When producing an
IEnumerable<T>
use the same codegen pattern thatyield
does. Specifically, where the instance created is both anIEnumerable<T>
and its ownIEnumerator<T>
for the very first iteration of the enumerable on the same thread. This avoids an extra allocation for hte common case of producing anIEnumerable<T>
just to have it be immediately iterated.Avoid heap allocation for spread in(moved to #69277)[.. x ? [y] : []]
.Avoid heap allocation for collection in(moved to #69277)foreach (bool x in [true, false])
.Relates to test plan #66418
The text was updated successfully, but these errors were encountered: