Discussion :

[Benbout]

Bonsoir, ce sujet est surement un marronier qui revient régulierement jusqu'a à vous, mais la question me parait très importante surtout du fait que j'ai pu voir de grosses collections d'objets être contenus dans des conteneurs pas forcément très réputés pour leur performance quand un grand nombre d'objets y est stocké.

Je me questionne au sujet de la meilleure collection à choisir en fonction de mes priorités, sachant que je cherche à stocker des références d'objets qui en general seront d'environ 500 et dont certaines pourraient s'élever à 20k, le tout pour y effectuer des ajout / remove fréquents et des itérations moins fréquentes, avec du tri en linq. Cela doit etre le plus rapide possible évidemment c'est pour un serveur.

les listes sont fréquemment pointées du doigt pour leur faiblesse quand elles contiennent un grand nombre d'entiers ou un petit nombre de strings de taille moyenne, selon certains benchmark maison :

Just thought I'd chime in with some benchmarks for different scenarios to illustrate the previous answers:

A few (12 - 20) small strings (length between 5 and 10 characters)
Many (~10K) small strings
A few long strings (length between 200 and 1000 characters)
Many (~5K) long strings
A few integers
Many (~10K) integers

And for each scenario, looking up values which appear:

In the beginning of the list ("start", index 0)
Near the beginning of the list ("early", index 1)
In the middle of the list ("middle", index count/2)
Near the end of the list ("late", index count-2)
At the end of the list ("end", index count-1)

Before each scenario I generated randomly sized lists of random strings, and then fed each list to a hashset. Each scenario ran 10,000 times, essentially:

(test pseudocode)

stopwatch.start
for X times
exists = list.Contains(lookup);
stopwatch.stop

stopwatch.start
for X times
exists = hashset.Contains(lookup);
stopwatch.stop

Sample Output

Tested on Windows 7, 12GB Ram, 64 bit, Xeon 2.8GHz

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...

Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]


---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...

Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]


---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]


---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]


---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...

Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]


---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]

Et pourtant, je remarque que pas mal de studios qui utilisent des moteurs de jeu en c# natif utilisent énormément de listes d'objets (que ce soit pour le moteur lui meme ou pour la partie serveur de ces jeux) et ce pour des collections qui sont assez importantes à itérer ou à SELECT avec linq (+ de 30 000) et avec des add/remove très fréquents, pourtant selon ces benchmark il apparaitrait que les listes soient vraiment très désavantagées pour ces types de collections, du coup je m'interroge sur le fait de remplacer toutes les listes qui contiennent beaucoup d'objets par des hashset.

Selon vous, ces benchmark sont ils pertinents ?
La liste a elle vraiment une impact important sur l'execution des traitements quand elles contiennent un nombre important d'objet ?
Que me conseilleriez vous de privilégier, au regard des informations que je vous ai donné plus haut ? (rester sur des listes, passer en hashset ? Ce qui ne me dérangerait pas puisque mes listes ne sont pas censés accueillir de doublon).

Merci.

[clementmarcotte]

Bonjour.

C'est bizarre er je n'ai absolument rien qui prouverait que c'est mieux. Mais, instinctivement, je te dirais de regarder vers des DataTable(s). D'autant plus que tu peux les sauvegarder en xml, et les relire, avec une seule ligne de code. De prime abord (et sans preuve, je le répète) je sui porté à penser que les DataTable, sont mieux adaptées aux modifications fréquentes que les collections.

[Pol63]

il y a peu de chances que le datatable soit plus performant, le dataadapter qui en remplie est significativement plus long qu'un remplissage d'une list<list<object>> via un datareader déjà
et l'argument de l'xml ne tient pas, tout peut être sérialisé en xml


sinon c'est assez facile à tester donc tu pourrais trouver ce qui te convient le mieux dans ton cas

