J'ai écrit du code optimisé pour un algorithme qui calcule un vecteur de quantités. Je l'ai acheminé avant et après diverses tentatives d'obtenir les données calculées dans la fonction hors de la fonction. Je pense que la nature spécifique du calcul ou de la nature du vecteur de quantités n'est pas pertinente. Un aperçu du code, des horaires et des détails suivez.
Tous les codes ont été compilés avec les indicateurs suivants: p>
g ++ -wall -wextra -werror -std = c ++ 11 -pedantique -O3
J'ai une classe comme celle-ci: p> et une principale comme ceci: p> ici sont des détails pertinents sur les données: p> Tout cela nécessite exactement 5 minutes et 48 secondes à exécuter. Naturellement, je peux imprimer le tableau dans la fonction de classe et c'est ce que je faisais, mais je vais libérer le code publiquement, et certains cas d'utilisation peuvent inclure de vouloir faire autre chose que l'impression du vecteur. Dans ce cas, je dois modifier la signature de la fonction pour obtenir les données à l'utilisateur. C'est là que le problème se pose. Des choses que j'ai essayées: p> Création d'un vecteur dans la principale et le transmettant en référence: p>
Création d'un vecteur dans la fonction Dowork et le renvoyer, profiter de la sémantique de déplacement.
Comme cela nécessite une allocation dynamique pour chaque résultat, je ne m'attendais pas à ce que cela soit rapide. Étrangement, ce n'est pas beaucoup plus lent. 7 minutes 40 secondes. P> li>
retourner le std :: matrice actuellement à Dowork par la valeur.
Naturellement, cela doit copier les données à leur retour car le tableau de piles ne prend pas en charge la sémantique de déplacement. 7 minutes 30 secondes p> li>
Passer un STD :: Array en référence. P>
while( std::cin >> param1 >> param2 ) {
std::array<unsigned long,40> counts = {{0}};
c.doWork( param1, param2, counts )
}
std::vector<unsigned long> counts( 40 );
while( std::cin >> param1 >> param2 ) {
c.doWork( param1, param2, counts );
std::fill( counts.begin(), counts.end(), 0 );
}
3 Réponses :
Ce que je ferais, c'est la mettre en pause quelques fois et voir ce que cela fait la plupart du temps. En regardant votre code, je soupçonnerais le plus de temps à entrer dans une) la boucle la plus intérieure, en particulier du calcul de l'indice, ou 2) l'allocation du Si la taille de qui alloue sur la pile, qui ne prend pas de temps et Si la taille varie au moment de l'exécution, ce que je fais est une allocation statique, comme ceci: P> std :: tableau code>. comptes code> est toujours 40, je ferais simplement p> Memset code> ne prend pas de temps comparé à tout ce que vous faites. p> void myRoutine(){
/* this does not claim to be pretty. it claims to be efficient */
static int nAlloc = 0;
static long* counts = NULL;
/* this initially allocates the array, and makes it bigger if necessary */
if (nAlloc < /* size I need */){
if (counts) delete counts;
nAlloc = /* size I need */;
counts = new long[nAlloc];
}
memset(counts, 0, sizeof(long)*nAlloc);
/* do the rest of the stuff */
}
Hmm. Soit je suis totalement tort à ce sujet ou de nombreuses personnes ont une idée fausse. N'est-il pas vrai que STD :: Array est un conteneur alloué statiquement sur la pile. Sinon, pourquoi prend-il la taille en tant que paramètre de modèle? Son coût d'allocation devrait être minimal ne devrait-il pas? J'ai essayé Memset et sur toute solution où les données quittent la fonction, il a le même coût élevé (environ 7 minutes 20 secondes). Le code devrait passer la majeure partie de son temps dans les nombreuses branches, les plus nombreuses branches, les déréporences, etc., mais je suppose que selon certains commentaires, je vais essayer de comprendre l'Assemblée.
Gosh, @ryan, pourquoi devinez? Il suffit de l'exécuter sous le débogueur et de la mettre en pause plusieurs fois. Vous pouvez simplement voir quel est le problème.
Remarque côté: si (compte) ne devrait pas être nécessaire, comme Supprimer 0; a défini comportement IIRC. nullptr serait aussi sympa;) peut-être même Memset pourrait être supprimé en faveur de neuf [NALLOC] (); mais je ne suis pas sûr de la performance de ce dernier.
D'accord. Je l'ai couru à travers le GDB dans la forme originale et passez STD :: Array par référence. Dans les deux cas, environ 100 pauses et curriculum vitae illustrent une distribution peu échantillonnée mais apparemment grossièrement uniforme de toutes les stations, il semble donc qu'elles soient exécutées. Comme je continue à dire, le code réel est une série extrêmement complexe de déréférences, d'ajouts, de soustractions, de sous-traits et de branches plus coûteuses. Je crains qu'un grand échantillon ne soit nécessaire d'apprendre grand chose, mais une centaine de chaque façon suggère que tout code est en cours d'exécution. Cela me confond encore plus.
@Ryan: 10 ou 20 est tout ce dont vous avez besoin, mais prenez la peine de comprendre à fond de chaque échantillon. Ce ne sera pas uniforme. Il sera concentré dans la boucle la plus interne. Peut-être perceptible dans la boucle suivante. Là où vous le trouvez, vous pouvez examiner la langue d'assemblage pour voir s'il s'agit de calculer l'indexation de la matrice ou du côté droit de la déclaration. Si cela facilite la tâche, vous pouvez diviser le côté droit de chaque instruction en plusieurs relevés. Cela n'affectera pas la performance. Si vous vous trouvez à l'intérieur d'une routine étrange, recherchez la pile pour voir où il est dans votre code.
@MikeDunlavey En fait, ils n'étaient pas concentrés dans la boucle la plus interne, car pendant que la boucle la plus interne est exécutée le plus souvent, elle contient également les moins d'opérations. Néanmoins, comme je l'ai dit, comme je l'ai révélé des choses intéressantes sur ce que est être exécuté et que je passais ces dernières heures à le faire sentir. Dès que j'atteigne une conclusion, je vais mettre à jour. Merci!
@MikeDunlavey Point bien pris, cependant! Je suppose que je voulais juste dire que je les ai observés proportionnellement aux attentes. Je pense que j'ai suivi la question. Dès que je vérifie, je vais fermer la question.
@Mikedunlavey Cette approche pseudo-profilée a fini par allusion à la question. Le nombre de déclarations peu coûteuses impliquées signifiait cela a pris beaucoup de temps, mais il a commencé à ressembler à des déclarations non exécutées. Pour confirmer cela, j'ai commencé à exécuter des timings, y compris l'impression de sortie à l'intérieur et à l'extérieur de la classe. Celles-ci ont pris 10 minutes 30 à 50 secondes en fonction de l'approche. Comme il s'est avéré, les approches différentes pour obtenir les données étaient aussi bon marché que celles-ci (et nous tous). Le compilateur effectuait des optimisations vraiment sélectives sur le code qu'il détectées n'avait aucun effet.
@RYAN: Vous devriez trouver un petit nombre d'échantillons manuels pointant directement au problème. Il est nécessaire de comprendre de manière approfondie chaque échantillon, de connaître précisément ce qu'il fait à l'heure de l'échantillon et la pleine raison pour laquelle il le fait. Je le fais d'abord avec l'optimiseur éteint, la raison étant que si je fais quelque chose de mal, il est plus facile de voir de cette façon. Ensuite, j'allume l'optimiseur après que je suis sûr que j'ai nettoyé tous les trucs stupides.
Les optimisations du compilateur sont un endroit à regarder, mais il y a un endroit de plus que vous devez regarder. Les modifications que vous avez faites dans le code peuvent perturber la mise en page du cache. Si la mémoire allouée à la matrice est dans une autre partie de la mémoire à chaque fois, le nombre de cache manque dans votre système peut augmenter, ce qui dégrade à son tour les performances. Vous pouvez jeter un coup d'œil à des compteurs de performance matériels sur votre CPU pour faire une meilleure estimation à ce sujet.
Intéressant. Cela m'avait eu lieu, mais j'ai supposé que la pénalité de coûts ne pouvait pas prendre en compte une pénalité de 25% dans une procédure aussi complexe. Je vais essayer d'examiner cela.
Il y a des moments où les solutions peu orthodoxes sont applicables, ce qui peut être un. Avez-vous envisagé de faire le tableau un groupe mondial?
Néanmoins, le seul avantage crucial que les variables locales sont que l'optimiseur peut trouver tout accès à celui-ci, en utilisant uniquement des informations de la fonction. Qui rend l'affectation du registre un beaucoup plus facile.
A statique variable à l'intérieur de la fonction est presque de la même manière, mais dans votre cas, l'adresse de ce réseau de piles s'échapperait, battant à nouveau l'optimiseur.
Est-ce que des données dépendent des données calculées précédentes? Sinon, vous voudrez peut-être diviser le calcul en quelques threads, où chaque thread fonctionne sur une partie de l'ensemble de données.
Quelle est la taille de la taille de vecteur totale? Comme dans, combien d'octets?
Quelle est la taille de votre
comptes tableau? Est-ce vraiment seulement 40 éléments (ce qui devrait prendre un peu de temps à copier)? Je vois un& compte [1156] dans votre code commenté.Quelle est la différence entre le démontage pour les cas?
Juste une supposition. Le compilateur pourrait dérouler certaines boucles. Dans le cas où vous avez
Array défini à l'intérieur de la fonction et si vos boucles, disent, à partir de0 àarray.Size () , le compilateur pourrait être capable de le faire. Lorsque vous passezArray & en tant que paramètre, Compiler n'a aucune idée de quelle taille il aura et ne peut pas dérouler les boucles ... C'est une supposition, vous devez vérifier le code émis par le compilateur dans les deux cas.Et si vous passez un pointeur sur un tableau comme un argument, mais gardez le tableau local pour faire le travail réel? Ensuite, à la fin, copiez la matrice locale au pointeur fourni si ce n'est pas NULL.
@Vaughncato +1, bonne suggestion.
@ Joochim Aucune itération de la boucle n'est entièrement indépendante et je ferai certainement des provisions pour le parallementer une fois que les aspects du calcul série sont optimisés, mais je ne suis pas encore prêt pour cette étape.
@Xymostech il y a 40 éléments (corrigés ci-dessus). La taille est 40 * taille de taille (non signée) = 320 octets sur ma machine.
@Petrbudnik Le compilateur connaît la taille de la matrice de toute façon (pas dans le vecteur case) car STD :: Array prend sa taille comme un argument de modèle. Il n'y a pas de boucles sur la matrice, à l'exception de la sortie commentée à Dowork (non incluse dans les horaires de profil).
@VaughnCato n'est pas (presque) équivalent fonctionnellement à la transmission d'un STD: tableau par référence (qui est l'un des articles que j'ai essayés, montré dans une balle), la seule différence éventuellement une déréférence supplémentaire pour les accès. C'est tellement bon marché et apparaît si rarement dans mon code par rapport à l'autre travail, qu'il ne pouvait certainement pas tenir compte de la différence énorme de temps?
@ Ryann.lichtenwalter non, je ne pense pas que vous corrigez ici. Si
Array est une variable locale de la fonction, le compilateur peut optimiser le code en fonction de celle-ci - la taille ne change jamais dans la fonction. SiArray est transmis sous forme de paramètre, le compilateur ne peut pas utiliser la taille comme optimisation du code de fonction - il doit émettre un code générique qui fonctionnera avec touttableau s de leur taille ... Une fois encore, avez-vous comparé démontage? Pour rendre les choses évidentes, interdire les optimisations et les temps de comparer les deux versions sans optimisations.Existe-t-il une opération moins cher que l'impression coûteuse de la matrice que le compilateur est garantie de ne pas optimiser l'optimisation? Ensuite, je le fais dans la version originale du code, assurez-vous que l'opération est triviale et ne comptabilise pas 1 minute 30 secondes de temps et découvrez si les optimisations nécessaires sont optimisées autrement. Je pouvais certainement regarder l'assemblée, mais le code actuel est extrêmement complexe, c'est pourquoi il n'est pas tout affiché ici, et je ne suis pas convaincu que je peux l'aligner bien après une sortie optimisée.
@Petrbudnik Selon EN.CPPREFERFERATION.COM/W/CPP/Container/array, STD :: Array est un conteneur de taille constante avec une taille définie au moment de la compilation. Si STD :: Array & est transmis sous forme de paramètre, comment le compilateur peut-il ne pas savoir la taille?
Avez-vous essayé d'utiliser des itérateurs? (Pour
vecteur s,redimensionner avant de les transmettre, bien sûr.)std :: Distance peut vous indiquer la taille de la gamme fin début (Stockez cela dans unconst ). Bien sûr, cela n'adresse pas la boucle déroulante à cause des itérations connues (taille du tableau). Vous pouvez également essayer d'écrire un modèle pour couvrir les deux cas 1) Taille connue au moment de la compilation 2) Taille connue uniquement au moment de l'exécution.@ Ryann.lichtenwalter Oui, vous avez raison, bien sûr. Je l'ai mélangé avec votre tentative avec
vecteur ...Il est possible que l'accès à un tableau sur la pile soit plus rapide que d'accéder à celui qui est transmis par référence. Le compilateur en sait plus sur ce qui peut arriver ou peut ne pas arriver à cette mémoire quand elle est sur la pile. Il est possible que cela permet de rester plus dans des registres. Je voudrais essayer et voir.
@Dyp Oui, j'essaye vraiment de dimensionner un vecteur et de passer des itérateurs. Merci pour la suggestion. Cela a donné les mêmes résultats que les autres tentatives. J'ai battu ma tête contre le mur la nuit dernière pendant environ 5 heures d'essayer différentes choses. Tout sauf la déclaration locale du tableau statique, qu'il utilise des données finalement déclarées sur la pile ou sur le tas, prend à peu près au même moment: 7 minutes 20-40 secondes.