différence de performance entre foreach + break et linq FirstOrDefault

Question

J'ai deux classes qui effectuent la récupération de données sur une plage de dates pour des jours particuliers.

public class IterationLookup<TItem>
{
    private IList<Item> items = null;

    public IterationLookup(IEnumerable<TItem> items, Func<TItem, TKey> keySelector)
    {
        this.items = items.OrderByDescending(keySelector).ToList();
    }

    public TItem GetItem(DateTime day)
    {
        foreach(TItem i in this.items)
        {
           if (i.IsWithinRange(day))
           {
               return i;
           }
        }
        return null;
    }
}

public class LinqLookup<TItem>
{
    private IList<Item> items = null;

    public IterationLookup(IEnumerable<TItem> items, Func<TItem, TKey> keySelector)
    {
        this.items = items.OrderByDescending(keySelector).ToList();
    }

    public TItem GetItem(DateTime day)
    {
        return this.items.FirstOrDefault(i => i.IsWithinRange(day));
    }
}

Ensuite, je fais des tests de vitesse qui montrent que la version de Linq est à peu près 5 fois plus lent . Cela aurait un sens lorsque je stocke des éléments localement sans les énumérer en utilisant la fonction ToList . Cela le rendrait beaucoup plus lent, car à chaque appel à FirstOrDefault linq effectuerait également OrderByDescending . Mais ce n'est pas le cas, alors je ne sais pas vraiment ce qui se passe. Linq devrait fonctionner de manière très similaire à l'itération.

Voici l'extrait de code qui mesure mes timings

IList<RangeItem> ranges = GenerateRanges(); // returns List<T>

var iterLookup = new IterationLookup<RangeItems>(ranges, r => r.Id);
var linqLookup = new LinqLookup<RangeItems>(ranges, r => r.Id);

Stopwatch timer = new Stopwatch();

timer.Start();
for(int i = 0; i < 1000000; i++)
{
    iterLookup.GetItem(GetRandomDay());
}
timer.Stop();
// display elapsed time

timer.Restart();
for(int i = 0; i < 1000000; i++)
{
    linqLookup.GetItem(GetRandomDay());
}
timer.Stop();
// display elapsed time

Pourquoi je sais qu'il devrait être plus performant ? Parce que lorsque j'écris un code très similaire sans utiliser ces classes de recherche, Linq a des performances très proches de celles de foreach itérations...

// continue from previous code block

// items used by both order as they do in classes as well
IList<RangeItem> items = ranges.OrderByDescending(r => r.Id).ToList();

timer.Restart();
for(int i = 0; i < 1000000; i++)
{
    DateTime day = GetRandomDay();
    foreach(RangeItem r in items)
    {
        if (r.IsWithinRange(day))
        {
            // RangeItem result = r;
            break;
        }
    }
}    
timer.Stop();
// display elapsed time

timer.Restart();
for(int i = 0; i < 1000000; i++)
{
   DateTime day = GetRandomDay();
   items.FirstOrDefault(i => i.IsWithinRange(day));
}
timer.Stop();
// display elapsed time

Il s'agit à mon avis d'un code très similaire. FirstOrDefault pour autant que je sache, itèrent aussi seulement jusqu'à ce qu'ils atteignent un élément valide ou jusqu'à ce qu'ils atteignent la fin. Et c'est en quelque sorte la même chose que foreach con break .

Mais même la classe d'itération fonctionne moins bien que mon simple foreach la boucle d'itération, qui est également un mystère car la seule surcharge qu'elle présente est l'appel à une méthode au sein d'une classe par rapport à un accès direct.

Pregunta

Qu'est-ce que je fais de mal dans ma classe LINQ pour qu'elle soit si lente ?
Qu'est-ce que je fais de mal dans ma classe Iteration pour qu'elle soit deux fois plus lente que la classe directe ? foreach boucle ?

Quels sont les temps mesurés ?

Je fais ces étapes :

1. Générer des plages (comme indiqué ci-dessous dans les résultats)
2. Créer des instances d'objets pour IterationLookup, LinqLookup (et ma classe de plage de dates optimisée BitCountLookup qui ne fait pas partie de la discussion ici).
3. Lancez la minuterie et exécutez 1 million de recherches sur des jours aléatoires dans la plage de dates maximale (comme indiqué dans les résultats) en utilisant la classe IterationLookup précédemment instanciée.
4. Lancez une minuterie et exécutez 1 million de recherches sur des jours aléatoires dans la plage de dates maximale (comme indiqué dans les résultats) en utilisant la classe LinqLookup précédemment instanciée.
5. Lancez une minuterie et exécutez 1 million de recherches (6 fois) en utilisant des boucles manuelles foreach+break et des appels Linq.

