Réimplémentation de LINQ to Objects : Partie 7 - « Count et LongCount »

Le sujet du jour couvre deux opérateurs, car ils sont incroyablement similaires… à un point tel qu'il suffit de copier-coller l'implémentation puis de changer le nom, le type de retour et quelques variables.

Count et LongCount disposent chacun de deux surcharges: une avec un prédicat, l'autre sans. Voici les quatre signatures:

publicstaticint Count<TSource>( 
 this IEnumerable<TSource> source) 

publicstaticint Count<TSource>( 
 this IEnumerable<TSource> source, 
 Func<TSource, bool> predicate) 

publicstaticlong LongCount<TSource>( 
 this IEnumerable<TSource> source) 

publicstaticlong LongCount<TSource>( 
 this IEnumerable<TSource> source, 
 Func<TSource, bool> predicate)

Comme vous pouvez le constater, les signatures de LongCount sont identiques à celles de Count, excepté pour le type de retour qui est long (Int64) au lieu de int (Int32).

La surcharge sans prédicat se contente de retourner le nombre d'éléments dans la collection source. La surcharge avec prédicat retourne le nombre d'éléments pour lesquels le prédicat est vérifié.

Quelques aspects intéressants de leur comportement:

• elles sont toutes des méthodes d'extension du type IEnumerable<T> - vous pourriez souligner ici que pour les versions sans prédicat il aurait été préférable de définir les méthodes sur le type non générique IEnumerable, car, en effet, rien ne nécessite le type;
• quand il n'y a pas de prédicat, Count est optimisé pour le type ICollection<T> et (à partir de .NET 4) ICollection - tous deux ont une propriété Count supposée être plus rapide que de parcourir toute la collection. LongCount n'est pas optimisé de la même manière dans l'implémentation .NET - j'en discuterai dans la section implémentation;
• aucune optimisation n'est effectuée pour les surcharges avec prédicats, simplement parce qu'il n'y a aucun moyen de savoir combien d'éléments valideront le prédicat sans les tester;
• toutes les méthodes utilisent l'exécution immédiate - rien n'est différé. (Si vous y réfléchissez, rien ne peut être différé ici alors que nous ne faisons que retourner un int ou un long.);
• tous les arguments sont validés en testant simplement qu'ils ne sont pas null;
• chacune des méthodes devrait lever une OverflowException si la collection comporte plus d'éléments que le maximum supporté par le type… bien que ce nombre soit considérablement plus élevé dans le cas de LongCount, évidemment.

Dans un certain sens, il n'y a que deux tests concluants impliqués ici: un sans prédicat et un avec. Ils sont suffisants, mais nous voulons également mettre à l'épreuve les optimisations. C'est cependant plus complexe qu'il n'y paraît, car nous avons quatre situations à tester:

