Array Performance très similaire à LinkedList – Qu’est-ce qui donne?

Donc, vous testez à quelle vitesse vous pouvez développer un tableau vers une liste chaînée?

Dans les deux cas, vous appelez une fonction d’allocation de mémoire. Généralement, les fonctions d’allocation de mémoire récupèrent une grande partie de la mémoire (peut-être une page) du système d’exploitation, puis la divisent en morceaux plus petits, comme requirejs par votre application.

L’autre hypothèse est que, de temps en temps, realloc () crache le mannequin et alloue une grande quantité de mémoire ailleurs car il ne peut pas y avoir de morceaux contigus dans la page actuellement allouée. Si vous ne faites pas passer d’autres appels à des fonctions d’allocation de mémoire entre votre liste, cela ne se produira pas. Et peut-être que l’utilisation de la mémoire virtuelle par votre système d’exploitation signifie que le segment de votre programme se développe de manière contiguë, indépendamment de l’origine des pages physiques. Dans ce cas, la performance sera identique à un tas d’appels malloc ().

Attendez-vous à ce que les performances changent là où vous mélangez les appels malloc () et realloc ().

Vous avez raison, realloc va simplement augmenter la taille du bloc alloué, sauf si cela est empêché. Dans un scénario réel, vous aurez probablement d’autres objects alloués sur le tas entre les ajouts suivants à la liste? Dans ce cas, realloc devra allouer un tout nouveau bloc de mémoire et copier les éléments déjà présents dans la liste.

Essayez d’allouer un autre object sur le tas en utilisant malloc pour chaque dizaine d’insertions et voyez si elles fonctionnent toujours de la même manière.

En supposant que votre liste liée soit un pointeur sur le premier élément, si vous souhaitez append un élément à la fin, vous devez d’abord parcourir la liste. Ceci est une opération O(n) .

En supposant que realloc doit déplacer le tableau vers un nouvel emplacement, il doit traverser le tableau pour le copier. Ceci est une opération O(n) .

En termes de complexité, les deux opérations sont égales. Cependant, comme d’autres l’ont fait remarquer, realloc évite peut-être de déplacer le tableau, auquel cas l’ajout de l’élément au tableau est O(1) . D’autres ont également souligné que la grande majorité du temps de votre programme est probablement passée dans malloc / realloc , que les deux implémentations appellent une fois par ajout.

Enfin, une autre raison pour laquelle la masortingce est probablement plus rapide est la cohérence du cache et la performance généralement élevée des copies linéaires. Sauter aux adresses erratiques avec des écarts importants entre eux (à la fois les éléments plus grands et la comptabilité malloc ) n’est généralement pas aussi rapide que de faire une copie en bloc du même volume de données.

Les performances d’une solution basée sur des tableaux développée avec realloc() dépendront de votre stratégie pour créer plus d’espace.

Si vous augmentez la quantité d’espace en ajoutant une quantité de stockage fixe à chaque réaffectation, vous obtiendrez une extension qui, en moyenne, dépend du nombre d’éléments stockés dans la baie. Ceci est supposé que realloc devra (occasionnellement) allouer de l’espace ailleurs et copier le contenu, plutôt que d’étendre simplement l’allocation existante.

Si vous augmentez la quantité d’espace en ajoutant une partie de votre nombre actuel d’éléments (le doublement est assez standard), vous vous retrouverez avec une expansion qui prend en moyenne du temps constant.

Le résultat du compilateur sera-t-il très différent dans ces deux cas?

Ce n’est pas une situation réelle. Vraisemblablement, dans la vraie vie, vous êtes intéressé à regarder ou même à supprimer des éléments de vos structures de données et à les append.

Si vous autorisez la suppression, mais uniquement à partir de la tête, la liste chaînée devient meilleure que le tableau car la suppression d’un élément est sortingviale et si au lieu de libérer l’élément supprimé, vous le placez sur une liste libre pour être recyclé, vous pouvez éliminer un Beaucoup de mallocs nécessaires lorsque vous ajoutez des éléments à la liste.

D’autre part, si vous avez besoin d’un access aléatoire à la structure, un tableau bat clairement la liste des liens.

(Mis à jour.) Comme d’autres l’ont noté, s’il n’y a pas d’autres allocations entre reallocs, aucune copie n’est nécessaire. Comme d’autres l’ont noté, le risque de copie de la mémoire diminue (mais aussi son impact bien sûr) sur les très petits blocs, plus petits qu’une page.

De plus, si tout ce que vous faites dans votre test est d’allouer un nouvel espace mémoire, je ne suis pas très surpris que vous voyiez peu de différence, car les appels système pour allouer de la mémoire prennent probablement la plupart du temps.

Choisissez plutôt vos structures de données en fonction de la manière dont vous souhaitez les utiliser. Un framebuffer est par exemple probablement mieux représenté par un tableau contigu.

Une liste chaînée est probablement meilleure si vous devez réorganiser ou sortinger rapidement les données dans la structure.

Ensuite, ces opérations seront plus ou moins efficaces selon ce que vous voulez faire.

(Merci pour les commentaires ci-dessous, je me suis d’abord trompé sur la façon dont ces choses fonctionnent.)

Quelle est la base de votre théorie selon laquelle la liste des liens devrait mieux fonctionner pour les insertions à la fin? Je ne m’attendrais pas à ce que, pour exactement la raison pour laquelle vous avez déclaré. realloc ne copiera que pour maintenir la contiguïté; dans d’autres cas, il peut être nécessaire de combiner des blocs libres et / ou d’augmenter la taille du bloc.

Cependant, chaque nœud de liste lié nécessite une nouvelle allocation et (en supposant une liste à double lien) deux écritures. Si vous voulez savoir comment fonctionne realloc , vous pouvez simplement comparer le pointeur avant et après realloc . Vous devriez trouver que cela ne change généralement pas.

Je soupçonne que puisque vous appelez realloc pour chaque élément (évidemment pas en production), l’appel realloc / malloc est le plus gros goulot d’étranglement pour les deux tests, même si realloc ne fournit souvent pas de nouveau pointeur.

En outre, vous confondez le segment de mémoire et le segment de données. Le tas est l’endroit où la mémoire malloced vit. Le segment de données concerne les variables globales et statiques.