Compiler's SelectMany selection strategy

[louthy]

In a LINQ expression like this:

var things = from _ in Enumerable.Range(1, 10)
             from y in Enumerable.Range(1, 10)
             select y;

The code that gets generated looks a little like this:

Enumerable
    .Range(1, 10)
    .SelectMany(_ => Enumerable.Range(1, 10), (_, y) => y);

The second lambda in SelectMany is unnecessary when there's a SelectMany(M<A>, Func<A, M<B>>) available (where M is the type that has a SelectMany implementation, like IEnumerable).

If you look at the generated IL for the second lambda, all it does is return the second argument:

  .method assembly hidebysig 
    instance int32 '<<Main>$>b__0_1' (
      int32 x,
      int32 y
    ) cil managed 
  {
    // Method begins at RVA 0x9888
    // Header size: 1
    // Code size: 2 (0x2)
    .maxstack 8

    // return y;
    IL_0000: ldarg.2
    IL_0001: ret
  } // end of method '<>c'::'<<Main>$>b__0_1'

The generated code could easily be:

Enumerable
    .Range(1, 10)
    .SelectMany(_ => Enumerable.Range(1, 10));

Because there's no additional processing after the final from clause, the projection function is simply an identity mapping. However an additional allocation is still needed (for the Func) and about 10 extra lines of IL are needed to invoke it (when it does nothing).

I always understood that the compiler would pick the best SelectMany implementation if we provided them.

So, either:

• My understanding is wrong
• This is a bug in the compiler, it should be picking the simpler SelectMany
• There's something I need to do to 'encourage' the compiler to use the correct SelectMany that I am not doing.

It would seem to me to be a relatively trivial optimisation and would reduce the allocation overhead of a common pattern in LINQ (and be more CPU efficient).

I wonder, does anyone have any insight in to this?

One final thing on this (and the real reason I am asking). I am adding Transducers to my language-ext project; they are going to be the system that backs all of the monadic types, like Try<A>, Eff<A>, Option<A>, Reader<E, A>, etc.

I have found a way to make transducers support infinite recursion without blowing the stack. Below is an example of an infinite recursive loop.

static Transducer<Unit, Unit> loop(int x) =>
    from _ in show(x)
    from r in loop(x + 1)
    select r;

Except because of the picking of SelectMany(M<A>, Func<A, M<B>>, Func<A, B, C>) rather than SelectMany(M<A>, Func<A, M<B>>) it ends up with a space leak.

If I write the code above as:

static Transducer<Unit, Unit> loop(int x) =>
    show(x)
        .SelectMany(_ => loop(x + 1));

Then I get infinite recursion without the space leak, which is pretty massive for a functional programming technique in C#.

I am about to start looking at building a Fody plugin to try and solve this, but really it would be great if the compiler didn't do work it didn't need to do and in the process cause me a space leak! ;)

[RikkiGibson]

The compiler doesn't make any attempt to decide if a lambda is trivial enough to be replaced by something else, e.g. replacing Id(a) with a, and it doesn't generally assume that one overload of a method is substitutable for another.

[333fred]

Specifically, query syntax is defined as a pure syntactic transformation: https://github.com/dotnet/csharpstandard/blob/draft-v7/standard/expressions.md#11183-query-expression-translation. There is no attempt to understand the original query syntax and produce an efficient translation; it is simply bound as if the user had written the equivalent methods.

[Joe4evr]

ReasonsWhyQuerySyntaxIsInferior++; 🙃

[DavidArno]

ReasonsWhyQuerySyntaxIsInferior++; 🙃

PossiblePrematureOptimizationDetected = true 😛