std :: pair < int, int > vs struct avec deux int

Question

Dans un exemple ACM, je devais construire un grand tableau pour la programmation dynamique. Je devais stocker deux entiers dans chaque cellule. J'ai donc décidé de choisir std :: pair int . Cependant, l’allocation d’un grand nombre d’entre eux a pris 1,5 seconde:

std::pair<int, int> table[1001][1001];

Ensuite, j'ai changé ce code en

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

et l'attribution a pris 0 secondes.

Qu'est-ce qui explique cette énorme différence de temps?

Answer 1

Le constructeur

std :: pair < int, int > :: pair () initialise les champs avec les valeurs par défaut (zéro en cas de int ) et votre struct Cell ne le fait pas (puisque vous n'avez qu'un constructeur par défaut généré automatiquement qui ne fait rien).

L’initialisation nécessite d’écrire dans chaque champ, ce qui nécessite de nombreux accès à la mémoire, qui prennent relativement beaucoup de temps. Avec struct Cell , rien n’est fait à la place et rien n’est un peu plus rapide.

Answer 2

Les réponses apportées à ce jour n’expliquent pas l’ampleur du problème.

Comme l'a souligné sharptooth, la solution de paire initialise les valeurs à zéro. Comme Lemurik l'a fait remarquer, la solution de paire ne consiste pas seulement à initialiser un bloc de mémoire contigu, mais à appeler le constructeur de la paire pour chaque élément de la table. Cependant, même cela ne prend pas en compte que cela prend 1,5 seconde. Quelque chose d'autre se passe.

Voici ma logique:

En supposant que vous utilisiez une machine ancienne, disons à 1,33 GHz, puis 1,5 seconde correspond à 2e9 cycles d'horloge. Vous avez à construire 2e6 paires, donc chaque constructeur de paires prend 1000 cycles. Il ne faut pas 1 000 cycles pour appeler un constructeur qui définit simplement deux entiers sur zéro. Je ne vois pas comment des erreurs de cache rendraient cela si long. Je le croirais si le nombre était inférieur à 100 cycles.

J'ai pensé qu'il serait intéressant de voir où vont tous ces cycles de traitement. J'ai utilisé le compilateur C ++ le plus désagréable que j'ai trouvé pour voir si je pouvais atteindre le niveau de perte requis. Ce compilateur était VC ++ v6. En mode débogage, cela fait quelque chose que je ne comprends pas. Il a une grosse boucle qui appelle le constructeur de la paire pour chaque élément de la table - assez bien. Ce constructeur définit les deux valeurs sur zéro - assez bien. Mais juste avant cela, tous les octets d'une région de 68 octets sont définis sur 0xcc. Cette région est juste avant le début de la grande table. Il écrase ensuite le dernier élément de cette région avec 0x28F61200. Chaque appel du constructeur de la paire répète ceci. Vraisemblablement, il s'agit d'une sorte de comptabilité tenue par le compilateur afin qu'il sache quelles régions sont initialisées lors de la recherche d'erreurs de pointeur au moment de l'exécution. J'aimerais savoir exactement à quoi cela sert.

Quoi qu'il en soit, cela expliquerait où le temps supplémentaire passe. Évidemment, un autre compilateur n'est peut-être pas si mal. Et certainement, une version optimisée ne le serait pas.

Answer 3

Je suppose que c'est la façon dont std :: pair est créé. Il y a plus de temps système lors de l'appel d'un constructeur de paire 1001x1001 fois que lorsque vous allouez simplement une plage de mémoire.

Answer 4

Ce sont toutes de très bonnes suppositions, mais comme tout le monde le sait, les suppositions ne sont pas fiables.

Je dirais simplement faites une pause dans ce délai de 1,5 seconde, mais vous devrez être assez rapide. Si vous augmentiez chaque dimension d'un facteur d'environ 3, cela pourrait prendre plus de 10 secondes, ce qui faciliterait la pause.

Vous pouvez également l'obtenir sous un débogueur, le décomposer dans le code constructeur de la paire, puis effectuer une étape pour voir ce qu'il fait.

Dans tous les cas, vous obtiendrez une réponse ferme à la question, pas seulement une supposition.

Answer 5

c’est vraiment un bon exemple de ce qu’il faut écrire en C ++ et utiliser STL avec précaution. des pensées?

Mon projet travaille sur un outil de test d'évaluation de performances au niveau du code C & C ++ dans lequel nous allons créer de nombreux exemples de code pour déterminer ce qui est "bon" et "correct". code et qu'est-ce qu'un "mauvais" habitude de codage. voir http://effodevel.googlecode.com pour en savoir plus sur C9B.M. Planification. Si vous avez déjà rencontré beaucoup de cas de ce type, veuillez vous joindre au projet pour nous aider.