Tag Archives: performance

Amélioration des performances de Linq dans .NET Core

Depuis le temps qu’on en parle, vous êtes sans doute au courant que Microsoft a publié une version open-source et multiplateforme de .NET : .NET Core. Cela signifie que vous pouvez maintenant créer et exécuter des applications .NET sous Linux ou macOS. C’est déjà assez cool en soi, mais ça ne s’arrête pas là : .NET Core apporte aussi beaucoup d’améliorations à la Base Class Library.

Par exemple, Linq est plus rapide dans .NET Core. J’ai fait un petit benchmark pour comparer les performances de certaines méthodes couramment utilisées de Linq, et les résultats sont assez impressionnants :


Le code complet de ce benchmark est disponible ici. Comme pour tous les microbenchmarks, les résultats ne sont pas à prendre pour argent comptant, mais ça donne quand même une idée des améliorations.

Certaines lignes de ce tableau sont assez surprenantes. Comment Select peut-il s’exécuter 5000 fois presque instantanément ? D’abord, il faut garder à l’esprit que la plupart des opérateurs Linq ont une exécution différée : ils ne font rien tant que qu’on n’énumère pas le résultat, donc quelque chose comme array.Select(i => i * i) s’exécute en temps constant (ça renvoie juste une séquence "lazy", sans consommer les éléments de array). C’est pourquoi j’ai ajouté un appel à Count() dans mon benchmark, pour m’assurer que le résultat est bien énuméré.

Pourtant, ce test s’exécute 5000 fois en 413µs… Cela est possible grâce à une optimisation dans l’implémentation .NET Core de Select et Count. Une propriété utile de Select est qu’il produit une séquence avec le même nombre d’éléments que la séquence source. Dans .NET Core, Select tire parti de cette propriété. Si la source est une ICollection<T> ou un tableau, il renvoie un objet énumérable qui garde la trace du nombre d’élément. Count peut ensuite récupérer directement la valeur et la renvoyer sans énumérer la séquence, ce qui donne un résultat en temps constant. L’implémentation de .NET 4.6.2, en revanche, énumère naïvement la séquence produite par Select, ce qui prend beaucoup plus longtemps.

Il est intéressant de noter que dans cette situation, .NET Core ne va pas exécuter la projection spécifiée dans Select, c’est donc un breaking change par rapport à .NET 4.6.2 pour du code qui dépend des effets de bord de la projection. Cela a été identifié comme un problème, qui a déjà été corrigé sur la branche master, donc la prochaine version n’aura plus cette optimisation et exécutera bien la projection sur chaque élément.

OrderBy suivi de Count() s’exécute aussi presque instantanément… Les développeurs de Microsoft auraient-ils inventé un algorithme de tri en O(1) ? Malheureusement, non… L’explication est la même que pour Select : puisque OrderBy préserve le nombre d’éléments, l’information est conservée pour pouvoir être utilisée par Count, et il n’est pas nécessaire de vraiment trier les éléments avant d’obtenir leur nombre.

Bon, ces cas étaient des améliorations assez évidentes (qui ne vont d’ailleurs pas rester, comment mentionné précédemment). Mais que dire du cas de SelectAndToArray ? Dans ce test, j’appelle ToArray() sur le résultat de Select, pour être certain que la projection soit bien exécutée sur chaque élément : cette fois, on ne triche pas. Pourtant, l’implémentation de .NET Core arrive encore à être 68% plus rapide que celle du framework .NET classique dans ce scénario. La raison est liée aux allocations : puisque l’implémentation .NET Core sait combien il y a d’éléments dans le résultat de Select, elle peut directement allouer un tableau de la bonne taille. Dans .NET 4.6.2, cette information n’est pas disponible, donc il faut commencer par allouer un petit tableau, y copier des éléments jusqu’à ce qu’il soit plein, puis allouer un tableau plus grand, y copier les données du premier tableau, y copier les éléments suivants de la séquence jusqu’à ce qu’il soit plein, etc. Cela cause de nombreuses allocations et copies, d’où la performance dégradée. Il y a quelques années, j’avais suggéré des versions optimisées de ToList et ToArray, auxquelles on passait le nombre d’éléments. L’implémentation de .NET Core fait grosso modo la même chose, sauf qu’il n’y a pas besoin de passer la taille manuellement, elle est transmise à travers la chaine de méthodes Linq.

Where et WhereAndToArray sont tous les deux environ 8% plus rapides sur .NET Core 1.1. En examinant le code, (.NET 4.6.2, .NET Core), je ne vois pas de différences évidentes qui pourraient expliquer les meilleures performances, donc je soupçonne qu’elles sont dues à des améliorations du runtime. Dans ce cas, ToArray ne connait pas le nombre d’éléments dans la séquence (puisqu’on ne peut pas prédire le nombre d’éléments que Where va laisser passer), il ne peut donc pas utiliser la même optimisation qu’avec Select, et doit construire le tableau en utilisant l’approche plus lente.

On a déjà parlé du cas de OrderBy + Count(), qui n’était pas une comparaison équitable puisque l’implémentation de .NET Core ne triait pas réellement la séquence. Le cas de OrderByAndToArray est plus intéressant, car le tri ne peut pas être évité. Et dans ce cas, l’implémentation de .NET Core est un peu plus lente que celle de .NET 4.6.2. Je ne sais pas très bien pourquoi; là aussi, l’implémentation est très similaire, à part quelques refactorisations dans la version .NET Core.

