C# Lambda performance issues/possibilities/guidelines

Question

I'm testing performance differences using various lambda expression syntaxes. If I have a simple method:

public IEnumerable<Item> GetItems(int point)
{
    return this.items.Where(i => i.IsApplicableFor(point));
}

then there's some variable lifting going on here related to point parameter because it's a free variable from lambda's perspective. If I would call this method a million times, would it be better to keep it as it is or change it in any way to improve its performance?

What options do I have and which ones are actually feasible? As I understand it is I have to get rid of free variables so compiler won't have to create closure class and instantiate it on every call to this method. This instantiation usually takes significant amount of time compared to non-closure versions.

The thing is I would like to come up with some sort of lambda writing guidelines that would generally work, because it seems I'm wasting some time every time I write a heavily hit lambda expression. I have to manually test it to make sure it will work, because I don't know what rules to follow.

Alternative method

& example console application code

I've also written a different version of the same method that doesn't need any variable lifting (at least I think it doesn't, but you guys who understand this let me know if that's the case):

public IEnumerable<Item> GetItems(int point)
{
    Func<int, Func<Item, bool>> buildPredicate = p => i => i.IsApplicableFor(p);
    return this.items.Where(buildPredicate(point));
}

Check out Gist here. Just create a console application and copy the whole code into Program.cs file inside namespace block. You will see that the second example is much much slower even though it doesn't use free variables.

A contradictory example

The reason why I would like to construct some lambda best usage guidelines is that I've met this problem before and to my surprise that one turned out to be working faster when a predicate builder lambda expression was used.

Now explain that then. I'm completely lost here because it may as well turn out I won't be using lambdas at all when I know I have some heavy use method in my code. But I would like to avoid such situation and get to the bottom of it all.

Edit

Your suggestions don't seem to work

I've tried implementing a custom lookup class that internally works similar to what compiler does with a free variable lambda. But instead of having a closure class I've implemented instance members that simulate a similar scenario. This is the code:

private int Point { get; set; }
private bool IsItemValid(Item item)
{
    return item.IsApplicableFor(this.Point);
}

public IEnumerable<TItem> GetItems(int point)
{
    this.Point = point;
    return this.items.Where(this.IsItemValid);
}

Interestingly enough this works just as slow as the slow version. I don't know why, but it seems to do nothing else than the fast one. It reuses the same functionality because these additional members are part of the same object instance. Anyway. I'm now extremely confused!

I've updated Gist source with this latest addition, so you can test for yourself.

Answer 1

What makes you think that the second version doesn't require any variable lifting? You're defining the Func with a Lambda expression, and that's going to require the same bits of compiler trickery that the first version requires.

Furthermore, you're creating a Func that returns a Func, which bends my brain a little bit and will almost certainly require re-evaluation with each call.

I would suggest that you compile this in release mode and then use ILDASM to examine the generated IL. That should give you some insight into what code is generated.

Another test that you should run, which will give you more insight, is to make the predicate call a separate function that uses a variable at class scope. Something like:

private DateTime dayToCompare;
private bool LocalIsDayWithinRange(TItem i)
{
    return i.IsDayWithinRange(dayToCompare);
}

public override IEnumerable<TItem> GetDayData(DateTime day)
{
    dayToCompare = day;
    return this.items.Where(i => LocalIsDayWithinRange(i));
}

That will tell you if hoisting the day variable is actually costing you anything.

Yes, this requires more code and I wouldn't suggest that you use it. As you pointed out in your response to a previous answer that suggested something similar, this creates what amounts to a closure using local variables. The point is that either you or the compiler has to do something like this in order to make things work. Beyond writing the pure iterative solution, there is no magic you can perform that will prevent the compiler from having to do this.

My point here is that "creating the closure" in my case is a simple variable assignment. If this is significantly faster than your version with the Lambda expression, then you know that there is some inefficiency in the code that the compiler creates for the closure.

I'm not sure where you're getting your information about having to eliminate the free variables, and the cost of the closure. Can you give me some references?

Answer 2

