J'essaie d'optimiser mon code C ++. J'ai recherché Internet sur Internet à l'aide de tableaux C ++ alloués dynamiquement à l'aide de STD :: Vector et ont généralement vu une recommandation en faveur de STD :: Vector et que la différence de performance entre les deux est négligeable. Par exemple, ici - Utiliser des tableaux ou des vecteurs STD :: C ++, quel est l'écart de performance? .
Cependant, j'ai écrit un certain code pour tester les performances d'itération à travers un tableau / vecteur et l'attribution de valeurs aux éléments et j'ai généralement constaté que l'utilisation de tableaux alloués dynamiquement était presque 3 fois plus rapide que d'utiliser des vecteurs (j'ai spécifié une taille pour les vecteurs à l'avance). J'ai utilisé g ++ - 4.3.2.
Cependant, je pense que mon test peut avoir ignoré des problèmes que je ne sais pas pour que je puisse apprécier aucun conseil sur cette question.
merci < / p>
code utilisé -
10 Réponses :
J'imagine la raison pour laquelle vous avez trouvé itération et l'ajout à STD :: Vecteur 3 fois plus lent que un tableau uni est une combinaison du coût d'itération du vecteur et de faire l'assentiment.
edit: strong> p> C'était mon hypothèse initiale avant la TESTCASE; Toutefois, exécutez l'attestation (compilée avec Je ne vois pas comment STD: : Vecteur pourrait être plus rapide (certainement pas 3 fois plus rapide) qu'une copie de la fourchette vanille - je pense que l'optimisation est appliquée sur le code STD :: vecteur compilé de vecteur qui ne se produit pas pour la version Array. P> Benchmark d'origine Résultats: P> std :: vecteur est 3 fois plus rapide. Même référence à nouveau, sauf ajouter une boucle extérieure supplémentaire pour exécuter la boucle d'itérateur de test 1000 fois: p>
$ ./array
Array: 21.7129
Vecteur: 21.6413 P> Li>
std :: vecteur est maintenant ~ la même vitesse que la matrice. p> li>
ul> EDIT 2 STRUT> P> trouvé! Donc, le problème avec votre cas de test est que dans le cas de vecteur, la mémoire de maintien des données apparaît déjà dans le cache de la CPU - soit à la manière dont il est initialisé, ou en raison de l'appel à Cela me donne le résultat suivant: p> -O3 code>) montre que le vecteur de converse - std :: est réellement 3 fois plus rapide, ce qui m'a surpris. P> $ ./array
vector: 0.020875
array: 0.020695
Vec.end () . Si je "réchauffer" le cache de la CPU avant chaque test de synchronisation, je reçois les mêmes numéros pour le tableau et le vecteur: p>
Ce n'est pas non plus sûr. Il ne fait pas que les limites vérifient par défaut.
Peut-être que c'est la mise en cache des adresses de tableau dans le registre de la CPU, raison pour laquelle des courses sont beaucoup plus rapides? J'ai essayé de boucler 2 fois au lieu de 1000 et tandis que la première course a pris 0,06, la deuxième course a pris 0,25
Bien sûr, cela n'explique pas pourquoi le vecteur doit fonctionner à une vitesse optimale dès le début.
@jalf: Je ne me suis pas réalisé que - montre beaucoup récemment que j'ai utilisé std :: Vecteur de la colère! J'ai mis à jour le message pour supprimer l'erreur.
Lors de l'analyse comparative C ++ Comtainers, il est important d'activer la plupart des optimisations du compilateur. Plusieurs de mes propres réponses à ce sujet ont donc châte de cela - par exemple, la fonction appelle les frais généraux lorsque quelque chose comme l'opérateur [] n'est pas inlincé peut être très important.
Pourquoi l'opérateur de l'indice ne serait-il pas entré dans la mesure du possible?
@Catskul en raison d'optimisations étant désactivées.
Sans parler de tous les contrôles itérateurs de débogage, etc. qui sont laissés dans
Le problème semble être que vous avez compilé votre code avec des optimisations désactivées. Sur ma machine, OS X 10.5.7 avec g ++ 4.0.1 Je vois réellement que le vecteur est plus rapide que les tableaux primitifs d'un facteur de 2,5.
avec GCC Essayez de passer -O2 au compilateur et voyez s'il y a une amélioration.
Juste pour le plaisir, essayez d'itération sur le tableau uni à l'aide d'un pointeur au lieu d'un index entier (le code doit ressembler à l'itération de vecteur, car le point d'itérateurs STL doit apparaître comme un pointeur arithmétique pour la plupart des opérations). Je parie que la vitesse sera exactement égale dans ce cas. Ce qui signifie bien sûr que vous devriez choisir le vecteur, car il vous sauvera un monde de maux de tête à partir de matrices de gestion à la main.
La raison pour laquelle votre matrice itération est plus rapide est que le nombre d'itérations est constant et que le compilateur est capable de dérouler la boucle. Essayez d'utiliser RAND pour générer un numéro et plusieurs chiffres pour être un grand nombre que vous vouliez, de sorte que le compilateur ne puisse pas le comprendre au moment de la compilation. Ensuite, essayez à nouveau, vous verrez des résultats similaires d'exécution.
La chose à propos des classes de bibliothèque standard telles que mais qui nécessite une optimisation du compilateur d'être activé. std :: vecteur est que oui, naïvement, c'est beaucoup plus de code qu'un tableau brut. Mais tout cela peut être trivialement inliné par le compilateur, ce qui signifie que si des optimisations sont activées, il devient essentiellement le même code comme si vous avez utilisé un tableau brut. La différence de vitesse n'est alors pas négligeable mais inexistante. Toutes les frais généraux sont enlevés au moment de la compilation.
Je suis d'accord avec Rmeador,
for (int i = 0; vecIt != vecEnd; i++) {
*(vecIt++) = i; // <-- quick offset calculation
}
end = clock();
cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
int* arr = new int[9999999];
start = clock();
for (int i = 0; i < 9999999; i++) {
arr[i] = i; // <-- not fair play :) - offset = arr + i*size(int)
}
Je pense que la réponse ici est évidente: peu importe. Comme Jalf a déclaré que le code finira par être à peu près la même chose, mais même si ce n'était pas, regardez les chiffres. Le code que vous avez affiché crée un énorme tableau de 10 millions d'articles, mais itérant sur l'ensemble de la matrice ne prend que quelques centièmes de seconde.
Même si votre application travaille vraiment avec beaucoup de données, quoi que ce soit Faire avec ces données est susceptible de prendre beaucoup plus de temps que d'itération sur votre tableau. Il suffit d'utiliser la structure de données que vous préférez et concentrez votre temps sur le reste de votre code.
Pour prouver mon point, voici le code avec un changement: l'affectation de I à l'élément de tableau est remplacé par un Affectation de SQRT (I). Sur ma machine en utilisant -O2, l'heure d'exécution triple de 0,02 à 0,06 secondes.
Une des raisons que votre code n'est peut-être pas tout à fait la même chose parce que sur la version de votre std :: vecteur, vous êtes incrimilant deux valeurs, l'entier i code> et le std :: vecteur :: Itérateur Vecit code>. Pour vraiment être équivalent, vous pouvez refroidir à start = clock();
for (int i = 0; i < vec.size(); i++) {
vec[i] = i;
}
end = clock();
cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
Votre code fournit une comparaison injuste entre les deux cas, car vous travaillez beaucoup plus dans le test vectoriel que le test de la matrice.
Avec le vecteur, vous incrémentez à la fois l'itérateur (Vecit) et une variable distincte (I) pour générer les valeurs d'affectation.
avec le tableau, vous n'écrégnez que la variable I et l'utiliser pour le double usage.
Oui, voyons votre code de référence. Souvent, les problèmes de performance avec les conteneurs STL sont duus à l'utilisation.
et assurez-vous que la référence est compilée avec le débogage et les optimisations sur
Je viens de courir votre code de test et j'ai obtenu: $ ./aray vector: 0.021851 Array: 0.059796 Je vois donc la version vectorielle plus rapidement!
@SID - Utilisez le bouton Little-and-Zeros lorsque vous publiez le code de manière à ce qu'il soit formaté correctement.
Les optimisations n'étaient pas activées lors de la compilation. std :: vecteur est plus rapide maintenant. Merci pour l'aide.
@Neil, je pense que votre commentaire est ce qui devrait être la réponse acceptée. Peut-être devriez-vous faire une réponse afin que nous puissions le voter et que SID peut l'accepter. 8v)
Sur ma machine (OS X 10.5.7 g ++ 4.0.1), le code ci-dessus donne des matrices primitives est d'environ 2,5 fois plus lent que les vecteurs.
SID: Il y a vraiment quelque chose d'injuste à propos de votre test - voir mon message ci-dessous - en cours d'exécution de chaque test 100 fois, ils prennent fondamentalement la même heure!
@Sid: OK; Donc, le STD :: Vector Case a déjà des données dans le cache de la CPU, c'est pourquoi il est 3 fois plus rapide. Voir ci-dessous pour plus de détails.
@Dave Rigby: Merci d'avoir souligné la faille dans le test.