Comme vous pouvez le constater l'instanciation de l'objet n'est pas mesurée .

Annexe I : Résultats sur un million de consultations

Les plages affichées dans ces résultats ne se chevauchent pas, ce qui devrait rendre les deux approches encore plus similaires au cas où la version LINQ ne rompt pas la boucle en cas de correspondance réussie (ce qui est très probable).

Generated Ranges:

ID Range        000000000111111111122222222223300000000011111111112222222222
                123456789012345678901234567890112345678901234567890123456789
09 22.01.-30.01.                     |-------|
08 14.01.-16.01.             |-|
07 16.02.-19.02.                                              |--|
06 15.01.-17.01.              |-|
05 19.02.-23.02.                                                 |---|
04 01.01.-07.01.|-----|
03 02.01.-10.01. |-------|
02 11.01.-13.01.          |-|
01 16.01.-20.01.               |---|
00 29.01.-06.02.                            |-------|

Lookup classes...

- Iteration: 1028ms
**\- Linq: 4517ms   !!! THIS IS THE PROBLEM !!!**
- BitCounter: 401ms

Manual loops...

- Iter: 786ms
- Linq: 981ms
- Iter: 787ms
- Linq: 996ms
- Iter: 787ms
- Linq: 977ms
- Iter: 783ms
- Linq: 979ms

Annexe II : code GitHub:Gist à tester par vous-même

J'ai mis en place un Gist pour que vous puissiez obtenir le code complet vous-même et voir ce qui se passe. Créez un Console demande et copie Programme.cs et ajouter d'autres fichiers qui font partie de cette liste.

Prends-le. aquí .

Annexe III : Réflexions finales et tests de mesure

La chose la plus problématique était bien sûr l'implémentation de LINQ qui était terriblement lente. Il s'avère que cela a tout à voir avec l'optimisation du compilateur de délégués. LukeH a fourni la solution la meilleure et la plus utilisable. qui m'a fait essayer différentes approches de la question. J'ai essayé plusieurs approches différentes dans le GetItem (ou GetPointData comme on l'appelle dans Gist) :

1. la manière habituelle que la plupart des développeurs feraient (et qui est également implémentée dans Gist et n'a pas été mise à jour après que les résultats aient révélé que ce n'est pas la meilleure manière de faire) :

   return this.items.FirstOrDefault(item => item.IsWithinRange(day));

2. en définissant une variable de prédicat locale :

   Func<TItem, bool> predicate = item => item.IsWithinRange(day);
   return this.items.FirstOrDefault(predicate);

3. constructeur local de prédicats :

   Func<DateTime, Func<TItem, bool>> builder = d => item => item.IsWithinRange(d);
   return this.items.FirstOrDefault(builder(day));

4. constructeur de prédicat local et variable de prédicat local :

   Func<DateTime, Func<TItem, bool>> builder = d => item => item.IsWithinRange(d);
   Func<TItem, bool> predicate = builder(day);
   return this.items.FirstOrDefault(predicate);

5. constructeur de prédicats au niveau de la classe (statique ou instance) :

   return this.items.FirstOrDefault(classLevelBuilder(day));

6. prédicat défini en externe et fourni comme paramètre de la méthode

   public TItem GetItem(Func<TItem, bool> predicate)
   {
       return this.items.FirstOrDefault(predicate);
   }

   En exécutant cette méthode, j'ai également adopté deux approches :

   1. prédicat fourni directement à l'appel de la méthode dans for boucle :

      for (int i = 0; i < 1000000; i++)
      {
          linqLookup.GetItem(item => item.IsWithinRange(GetRandomDay()));
      }

   2. constructeur de prédicats défini en dehors de for boucle :

      Func<DateTime, Func<Ranger, bool>> builder = d => r => r.IsWithinRange(d);
      for (int i = 0; i < 1000000; i++)
      {
          linqLookup.GetItem(builder(GetRandomDay()));
      }

Résultats - ce qui est le plus performant

À titre de comparaison, l'utilisation de la classe d'itération prend environ 1,5 heure. 770ms pour exécuter 1 million de recherches sur des plages générées aléatoirement.

1. Le constructeur de prédicats locaux 3 s'avère être le mieux optimisé par le compilateur, ce qui lui permet d'être presque aussi rapide que les itérations habituelles. 800 ms .

2. 6.2 constructeur de prédicats défini en dehors de l'entreprise for boucle : 885ms

3. 6.1 prédicat défini dans for boucle : 1525ms

4. tous les autres ont pris entre 4200ms - 4360ms et sont donc considérés comme inutilisables.

