Pourquoi est-il si lent à parcourir une grande liste std ::?

Question

Comme le titre l’indique, j’ai eu des problèmes avec un de mes programmes où j’utilisais std :: list comme pile et aussi pour parcourir tous les éléments de la liste. Le programme prenait trop de temps lorsque les listes sont devenues très volumineuses.

Quelqu'un at-il une bonne explication à cela? Est-ce un comportement de pile / cache?

(Résolu le problème en changeant les listes std :: vector et std :: deque (une structure de données étonnante au fait) et tout a soudainement été beaucoup plus rapide)

EDIT: Je ne suis pas dupe et je n’ai pas accès aux éléments au milieu des listes. La seule chose que j'ai faite avec les listes était de supprimer / ajouter des éléments à la fin / au début et de parcourir les tous éléments de la liste. Et j'ai toujours utilisé des itérateurs pour parcourir la liste.

Answer 1

Les listes ont une localité de cache terrible (inexistante). Chaque nœud est une nouvelle allocation de mémoire et peut être n'importe où . Ainsi, chaque fois que vous suivez un pointeur d'un nœud à un autre, vous passez à un nouveau lieu, non lié, en mémoire. Et oui, cela nuit beaucoup aux performances. Une perte de mémoire cache peut être deux ordres de grandeur plus lente qu'un résultat de cache. Dans un vecteur ou une deque, pratiquement chaque accès sera un cache hit. Un vecteur est un seul bloc de mémoire contigu, vous pouvez donc l'itérer aussi rapidement que vous le souhaitez. Un deque est composé de plusieurs blocs de mémoire plus petits. Il introduit donc un manque de cache occasionnel, mais ils seront toujours rares et l'itération sera toujours très rapide, car vous obtiendrez principalement des hits en cache.

Une liste contiendra presque toutes les erreurs de cache. Et la performance sera nul.

En pratique, une liste chaînée n’est guère le bon choix du point de vue des performances.

Modifier : Comme l'a souligné un commentaire, les dépendances de données sont un autre problème des listes. Un processeur moderne aime chevaucher les opérations. Mais cela ne peut pas être le cas si l'instruction suivante dépend du résultat de celle-ci.

Si vous parcourez un vecteur, ce n'est pas un problème. Vous pouvez calculer l'adresse suivante à lire à la volée, sans avoir à vous enregistrer en mémoire. Si vous lisez à l'adresse x maintenant, l'élément suivant sera situé à l'adresse x + sizeof (T) où T est le type d'élément. Donc, il n'y a pas de dépendances là-dedans, et la CPU peut commencer à charger immédiatement l'élément suivant, ou celui qui le suit, tout en traitant un élément précédent. Ainsi, les données seront prêtes lorsque nous en aurons besoin, ce qui contribuera à masquer le coût d’accès aux données dans la RAM.

Dans une liste, nous devons suivre un pointeur du noeud i au noeud i + 1 et jusqu'à ce que i + 1 soit chargé, nous ne savons même pas où chercher i + 2 . Nous avons une dépendance à l'égard des données, de sorte que le processeur est obligé de lire les nœuds un à un. Il ne peut pas commencer à lire les nœuds suivants à l'avance, car il ne sait pas encore où ils se trouvent.

Si une liste n’avait pas été constituée d’absence de mémoire cache, le problème n’aurait pas été grave, mais comme nous en avons beaucoup, ces délais sont coûteux.

Answer 2

Cela est dû aux grandes quantités de cache manquantes que vous obtenez lorsque vous utilisez une liste. Avec un vecteur, les éléments environnants sont stockés dans le cache des processeurs.

Answer 3

Consultez le fil de stackoverflow .

Answer 4

Il y a il y a un problème de cache: toutes les données du vecteur sont stockées dans un bloc contigu, et chaque élément de la liste est alloué séparément et peut arriver à être stocké dans un emplacement assez aléatoire de la mémoire, ce qui conduit à plus de cache cache. Cependant, je parie que vous rencontrez l’un des problèmes décrits dans les autres réponses.

Answer 5

La réponse simple est qu'itérer sur un vecteur n'est pas du tout itératif, il commence simplement à la base d'un tableau et lit les éléments l'un après l'autre.

Je vois que c'est marqué C ++, pas C, mais comme ils font la même chose sous les couvertures, il est intéressant de noter que vous pouvez ajouter des éléments au début et à la fin d'un tableau en l'allouant de manière arbitraire, et à realloc (). ing et memmove () entre 2 baies de compagnons si et quand vous manquez de place. Très vite.

L'astuce pour ajouter des éléments au début d'un tableau consiste à biaiser le début logique du tableau en faisant avancer le pointeur dans le tableau au début, puis en le sauvegardant lors de l'ajout d'éléments au premier plan. (aussi la façon dont une pile est implémentée)

De la même manière, C peut être configuré pour prendre en charge les indices négatifs.

C ++ fait tout cela pour vous avec la classe STL de vecteur, mais vous devez vous rappeler ce qui se passe sous la couverture.

Answer 6

[Edit: je suis corrigé. std :: list n'a pas d'opérateur []. Désolé.]

Il est difficile de dire à partir de votre description, mais je suppose que vous essayiez d'accéder aux éléments de manière aléatoire (c'est-à-dire, par index):

for(int i = 0; i < mylist.size(); ++i) { ... mylist[i] ... }

Au lieu d'utiliser les itérateurs:

for(list::iterator i = mylist.begin(); i != mylist.end(); ++i) { ... (*i) ... }

Les deux "vecteur" & amp; " deque " sont bons à accès aléatoire, donc soit va bien fonctionner pour ces types --- O (1) dans les deux cas. Mais " list " n'est pas bon en accès aléatoire. L’accès à la liste par index prendrait un temps O (n ^ 2), par opposition à O (1) lors de l’utilisation d’itérateurs.