après de ce que j'ai en tête je dirais que :
- le list doit être ce qu'il y a de plus rapide en .add (le queue est peut être plus rapide, mais il n'est pas prévu pour des itérations)
idéalement il faut le prédimensionner (new list<object>(nbvaleurprévues))
car c'est un tableau qui est derrière et il a une dimension de base, quand ca dépasse, un nouveau tableau 2x plus grand est créé et le premier est copié dedans, c'est donc là qu'on a de la perte de perf
- en .remove avec un peu de chance il déplace des items, donc ca ne doit pas être ce qu'il y a de mieux
- et en itération ca doit aller aussi, 30k dans une list c'est pas énorme non plus

(...)

en fait je viens de faire un petit test pour pas trop dire de conneries, et pour 30k items
ADD : list légèrement plus performant mais les 2 sont en dessous de 3ms
REMOVE : hashset énormement plus performant
FOR EACH : pas de différence noté, temps insignifiant dans les 2 cas
CONTAINS : même chose que remove, il a un index sur le hashage donc c'est quasi immédiat avec le hashset et long avec le list

après dans les différences hashset ne permet pas d'avoir des doublons
list permet d'accéder à un élément par son rang (list[8]) et donc de changer un item d'un rang
sur list il y a aussi .insert

après quand tu fais du .add et après juste de la lecture le list reste ce qu'il y a de mieux
par contre si tu fais des milliers de delete assez souvent, ou des milliers de contains le hashset sera en effet plus performant (et si les contraintes du hashset n'en sont pas dans ton cas)
mais si c'est pour un delete de temps en temps le list reste plus efficace, d'où son utilisation massive je pense (ca plus le fait que c'est la collection la plus simple et que certains développeurs ne savent pas qu'il y a plein d'autres types de collection )

après c'est surtout les besoins qui font le choix, si tu veux pouvoir mettre 3x la même chose tu ne pourras pas prendre le hashset
et si tu veux du contains rapide sur une liste de choses tu prendras le hashset

[StringBuilder]

J'avoue être surpris de lire dans une même phrase "je cherche le truc le plus performant" et "j'utilise Linq".

Je veux bien que Linq soit bien écrit, mais en aucun cas il peut faire mieux qu'une recherche "manuelle", surtout quand toi tu fonctionnellement la structure des listes.

Pour faire le parallèle avec SQL :
- Linq n'a pas d'optimiseur
- Linq n'a pas d'index à utiliser

De ce fait, au mieux, il produira le même code que le tiens, absolument pas optimisé.
-> Toi tu as l'intelligence de savoir que ça sert à rien de rechercher le nombre d'enfant des personnes qui ont moins de 12 ans : Linq, lui il va aller voir s'il y a des noeuds fils quand même.
-> Toi tu as l'intelligence de savoir que quand t'as chargé les gens dans ta liste, elles étaient triées par date de naissance, et que donc ça sert à rien de parcourir la liste depuis le début pour rechercher le nombre d'enfants, puisque toutes les premières lignes n'en auront probablement pas. Linq, lui il en sait rien.

Donc autant remplacer un List<T> Par un T[] ou autre Stack<T> te fera peut-être gagner ou perdre quelques cycles CPU dans certains cas extrêmes, autant ne pas parcourir l'intégralité de la liste à chaque recherche dedans par exemple, ça te divisera par 2, 3, ou même 1000 les temps de traitements.

[Benbout]

Merci pour vos réponses, ces conseils sont très utiles.

@stringbuilder Je suis encore débutant .net, je pensais tout de meme que c'était assez bien optimisé à ce niveau. Ce que vous décrivez est aussi le cas pour une requete de type firstordefault ?

Dans tout les cas vous avez raisons, d'autant plus que je n'ai pas énormémment de type d objets à faire persister dans une base de données (car la plupart d'entre eux n'ont aucune valeur pour un partage entre mon serveur de jeu et mon serveur web). Je vais donc surement faire ce que vous me conseillez, pratiquer des requetes manuelles pour les échanges avec la bdd, et pour le reste, surement créer un storage protobuf. Merci !

[jcdentons]

Bonjour,

A noter que si vous souhaitez conserver le code Linq, il est possible de l'utiliser sur des Vues, qui seront elles indexées par exemple, ou encore de combiner avec l'appel de procédures stockées qui optimiseraient la recherche.