Au final, Linq a l’air globalement plus rapide dans .NET Core que dans 4.6.2, ce qui est une très bonne nouvelle. Bien sûr, je n’ai benchmarké qu’un nombre limité de scénarios, mais cela montre quand même que l’équipe .NET Core travaille dur pour optimiser tout ce qu’ils peuvent.

Optimiser ToArray et ToList en fournissant le nombre d’éléments

Les méthodes d’extension ToArray et ToList sont des moyens pratiques de matérialiser une séquence énumérable (par exemple une requête Linq). Cependant, quelque chose me chiffonne : ces deux méthodes sont très inefficaces si elles ne connaissent pas le nombre d’éléments dans la séquence (ce qui est presque toujours le cas quand on les utilise sur une requête Linq). Concentrons nous sur ToArray pour l’instant (ToList a quelques différences, mais le principe est essentiellement le même).

Pour faire simple, ToArray prend une séquence, et retourne un tableau qui contient tous les éléments de la séquence. Si la séquence implémente ICollection<T>, ToArray utilise la propriété Count pour allouer un tableau de la bonne taille, et copie les éléments dedans ; voici un exemple :

List<User> users = GetUsers();
User[] array = users.ToArray();

Dans ce scénario, ToArray est assez efficace. Maintenant, changeons ce code pour extraire les noms des utilisateurs :

List<User> users = GetUsers();
string[] array = users.Select(u => u.Name).ToArray();

Maintenant, l’argument de ToArray est un IEnumerable<User> renvoyé par Select. Il n’implémente pas ICollection<User>, donc ToArray ne connait pas le nombre d’éléments, et ne peut donc pas allouer un tableau de la bonne taille. Voilà donc ce qu’il fait :

  1. commencer par allouer un petit tableau (4 éléments dans l’implémentation actuelle)
  2. copier les éléments depuis la source vers le tableau jusqu’à ce que celui-ci soit plein
  3. s’il n’y a plus d’éléments dans la séquence, aller en 7
  4. sinon, allouer un nouveau tableau deux fois plus grand que le précédent
  5. copier les éléments de l’ancien tableau vers le nouveau
  6. répéter depuis l’étape 2
  7. si le tableau est plus long que le nombre d’éléments, le tronquer : allouer un nouveau tableau d’exactement la bonne taille, et y copier les éléments depuis le tableau précédent
  8. renvoyer le tableau

S’il n’y a que quelques éléments, tout ceci est assez indolore ; mais pour une très longue séquence, c’est très inefficace, à cause des nombreuses allocations et copies.

Ce qui est agaçant est que, bien souvent, on (le développeur) connait le nombre d’éléments de la source! Dans l’exemple ci-dessus, on n’utilise que Select, qui ne change pas le nombre d’éléments, donc on sait que c’est le même que dans la liste d’origine; mais ToArray ne le sait pas, car l’information a été perdue en cours de route. Si seulement on pouvait fournir cette information nous-mêmes…

Eh bien, c’est en fait très facile à faire : il suffit de créer une nouvelle méthode d’extension qui accepte le nombre d’éléments comme paramètre. Voilà à quoi elle pourrait ressembler :

public static TSource[] ToArray<TSource>(this IEnumerable<TSource> source, int count)
{
    if (source == null) throw new ArgumentNullException("source");
    if (count < 0) throw new ArgumentOutOfRangeException("count");
    var array = new TSource[count];
    int i = 0;
    foreach (var item in source)
    {
        array[i++] = item;
    }
    return array;
}

On peut maintenant optimiser notre exemple précédent de la façon suivante :

List<User> users = GetUsers();
string[] array = users.Select(u => u.Name).ToArray(users.Count);

Notez que si vous spécifiez un nombre inférieur au nombre réel d’éléments dans la séquence, vous obtiendrez une IndexOutOfRangeException ; il est de votre responsabilité de fournir une information correcte à la méthode.

Et au final, qu’est-ce qu’on y gagne? D’après mes tests, cette version améliorée de ToArray est environ deux fois plus rapide que la version standard, pour une longue séquence (testé avec 1.000.000 éléments). Pas mal du tout !

Notez qu’on peut améliorer ToList de la même manière, en utilisant le constructeur de List<T> qui permet de spécifier la capacité initiale :

public static List<TSource> ToList<TSource>(this IEnumerable<TSource> source, int count)
{
    if (source == null) throw new ArgumentNullException("source");
    if (count < 0) throw new ArgumentOutOfRangeException("count");
    var list = new List<TSource>(count);
    foreach (var item in source)
    {
        list.Add(item);
    }
    return list;
}

Ici, le gain de performance n’est pas aussi important que pour ToArray (environ 25% au lieu de 50%), probablement parce que la liste n’a pas besoin d’être tronquée, mais il n’est pas négligeable.

Bien sûr, une optimisation similaire pourrait être faite pour ToDictionary, puisque la classe Dictionary<TKey, TValue> a aussi un constructeur qui permet de spécifier la capacité initiale.

Les méthodes ToArray et ToList améliorées sont disponibles dans ma librairie Linq.Extras, qui fournit également de nombreuses méthodes d’extension utiles pour travailler avec des séquences et collections.