Your second method runs 8 times slower than the first for me. As @DanBryant says in comments, this is to do with constructing and calling the delegate inside the method - not do do with variable lifting.

Your question is confusing as it reads to me like you expected the second sample to be faster than the first. I also read it as the first is somehow unacceptably slow due to 'variable lifting'. The second sample still has a free variable (point) but it adds additional overhead - I don't understand why you'd think it removes the free variable.

As the code you have posted confirms, the first sample above (using a simple inline predicate) performs jsut 10% slower than a simple for loop - from your code:

foreach (TItem item in this.items)
{
    if (item.IsDayWithinRange(day))
    {
        yield return item;
    }
}

So, in summary:

• The for loop is the simplest approach and is "best case".
• The inline predicate is slightly slower, due to some additional overhead.
• Constructing and calling a Func that returns Func within each iteration is significantly slower than either.

I don't think any of this is surprising. The 'guideline' is to use an inline predicate - if it performs poorly, simplify by moving to a straight loop.

Answer 3

I profiled your benchmark for you and determined many things:

First of all, it spends half its time on the line return this.GetDayData(day).ToList(); calling ToList. If you remove that and instead manually iterate over the results, you can measure relative the differences in the methods.

Second, because IterationCount = 1000000 and RangeCount = 1, you are timing the initialization of the different methods rather than the amount of time it takes to execute them. This means your execution profile is dominated by creating the iterators, escaping variable records, and delegates, plus the hundreds of subsequent gen0 garbage collections that result from creating all that garbage.

Third, the "slow" method is really slow on x86, but about as fast as the "fast" method on x64. I believe this is due to how the different JITters create delegates. If you discount the delegate creation from the results, the "fast" and "slow" methods are identical in speed.

Fourth, if you actually invoke the iterators a significant number of times (on my computer, targetting x64, with RangeCount = 8), "slow" is actually faster than "foreach" and "fast" is faster than all of them.

In conclusion, the "lifting" aspect is negligible. Testing on my laptop shows that capturing a variable like you do requires an extra 10ns every time the lambda gets created (not every time it is invoked), and that includes the extra GC overhead. Furthermore, while creating the iterator in your "foreach" method is somewhat faster than creating the lambdas, actually invoking that iterator is slower than invoking the lambdas.

If the few extra nanoseconds required to create delegates is too much for your application, consider caching them. If you require parameters to those delegates (i.e. closures), consider creating your own closure classes such that you can create them once and then just change the properties when you need to reuse their delegates. Here's an example:

public class SuperFastLinqRangeLookup<TItem> : RangeLookupBase<TItem>
    where TItem : RangeItem
{

    public SuperFastLinqRangeLookup(DateTime start, DateTime end, IEnumerable<TItem> items)
        : base(start, end, items)
    {
        // create delegate only once
        predicate = i => i.IsDayWithinRange(day);
    }

    DateTime day;
    Func<TItem, bool> predicate;

    public override IEnumerable<TItem> GetDayData(DateTime day)
    {
        this.day = day; // set captured day to correct value
        return this.items.Where(predicate);
    }
}

Answer 4

When a LINQ expression that uses deferred execution executes within the same scope that encloses the free variables it references, the compiler should detect that and not create a closure over the lambda, because it's not needed.

The way to verify that would be by testing it using something like this:

public class Test
{
   public static void ExecuteLambdaInScope()
   {
      // here, the lambda executes only within the scope
      // of the referenced variable 'add'

      var items = Enumerable.Range(0, 100000).ToArray();

      int add = 10;  // free variable referenced from lambda

      Func<int,int> f = x => x + add;

      // measure how long this takes:
      var array = items.Select( f ).ToArray();  
   }

   static Func<int,int> GetExpression()
   {
      int add = 10;
      return x => x + add;  // this needs a closure
   }

   static void ExecuteLambdaOutOfScope()
   {
      // here, the lambda executes outside the scope
      // of the referenced variable 'add'

      Func<int,int> f = GetExpression();

      var items = Enumerable.Range(0, 100000).ToArray();

      // measure how long this takes:
      var array = items.Select( f ).ToArray();  
   }

}