Hacker News Reader

Comment by untog | Hacker News Reader

It is and it isn't. LINQ is actually incredibly smart under the hood, so if I ran:

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

it wouldn't actually run two different array filters - it would combine them. You can imagine the performance gains to be had there.

View on HN

Citation? I was unaware that the little IEnumerable functions did fusion. If you mean an IQueryable execution, like LINQ-To-SQL, then sure.

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);
    }
  }

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.)

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.

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

It is not so bad in JavaScript anymore. With Lodash:

    _(myList)
        .filter(x => x.name == 'Person')
        .filter(x => x.age > 18)
        .value()

Used like this Lodash is lazy, so the first value of myList will run through all the filters before the next item gets processed.

Well, underscore offers this, from the docs:

_.where(listOfPlays, {author: "Shakespeare", year: 1611});

That's not the same, though; that's you purposefully combining your query (which you can do in LINQ).

LINQ doesn't just combine Wheres. It tries to optimize your query as much as possible and executes lazily, so you aren't actually doing any work until you try to use the resultset (in a ToList, for example).

I don't know about Underscore, but lo-dash [0] supports lazy execution of a chained query without generating intermediate arrays (see docs [1]). It offers something pretty similar to LINQ queries on collections (except you don't get the benefit of strong typing).

[0]: https://lodash.com/

[1]: https://lodash.com/docs#_

Yes. IQueryable actually implements an expression tree, which means that it may never be executed, at least directly. LINQ to Entities (Entity Framework) actually evaluates the expression tree to build SQL statements, then runs those and returns the results (after coercion back to the mapped POCO object).

Right. Actually Linq to SQL did the same thing, but a big philosophical difference is Entity will reject stuff that it can't resolve from the database instead of just letting you do whatever (which may involve multiple queries).

Reply on news.ycombinator.com