• une source qui implémente ICollection<T> et ICollection (facile: List<T>);
• une source qui implémente ICollection<T> mais pas ICollection (relativement facile, après un petit travail pour trouver un type correspondant: HashSet<T>);
• une source qui implémente ICollection mais pas ICollection<T> mais qui implémente néanmoins IEnumerable<T> (de façon à pouvoir l'étendre) - compliqué…;
• une source qui n'implémente ni ICollection ni ICollection<T> (facile: Enumerable.Range que nous avons déjà implémenté).

Le troisième point est le plus compliqué. Étonnamment, il y a plein de types qui implémentent ICollection mais pas ICollection<T> (ex.: ArrayList), mais comme ils n'implémentent pas IEnumerable<T>, nous ne pouvons pas appeler la méthode d'extension Count<T>. Pour finir, j'ai moi-même écrit ma propre classe: SemiGenericCollection.

Une fois que nous avons des sources pour tous ces tests, nous devons décider des tests que nous allons effectivement leur appliquer. Idéalement, nous devrions tester que le résultat est optimisé en vérifiant, par exemple, que nous n'énumérons jamais réellement la collection. Cela nécessiterait d'écrire des collections personnalisées avec une méthode GetEnumerator() qui lèverait une exception, mais avec une propriété Count qui retournerait effectivement le nombre d'éléments. Je n'ai pas été si loin mais c'est une étape que nous devrions certainement effectuer.

Pour les surcharges qui acceptent un prédicat, nous n'avons pas à nous soucier des différentes interfaces des collections, n'optimisant de toute façon rien.

Les cas d'échec pour les arguments null sont très simples, mais il y a un autre cas à considérer: le dépassement de capacité. Pour l'opérateur Count, j'ai implémenté un test pour vérifier le comportement en cas de dépassement de capacité. Malheureusement, nous ne pouvons exécuter ce test dans l'implémentation Edulinq actuellement, car il nécessite Enumerable.Concat. Le voici néanmoins:

[Test] 
[Ignore("Takes an enormous amount of time!")] 
publicvoid Overflow() 
{ 
 var largeSequence = Enumerable.Range(0, int.MaxValue) 
 .Concat(Enumerable.Range(0, 1)); 
 Assert.Throws<OverflowException>(() => largeSequence.Count()); 
}

Cela nous protège contre une mauvaise implémentation qui traiterait le dépassement en ramenant la valeur aux alentours de Int32.MinValue plutôt que de lever une exception.

Comme vous pouvez le constater, ce test sera désactivé, même après l'implémentation de Concat, car cela nécessite de compter jusqu'à 2 milliards - pas idéal pour un ensemble rapide de tests unitaires. Ce n'est pas encore catastrophique, cependant, comparé à l'équivalent avec LongCount, qui nécessiterait de compter 2⁶³ éléments. Générer une telle séquence n'est pas compliqué, mais l'énumérer prendrait un très long moment. Nous avons également besoin d'un test équivalent pour les surcharges avec prédicat - ce que j'avais négligé jusqu'à l'écriture de ce billet et la découverte d'un bogue dans mon implémentation.

Pour LongCount, j'ai simplement un test similaire à celui décrit plus haut qui vérifie que la même séquence peut avoir sa longueur exprimée par un long.

Nous allons regarder les surcharges qui utilisent un prédicat en premier - elles sont en effet plus simples:

publicstaticint Count<TSource>(this IEnumerable<TSource> source, 
 Func<TSource, bool> predicate) 
{ 
 if (source == null) 
 { 
 thrownew ArgumentNullException("source"); 
 } 
 if (predicate == null) 
 { 
 thrownew ArgumentNullException("predicate"); 
 } 

 // No way of optimizing this 
 checked 
 { 
 int count = 0; 
 foreach (TSource item in source) 
 { 
 if (predicate(item)) 
 { 
 count++; 
 } 
 } 
 return count; 
 } 
}

Notez que cette fois nous n'utilisons pas un bloc itérateur (nous ne retournons pas une séquence) ainsi, nous n'avons pas besoin de séparer l'implémentation en deux méthodes différentes simplement pour obtenir une validation anticipée des arguments.

Après la validation des arguments, la partie principale de la méthode est relativement simple, à une subtilité près: on effectue l'itération complète dans un bloc «checked». Cela implique que si l'incrémentation de count produit un dépassement de capacité, cela lèvera une exception (OverflowException) plutôt que de redémarrer à un nombre négatif. Il y a d'autres solutions ici:

• nous aurions pu nous contenter de placer l'instruction d'incrémentation seule dans le bloc «checked» plutôt que toute la seconde partie de la méthode;
• nous aurions pu tester explicitement que count == int.MaxValue avant de procéder à l'incrémentation et lever une exception le cas échéant;
• nous aurions pu compiler toute l'assembly dans un contexte «checked».

Je pense qu'il est utile pour ce morceau de code d'être placé explicitement dans un bloc «checked» - il devient dès lors évident que c'est une nécessité pour l'exactitude générale. Vous pourriez tout aussi bien préférer ne placer que l'instruction d'incrémentation dans le bloc «checked» - personnellement, je pense que l'approche actuelle attire plus l'attention sur la nécessité de ce bloc «checked», mais c'est totalement subjectif. Il est possible également qu'une vérification explicite soit plus rapide, bien que j'en doute. Je n'ai chronométré aucune des deux approches.

Outre les parties spécifiques au prédicat, tout le code ci-dessus apparaît dans l'implémentation optimisée de Count. De ce fait, je n'en reparlerai pas. Voici le code de la méthode:

publicstaticint Count<TSource>(this IEnumerable<TSource> source) 
{ 
 if (source == null) 
 { 
 thrownew ArgumentNullException("source"); 
 } 

 // Optimization for ICollection<T> 
 ICollection<TSource> genericCollection = source as ICollection<TSource>; 
 if (genericCollection != null) 
 { 
 return genericCollection.Count; 
 } 

 // Optimization for ICollection 
 ICollection nonGenericCollection = source as ICollection; 
 if (nonGenericCollection != null) 
 { 
 return nonGenericCollection.Count; 
 } 

 // Do it the slow way - and make sure we overflow appropriately 
 checked 
 { 
 int count = 0; 
 using (var iterator = source.GetEnumerator()) 
 { 
 while (iterator.MoveNext()) 
 { 
 count++; 
 } 
 } 
 return count; 
 } 
}

La seule «nouveauté» ici est l'optimisation. Il y a, en effet, deux blocs équivalents qui testent la présence des différents types d'interfaces de collection et utilisent le premier trouvé, le cas échéant. Je ne sais pas si l'implémentation .NET teste en premier la présence de ICollection ou ICollection<T> - je pourrais le tester en implémentant les deux interfaces et en retournant un nombre différent pour la propriété Count de chacune d'elles, bien sûr, mais c'est un peu excessif. Cela n'a pas réellement d'importance pour les collections courantes, si ce n'est une minuscule amélioration des performances. Nous voulons tester l'interface la plus «courante» en premier et je pense que c'est la générique.

Les implémentations de LongCount sont identiques à celles de Count, excepté qu'elles utilisent des long plutôt que des int.

À noter que j'ai conservé les optimisations pour ICollection et ICollection<T>. Je ne pense pas cependant que ce soit le cas pour l'implémentation .NET (c'est assez facile à vérifier en créant une énorme liste de bytes et en comparant les temps d'exécution pour Count et LongCount).

Il y a un intérêt à utiliser Array.GetLongLength quand la source est un tableau… mais je ne pense pas que la CLR actuelle supporte des tableaux avec plus de Int32.MaxValue éléments de toute façon, c'est donc une fausse optimisation si ce n'est pour l'anticipation d'une prochaine fonctionnalité. Au-delà de ça, je ne sais pas pourquoi l'implémentation .NET n'est pas optimisée. Ce qu'une ICollection / ICollection<T> est supposée retourner via sa propriété Count quand elle contient plus que Int32.MaxValue éléments n'est de toute façon pas clair, honnêtement.

Des suggestions sur ce que j'aurais dû faire sont les bienvenues… mais je devrais probablement signaler que LongCount est vraisemblablement plus enclin à être utilisé sur des Queryable plutôt que des Enumerable. Il est facile d'imaginer un service représentant une collection (telle une table d'une base de données) qui pourrait rapidement fournir son nombre d'éléments, même s'il est très grand. J'imagine qu'il y a peu de cas où vous avez une collection que vous voulez vraiment parcourir intégralement pour en connaître le nombre d'éléments.

Ce sont nos premiers opérateurs Linq qui retournent des valeurs scalaires plutôt que des séquences, avec la conséquence qu'ils sont plus simples à comprendre en termes de flux d'exécution et de timing. Ces méthodes s'exécutent simplement - avec parfois des optimisations - et retournent leur résultat. Simple et efficace. Cependant, nous avons vu ici qu'il y a quand même quelques aspects intéressants à considérer, en ce compris quelques questions autour de l'optimisation qui n'ont pas spécialement de «bonne» réponse.

La prochaine fois, je pense que j'implémenterai Concat - principalement parce que je pourrai décommenter le test de dépassement de capacité pour Count. Cela nous ramènera à un opérateur qui retourne une séquence, mais c'est vraiment un opérateur simple…

Merci à Jon Skeet de m'avoir autorisé à traduire son article Reimplementing LINQ to Objects: Part 7 - Count and LongCount.

Merci à Thomas Levesque (tomlev) pour ses conseils avisés.

Merci à Claude Leloup pour sa relecture orthographique et ses précieux conseils.