c# Linq to Objects - FirstOrDefault performance

Question

We're trying to optimize some of our methods. We use Redgate's Performance profiler to find some performance leaks.

Our tool uses Linq to objects in several methods. But we have noticed that a FirstOrDefault takes very long on collections with +/- 1000 objects.

The profiler also alerts that the query is very slow. I've added images with the profiler results.

It's not possible to add the collection to a database and then query the database. Any recommendations?

Thanks !

private SaldoPrivatiefKlantVerdeelsleutel GetParentSaldoPrivatiefKlantVerdeelsleutel(SaldoPrivatiefKlantVerdeelsleutel saldoPrivatiefKlantVerdeelsleutel, SaldoGebouwRekeningBoeking boeking, int privatiefKlant)
{
    SaldoPrivatiefKlantVerdeelsleutel parentSaldoPrivatiefKlantVerdeelsleutel = null;

    if (saldoPrivatiefKlantVerdeelsleutel != null)
    {
        try
        {
            parentSaldoPrivatiefKlantVerdeelsleutel = saldoPrivatiefKlantVerdeelsleutel.AfrekenPeriode.SaldoPrivatiefKlantVerdeelsleutelCollection
                .FirstOrDefault(s => (boeking == null || (s.SaldoVerdeelsleutel != null &&
                (s.SaldoVerdeelsleutel.GebouwVerdeelSleutel.ID == boeking.SaldoGebouwRekeningVerdeling.SaldoGebouwRekening.SaldoVerdeelsleutel.GebouwVerdeelSleutel.ID)))
                && s.PrivatiefKlant.ID == privatiefKlant);
        }
        catch (Exception ex)
        { }
    }

    return parentSaldoPrivatiefKlantVerdeelsleutel;
}

Image : Profile report

My first thought is to move the `boeking == null` check, and the `SaldoGebouwRekeningVerdeling.SaldoGebouwRekening.SaldoVerdeelsleutel.GebouwVerdeelSleutel.ID` value _outside_ your loop. There's no reason to re-evaluate it for every single element in your collection. — Chris Sinclair, Aug 30 '13 at 13:18
The query is executed when you read from the expression. In this case the FirstOrDefault will execute the whole expression tree, so it's not the FirstOrDefault thats slow. — Jeroen van Langen, Aug 30 '13 at 13:24
Obligatory remark: An empty `catch{}` is very harmful, remove it. — H H, Aug 30 '13 at 13:29
Now I'll ask you a question... That objects are loaded through NHibernate or Entity Framework, right? Are you sure they aren't partially LAZILY LOADED? Like this `s.SaldoVerdeelsleutel.GebouwVerdeelSleutel.ID` ? Because it could be a classical [SELECT N+1 antipattern](http://stackoverflow.com/questions/97197/what-is-the-n1-selects-issue). — xanatos, Aug 30 '13 at 13:30

score 7 · Answer 1 · edited May 23 '17 at 12:23

You should be able to speed it up by rewriting it as

saldoPrivatiefKlantVerdeelsleutel.AfrekenPeriode.SaldoPrivatiefKlantVerdeelsleutelCollection
            .Where(s => (boeking == null || (s.SaldoVerdeelsleutel != null &&
                (s.SaldoVerdeelsleutel.GebouwVerdeelSleutel.ID == boeking.SaldoGebouwRekeningVerdeling.SaldoGebouwRekening.SaldoVerdeelsleutel.GebouwVerdeelSleutel.ID))) && s.PrivatiefKlant.ID == privatiefKlant)
            .FirstOrDefault()

See Why is LINQ .Where(predicate).First() faster than .First(predicate)? for why this is faster.

MarcinJuraszek · Answer 2 · 2013-08-30T13:22:53.953

FirstOrDefault do standard linear search over source collection and returns first element that matches a predicate. It's O(n), so it's not surprising that it takes more time on bigger collections.

You can try following, but the gain won't be huge, because it's still O(n).

private SaldoPrivatiefKlantVerdeelsleutel GetParentSaldoPrivatiefKlantVerdeelsleutel(SaldoPrivatiefKlantVerdeelsleutel saldoPrivatiefKlantVerdeelsleutel, SaldoGebouwRekeningBoeking boeking, int privatiefKlant)
{
    SaldoPrivatiefKlantVerdeelsleutel parentSaldoPrivatiefKlantVerdeelsleutel = null;

    if (saldoPrivatiefKlantVerdeelsleutel != null)
    {
        try
        {
            var query = saldoPrivatiefKlantVerdeelsleutel.AfrekenPeriode
                                                         .SaldoPrivatiefKlantVerdeelsleutelCollection
                                                         .Where(s => s.PrivatiefKlant.ID == privatiefKlant);

            if(boeking != null)
            {
                var gebouwVerdeelSleutelId = boeking.SaldoGebouwRekeningVerdeling
                                                    .SaldoGebouwRekening
                                                    .SaldoVerdeelsleutel
                                                    .GebouwVerdeelSleutel
                                                    .ID;

                query = query.Where(s => s.SaldoVerdeelsleutel != null &&
                    s.SaldoVerdeelsleutel.GebouwVerdeelSleutel.ID == gebouwVerdeelSleutelId);
            }
            parentSaldoPrivatiefKlantVerdeelsleutel = query.FirstOrDefault();
        }
        catch (Exception ex)
        { }
    }

    return parentSaldoPrivatiefKlantVerdeelsleutel;
}

It will make better, because boeking != null check will be done only once, not on every source collection element. And because nested Where calls are combined they will not cause performance penalty.

score 2 · Answer 3 · answered Aug 30 '13 at 13:20

I'll say that this

boeking.SaldoGebouwRekeningVerdeling.SaldoGebouwRekening.SaldoVerdeelsleutel.GebouwVerdeelSleutel.ID

could be the culprit. Try caching it outside, like:

var id = boeking != null ? boeking.SaldoGebouwRekeningVerdeling.SaldoGebouwRekening.SaldoVerdeelsleutel.GebouwVerdeelSleutel.ID : 0;

and use the id inside the query.

(I'm doing a supposition: one of the properties of that long chain do something "not too much smart" and is in fact quite slow)

score 0 · Answer 4 · answered Aug 30 '13 at 13:43

You can try write it like a simple code. LINQ is using delegates this is why there is a little perfomance hit.

                try
                {
                    parentSaldoPrivatiefKlantVerdeelsleutel = null;
                    foreach (var s in saldoPrivatiefKlantVerdeelsleutel.AfrekenPeriode.SaldoPrivatiefKlantVerdeelsleutelCollection)
                    {
                        if ((boeking == null || (s.SaldoVerdeelsleutel != null && (s.SaldoVerdeelsleutel.GebouwVerdeelSleutel.ID == boeking.SaldoGebouwRekeningVerdeling.SaldoGebouwRekening.SaldoVerdeelsleutel.GebouwVerdeelSleutel.ID))) && s.PrivatiefKlant.ID == privatiefKlant)
                        {
                            parentSaldoPrivatiefKlantVerdeelsleutel = s;
                            break;
                        }
                    }
                }
                catch (Exception ex)
                { }

c# Linq to Objects - FirstOrDefault performance

4 Answers4

Linked