Citation? I was unaware that the little IEnumerable functions did fusion. If you...

jpatte · on Feb 27, 2015

LINQ IEnumerable functions are implemented using the `yield return` operator:

  public static IEnumerable<T> Where<T>(IEnumerable<T> source, 
                                        Predicate<T> predicate)
  {
    foreach(var item in source)
    {
      if(predicate(item))
        yield return item;
    }
  }

which means

  var results = myList
    .Where(x => x.name == 'Person');
    .Where(x => x.age > 18);
    .ToList();

is executed just like

  var results = new List<Foo>();
  foreach(var x in myList)
  {
    if(x.name == 'Person')
    {
      if(x.age > 18)
        results.Add(x);
    }
  }

MichaelGG · on Feb 27, 2015

I think your "executed like" is missing another foreach loop, and the actual function calls (lambdas don't get inlined on the C# compiler, and it's a bit of a crap shoot when counting on the JIT). The end result is the same, but you're eliding a bunch of allocation, branches and method invocations that occur in the actually executed code. Which is the whole point of optimizations for such code, which LINQ lacks.

In fact, how else could "Where" be implemented while keeping lazy semantics?

(Rust, AFAIK, can actually do this, by inlining everything including the lambdas.)

jpatte · on Feb 27, 2015

There is no missing foreach loop because LINQ iterators are smart enough to combine predicates whenever possible (source here: http://referencesource.microsoft.com/#System.Core/System/Lin..., see line 204 when dealing with arrays).

You're right it's missing the actual function calls, but that wasn't the point: the point here was that LINQ avoids building temporary enumerations and iterating over them like JS functions do.

MichaelGG · on Feb 27, 2015

Ah, that's a cool optimization.

But here's a microbenchmark[1]. It's still not close to non-LINQ code. A factor of 10, with a trivial body, just summing up some numbers. (I didn't used Sum() as it appears to use checked arithmetic.)

As far as the optimizations, the smart combining code (which still has to allocate a combined delegate + lambda object, that'll cost, what 2 objects at like 40 bytes each?)) only happens when Select is followed by Select, or Where by Where. Select after Where gets a new "WhereSelectEnumerableIterator" and so on.

So you're right that it does eliminate some overhead though depending on the order of your Wheres and Selects there may be more "foreach" loops in the comparable code. And it's still not even close to being free like it should be. (Like, say, Haskell can do sometimes.)

1: http://pastebin.com/7J9FErWN