std::pair<int, int> vs struct avec deux int
Dans un ACM exemple, j'ai dû construire une grande table de programmation dynamique. J'ai eu de stocker deux entiers dans chaque cellule, j'ai donc décidé d'aller pour une std::pair<int, int>. Toutefois, l'allocation d'un large éventail d'entre eux a pris 1,5 secondes:
std::pair<int, int> table[1001][1001];Par la suite, j'ai changé ce code pour
struct Cell {
int first;
int second;
}
Cell table[1001][1001];et l'allocation a 0 secondes.
Ce qui explique cette énorme différence dans le temps?
- Je crois que tu veux dire ACM celui-ci.
- Avez-vous tester avec les optimisations activées?
- Quelle est la performance si vous ajoutez un non-arg constructeur de
Cell? - optimisations où activé sur le juge serveur. (pensez que j'ai entendu O3)
- Par clang (900.0.39.2), il prend en 0.007 s avec
-O0, 2e-07 s avec-O3. Par gcc (8.1), il faut 0.005 s avec-O0, 0 s avec-O3. Cette question devient invalide que le temps passe?
Vous devez vous connecter pour publier un commentaire.
std::pair<int, int>::pair()constructeur initialise les champs avec les valeurs par défaut (zéro en cas deint) et votrestruct Celln'est pas (puisque vous n'avez généré automatiquement constructeur par défaut qui ne fait rien).Initialisation nécessite l'écriture de chaque champ qui nécessite tout un tas d'accès à la mémoire qui sont relativement beaucoup de temps. Avec
struct Cellrien n'est fait, au lieu de ne rien faire et est un peu plus rapide.pairconstructeur ne délègue aux constructeurs de son (POD) membres. Un compilateur pourrait (et à mon humble avis, doit) le reconnaître, éluder l'appel du constructeur et simplement à zéro de la mémoire. L'analyse pour ce faire, ne sauraient être dur?std::pairest à blâmer pour la performance? J'ai tendance à utiliser la paire lorsqu'il en fait un code plus lisible, mais c'est me faire reconsidérer....Cell(): first(), second() {}? Il doit prendre la même 1,5 s, si le constructeur est à blâmer.firstetseconddestruct Cellseront initialisées à zéro, précisément parce que le constructeur est généré automatiquement.Les réponses jusqu'à présent de ne pas expliquer l'ampleur du problème.
Acéré comme l'a souligné, la paire de solution initialise les valeurs à zéro. Comme Lemurik souligné, la paire la solution n'est pas seulement de l'initialisation d'un bloc contigu de mémoire, c'est plutôt l'appel de la paire constructeur pour chaque élément dans le tableau. Cependant, même ce qui ne veut pas qu'il compte prendre 1,5 secondes. Quelque chose d'autre se passe.
Voici ma logique:
En supposant que vous étiez sur une ancienne machine, dire en cours d'exécution à 1,33 ghz, puis 1,5 secondes est 2e9 cycles d'horloge. Vous avez 2e6 paires de construire, donc, en quelque sorte chaque paire constructeur est de prendre 1000 cycles. Il ne prend pas 1000 cycles pour appeler un constructeur qui vient de deux nombres entiers à zéro. Je ne vois pas comment le cache en ferait-il autant de temps. Je crois que si le nombre était de moins de 100 cycles.
J'ai pensé qu'il serait intéressant de voir où ailleurs, tous ces cycles CPU va. J'ai utilisé le crappiest plus ancien compilateur C++ que j'ai pu trouver pour voir si je pouvais atteindre le niveau de gaspillage nécessaire. Ce compilateur a été VC++ v6. En mode debug, il fait quelque chose que je ne comprends pas. Il a une grande boucle qui appelle la paire constructeur pour chaque élément dans la table juste assez. Que constructeur, les deux valeurs à zéro juste assez. Mais juste avant de faire cela, il définit tous les octets de 68 octets de la région de 0xcc. Cette région est, juste avant le début de la grande table. Il remplace ensuite le dernier élément de cette région avec 0x28F61200. Chaque appel de la paire constructeur répète cette. Sans doute c'est une sorte de tenue de livres par le compilateur afin qu'il sache les régions sont initialisés lors de la vérification de pointeur erreurs au moment de l'exécution. J'aimerais savoir exactement ce que c'est pour.
De toute façon, qui pourrait expliquer où le temps s'en va. Évidemment, un autre compilateur ne peut pas être mauvais. Et certainement une version optimisée de construire ne serait pas.
Je suppose que c'est la façon dont std::pair est créé. Il n'y a plus de surcharge lors de l'invocation d'une paire constructeur 1001x1001 fois que lorsque vous venez d'allouer une plage de mémoire.
Ce sont toutes de très bonnes approximations, mais comme tout le monde le sait, devine ne sont pas fiables.
Je dirais au hasard des mettre en pause au sein de 1.5 secondes, mais vous devez être assez rapide. Si vous augmenté chaque dimension par un facteur de 3, vous pouvez le faire tenir plus de 10 secondes, de sorte qu'il serait plus facile pour faire une pause.
Ou, vous pourriez obtenir dans un débogueur, casser de la paire, le code du constructeur, puis seule étape pour voir ce qu'il fait.
De toute façon, vous obtiendrez une réponse ferme et définitive à la question, pas juste une supposition.
c'est vraiment un bon exemple, à propos de l'un devrait écrire du C++ et de l'utilisation de la STL avec soin. toutes les pensées?
mon projet est de travailler sur un C&C++ niveau de code de référence de l'outil de test dans lequel nous allons faire beaucoup d'exemples de code trouvé ce qu'est le "bon" code et ce qu'est une "mauvaise" habitude de codage. voir http://effodevel.googlecode.com pour en savoir plus sur C9B.M. de la planification. quelqu'un si vous aviez connu beaucoup de cas de ce genre, merci de bien vouloir joindre au projet pour nous aider.