J'ai 2 colonnes d'entiers délimités par des tabulations, dont la première est un entier aléatoire, la seconde un entier identifiant le groupe, qui peut être généré par ce programme. ( generate_groups.cc)
#include <cstdlib>
#include <iostream>
#include <ctime>
int main(int argc, char* argv[]) {
int num_values = atoi(argv[1]);
int num_groups = atoi(argv[2]);
int group_size = num_values / num_groups;
int group = -1;
std::srand(42);
for (int i = 0; i < num_values; ++i) {
if (i % group_size == 0) {
++group;
}
std::cout << std::rand() << '\t' << group << '\n';
}
return 0;
}J'utilise ensuite un deuxième programme ( sum_groups.cc) pour calculer les sommes par groupe.
#include <iostream>
#include <chrono>
#include <vector>
// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
for (size_t i = 0; i < n; ++i) {
p_out[p_g[i]] += p_x[i];
}
}
int main() {
std::vector<int> values;
std::vector<int> groups;
std::vector<int> sums;
int n_groups = 0;
// Read in the values and calculate the max number of groups
while(std::cin) {
int value, group;
std::cin >> value >> group;
values.push_back(value);
groups.push_back(group);
if (group > n_groups) {
n_groups = group;
}
}
sums.resize(n_groups);
// Time grouped sums
std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
for (int i = 0; i < 10; ++i) {
grouped_sum(values.data(), groups.data(), values.size(), sums.data());
}
std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
std::cout << (end - start).count() << std::endl;
return 0;
}Si je lance ensuite ces programmes sur un ensemble de données de taille donnée, puis mélangez l'ordre des lignes du même ensemble de données, les données mélangées calculent les sommes ~ 2x ou plus rapidement que les données ordonnées.
g++ -O3 generate_groups.cc -o generate_groups
g++ -O3 sum_groups.cc -o sum_groups
generate_groups 1000000 100 > groups
shuf groups > groups2
sum_groups < groups
sum_groups < groups2
sum_groups < groups2
sum_groups < groups
20784
8854
8220
21006Je m'attendais à ce que les données d'origine triées par groupe aient une meilleure localisation des données et soient plus rapides, mais j'observe le comportement opposé. Je me demandais si quelqu'un pouvait en faire l'hypothèse?
la source
.at()ou un mode de débogageoperator[]qui fait des limites vérifier que vous verriez.sum. Au lieu desums.reserve(n_groups);vous, vous devez appelersums.resize(n_groups);- c'est ce que @Shawn faisait allusion.p_out[p_g[i]] += p_x[i];. Peut-être que dans l'ordre brouillé d'origine, les groupes présentent en fait un bon regroupement en ce qui concerne l'accès aup_outtableau. Le tri des valeurs peut entraîner un mauvais modèle d'accès indexé sur le groupep_out.Réponses:
Installer / ralentir
Tout d'abord, le programme s'exécute à peu près au même moment, peu importe:
La plupart du temps est passé dans la boucle d'entrée. Mais puisque nous sommes intéressés par le
grouped_sum(), ignorons cela.Changer la boucle de référence de 10 à 1000 itérations
grouped_sum()commence à dominer le temps d'exécution:perf diff
Maintenant, nous pouvons utiliser
perfpour trouver les endroits les plus chauds de notre programme.Et la différence entre eux:
Plus de temps
main(), ce qui a probablementgrouped_sum()marqué. Génial, merci beaucoup, perf.perf annoter
Y a-t-il une différence dans l'endroit où le temps est passé à l' intérieur
main()?Mélangé:
Trié:
Non, ce sont les deux mêmes instructions qui dominent. Ils prennent donc beaucoup de temps dans les deux cas, mais sont encore pires lorsque les données sont triées.
perf stat
D'accord. Mais nous devrions les exécuter le même nombre de fois, donc chaque instruction doit ralentir pour une raison quelconque. Voyons voir ce qui se
perf statdit.Une seule chose ressort: les cycles bloqués-frontend .
D'accord, le pipeline d'instructions est au point mort. Dans le frontend. Exactement ce que cela signifie varie probablement entre les microarchictectures.
J'ai une supposition, cependant. Si vous êtes généreux, vous pourriez même appeler cela une hypothèse.
Hypothèse
En triant l'entrée, vous augmentez la localité des écritures. En fait, ils seront très locaux; presque tous les ajouts que vous effectuez écriront au même emplacement que le précédent.
C'est super pour le cache, mais pas super pour le pipeline. Vous introduisez des dépendances de données, empêchant la prochaine instruction d'ajout de continuer jusqu'à ce que l'ajout précédent soit terminé (ou a autrement rendu le résultat disponible pour les instructions suivantes )
C'est ton problème.
Je pense.
Le réparer
Vecteurs de somme multiples
En fait, essayons quelque chose. Que se passerait-il si nous utilisions plusieurs vecteurs de somme, en basculant entre eux pour chaque ajout, puis en les additionnant à la fin? Cela nous coûte un peu de localité, mais devrait supprimer les dépendances de données.
(le code n'est pas joli; ne me jugez pas, internet !!)
(oh, et j'ai également corrigé le calcul de n_groups; il était désactivé par un.)
Résultats
Après avoir configuré mon makefile pour donner un
-DNSUMS=...argument au compilateur, je pourrais faire ceci:Le nombre optimal de vecteurs de somme dépendra probablement de la profondeur du pipeline de votre CPU. Mon processeur ultrabook âgé de 7 ans peut probablement maximiser le pipeline avec moins de vecteurs qu'un nouveau processeur de bureau de luxe aurait besoin.
De toute évidence, plus n'est pas nécessairement mieux; quand je suis devenu fou avec 128 vecteurs de somme, nous avons commencé à souffrir davantage de ratés de cache - comme en témoigne l'entrée mélangée devenant plus lente que triée, comme vous l'aviez prévu à l'origine. Nous avons bouclé la boucle! :)
Somme par groupe dans le registre
(cela a été ajouté dans une édition)
Agh, ballot snipé ! Si vous savez que votre entrée sera triée et que vous recherchez encore plus de performances, la réécriture suivante de la fonction (sans tableau de somme supplémentaire) est encore plus rapide, au moins sur mon ordinateur.
L'astuce dans celui-ci est qu'il permet au compilateur de conserver la
gsumvariable, la somme du groupe, dans un registre. Je suppose (mais peut-être très mal) que cela est plus rapide car la boucle de rétroaction dans le pipeline peut être plus courte ici et / ou moins d'accès à la mémoire. Un bon prédicteur de branche rend le contrôle supplémentaire de l'égalité de groupe bon marché.Résultats
C'est terrible pour une entrée mélangée ...
... mais est environ 40% plus rapide que ma solution "plusieurs sommes" pour une entrée triée.
Beaucoup de petits groupes seront plus lents que quelques grands, donc que ce soit ou non la mise en œuvre la plus rapide dépendra vraiment de vos données ici. Et, comme toujours, sur votre modèle de processeur.
Vecteurs de sommes multiples, avec décalage au lieu de masquer les bits
Sopel a proposé quatre ajouts déroulés comme alternative à mon approche de masquage de bits. J'ai implémenté une version généralisée de leur suggestion, qui peut gérer différentes
NSUMS. Je compte sur le compilateur qui déroule la boucle interne pour nous (ce qu'il a fait, au moins pourNSUMS=4).Résultats
Il est temps de mesurer. Notez que depuis que je travaillais dans / tmp hier, je n'ai pas exactement les mêmes données d'entrée. Par conséquent, ces résultats ne sont pas directement comparables aux précédents (mais probablement assez proches).
Oui, la boucle interne avec
NSUMS=8est la plus rapide de mon ordinateur. Par rapport à mon approche "gsum local", elle a également l'avantage supplémentaire de ne pas devenir terrible pour l'entrée mélangée.Intéressant à noter:
NSUMS=16devient pire queNSUMS=8. Cela pourrait être dû au fait que nous commençons à voir plus de ratés de cache, ou parce que nous n'avons pas suffisamment de registres pour dérouler correctement la boucle interne.la source
perf.Voici pourquoi les groupes triés sont plus lents que les groupes non enregistrés;
Voici d'abord le code assembleur pour la boucle de sommation:
Regardons l'instruction d'ajout qui est la principale raison de ce problème;
Lorsque le processeur exécute d'abord cette instruction, il émet une demande de lecture (chargement) en mémoire à l'adresse dans edx, puis ajoute la valeur ecx, puis émet une demande d'écriture (stockage) pour la même adresse.
il y a une fonction dans la réorganisation de la mémoire de l'appelant du processeur
et il y a une règle
Donc, si la prochaine itération atteint l'instruction add avant la fin de la demande d'écriture, elle n'attendra pas si l'adresse edx est différente de la valeur précédente et émet la demande de lecture et elle est réorganisée sur l'ancienne demande d'écriture et l'instruction add continue. mais si l'adresse est la même, l'instruction add attendra que l'ancienne écriture soit terminée.
Notez que la boucle est courte et que le processeur peut l'exécuter plus rapidement que le contrôleur de mémoire ne termine la demande d'écriture dans la mémoire.
ainsi, pour les groupes triés, vous lirez et écrirez à partir de la même adresse plusieurs fois de suite afin de perdre l'amélioration des performances à l'aide de la réorganisation de la mémoire; en attendant, si des groupes aléatoires sont utilisés, chaque itération aura probablement une adresse différente, de sorte que la lecture n'attendra pas une écriture plus ancienne et sera réorganisée avant elle; ajouter une instruction n'attendra pas la précédente pour continuer.
la source