Remove LINQ usage from the generated code

[kasperk81]

To make the generated code performant and amenable to AOT compilation and linker trimming, usage of LINQ should be removed. .NET JIT (which AOT also uses at its build-time backend) gives up while devirtualizing complex queries as it has to account for all possible types of generic from the implementation of LINQ APIs. Replacing LINQ queries with regular loops and conditions outperforms in terms of both time and space in most cases.

background microsoft/kiota-serialization-form-dotnet#142

[baywet]

@kasperk81 I believe you've submitted pull requests across repositories and everything has been merged.
This would mean we can close this issue. Can you confirm please?

[kasperk81]

this is tracking removal of LINQ from the generated code in this repo

kiota/src/Kiota.Builder/Refiners/CSharpRefiner.cs

Lines 173 to 174 in c48c7f5

	new (static x => x is CodeClass @class && @class.IsOfKind(CodeClassKind.Model, CodeClassKind.RequestBuilder),
	"System.Linq", "Enumerable"),

[baywet]

Thanks for clarifying!

[andrueastman]

@baywet You can also checkout #4725 for more background

[baywet]

This thread provides a lot of additional context to why we'd want to do this dotnet/runtime#102131

[baywet]

The usage of Linq is limited to a couple of ToList and ToArray calls.

kiota/src/Kiota.Builder/Writers/CSharp/CodeMethodWriter.cs

Line 353 in 2bb3e51

var collectionMethod = propType.IsArray ? "?.ToArray()" : "?.ToList()";

kiota/src/Kiota.Builder/Writers/CSharp/CodeMethodWriter.cs

Line 410 in 2bb3e51

writer.WriteLine("return collectionResult?.ToList();");

I wonder whether replacing those by loops is actually going to reduce the binary size.

[kasperk81]

removing linq has improved the binary size in other places. it's the way ilcompiler and ryujit compile the types in memory. the generic nature of linq is the very antipattern ilc and illink advise against. why keeping linq deemed necessary? it's not even maintained by the BCL team..

[baywet]

to be clear, I'm not arguing against the change. I'm trying to ensure we won't negatively impact size by making changes, whichever solution we land on.
The alternative to generating loops would be to have generic array/list conversion methods in abstractions and use those instead. But at this point I'm not 100% sure it'd result in a size reduction.

[kasperk81]

we have made several changes in other repos:
((IEnumerable<T>)e).ToList() -> new List<T>(e)
((IEnumerable<T>)e).ToArray() -> new List<T>(e).ToArray()

depending on how "open" the generic T is, it will improve the codegen proportionally. if T was constrained, then we get the same codegen. either way it gives a clear message that there is no usage of linq in the generated code for accidental misuses in the future.

[baywet]

Right, I had forgotten about the copy constructor.
I think the ToList replacement is a no-brainer, we're not going to get any additional allocation/cycles with this replacement.
For the ToArray, we're probably going to iterate over the "collection" twice, and assign a list to discard it right away. Not a big deal, but has a cost. Is there any better alternative for this scenario?

[kasperk81]

we can avoid two copies by iterating and short-circuiting like this:

    public T[] ToArrayWithoutLinq(IEnumerable<T> e)
    {
        if (e is ICollection<T> collection)
        {
            // Allocate an array with the exact size
            T[] result = GC.AllocateUninitializedArray<T>(collection.Count);
            collection.CopyTo(result, 0);
            return result;
        }
        else
        {
            // First pass to count the elements
            int count = 0;
            foreach (var item in e) count++;

            // Allocate array with the counted size
            T[] result = GC.AllocateUninitializedArray<T>(count);

            // Second pass to copy the elements
            int index = 0;
            foreach (var item in e) result[index++] = item;

            return result;
        }
    }

[baywet]

Thanks for the additional context. And no matter what we'll need to iterate twice so we can count the "collection" to allocate the array and avoid re-allocations. (I doubt we have any scenario where we return ICollection today).
Having this method might save the allocation of one list, but won't save the double iteration.
Alight, let's use the first suggestion you proposed as a stop-gap, and iterate over that if we get feedback about memory pressure.

[kasperk81]

won't save the double iteration.

neither does LINQ. and it comes with additional baggage for open generics.

[baywet]

Now that we have a clear roadmap, would you be open to create a pull request to make the changes we've identified?

[kasperk81]

I doubt we have any scenario where we return ICollection today

IList<T> implements ICollection<T> and apparently list is commonly used

[baywet]

Right, but the places where we call to array are from an ienumerable. And those are generally a yield return under the covers.