Ainsi, chaque fois que vous utilisez un prédicat dans une méthode fréquemment appelée en externe, définissez un constructeur et exécutez-le. Cela donnera les meilleurs résultats.

Ce qui me surprend le plus, c'est que les délégués (ou prédicats) puissent prendre autant de temps.

Answer 1

Parfois, LINQ semble plus lent parce que la génération de délégués dans une boucle (en particulier une boucle non évidente sur des appels de méthode) peut ajouter du temps. Au lieu de cela, vous pouvez envisager de déplacer votre finder hors de la classe pour le rendre plus générique (comme votre sélecteur de clé est sur la construction) :

public class LinqLookup<TItem, TKey>
{
    private IList<Item> items = null;

    public IterationLookup(IEnumerable<TItem> items, Func<TItem, TKey> keySelector)
    {
        this.items = items.OrderByDescending(keySelector).ToList();
    }

    public TItem GetItem(Func<TItem, TKey> selector)
    {
        return this.items.FirstOrDefault(selector);
    }
}

Comme vous n'utilisez pas de lambda dans votre code itératif, cela peut faire une petite différence puisqu'il faut créer le délégué à chaque passage dans la boucle. Habituellement, ce temps est insignifiant pour le codage de tous les jours, et le temps pour invoquer le délégué n'est pas plus cher que les autres appels de méthode, c'est juste la création du délégué dans une boucle serrée qui peut ajouter ce petit peu de temps supplémentaire.

Dans ce cas, puisque le délégué ne change jamais pour la classe, vous pouvez le créer en dehors du code que vous parcourez en boucle et ce serait plus efficace.

Mise à jour :

En fait, même sans aucune optimisation, en compilant en mode release sur ma machine, je ne vois pas la différence de 5x. Je viens d'effectuer 1 000 000 de recherches sur un fichier Item qui n'a qu'un DateTime avec 5 000 articles dans la liste. Bien sûr, mes données, etc., sont différentes, mais vous pouvez voir que les temps sont en fait très proches lorsque vous faites abstraction du délégué :

itératif : 14279 ms, 0.014279 ms/appel

linq w opt : 17400 ms, 0.0174 ms/appel

Ces décalages horaires sont très mineur et qui vaut les améliorations de lisibilité et de maintenabilité de l'utilisation de LINQ. Je ne vois pas la différence de 5x, ce qui me pousse à croire qu'il y a quelque chose que nous ne voyons pas dans votre harnais de test.

Answer 2

Suite à La réponse de Gabe je peux confirmer que la différence semble être causée par le coût de la reconstruction du délégué pour chaque appel à la fonction GetPointData .

Si j'ajoute une seule ligne à la GetPointData dans votre IterationRangeLookupSingle puis il ralentit jusqu'à devenir aussi lent que la classe LinqRangeLookupSingle . Essayez-le :

// in IterationRangeLookupSingle<TItem, TKey>
public TItem GetPointData(DateTime point)
{
    // just a single line, this delegate is never used
    Func<TItem, bool> dummy = i => i.IsWithinRange(point);

    // the rest of the method remains exactly the same as before
    // ...
}

(Je ne sais pas pourquoi le compilateur et/ou jitter ne peuvent pas simplement ignorer le délégué superflu que j'ai ajouté ci-dessus. Évidemment, le délégué est nécessaire dans votre LinqRangeLookupSingle classe.)

Une solution de contournement possible est de composer le prédicat en LinqRangeLookupSingle de sorte que point lui est passé en tant qu'argument. Cela signifie que le délégué doit seulement être construit une fois pas à chaque fois que le GetPointData est appelée. Par exemple, la modification suivante accélérera la version LINQ de sorte qu'elle soit à peu près comparable à la version foreach version :

// in LinqRangeLookupSingle<TItem, TKey>
public TItem GetPointData(DateTime point)
{
    Func<DateTime, Func<TItem, bool>> builder = x => y => y.IsWithinRange(x);
    Func<TItem, bool> predicate = builder(point);

    return this.items.FirstOrDefault(predicate);
}

Answer 3

Supposons que vous ayez une boucle comme celle-ci :

for (int counter = 0; counter < 1000000; counter++)
{
    // execute this 1M times and time it 
    DateTime day = GetRandomDay(); 
    items.FirstOrDefault(i => i.IsWithinRange(day)); 
}

Cette boucle va créer 1.000.000 d'objets lambda afin que le i.IsWithinRange appel à l'accès day . Après chaque création de lambda, le délégué qui appelle i.IsWithinRange est invoqué en moyenne 1.000.000 *. items.Length / 2 fois. Ces deux facteurs n'existent pas dans votre foreach c'est pourquoi la boucle explicite est plus rapide.