Pourquoi la version multithread de ce programme est-elle plus lente?

J’essaie d’apprendre des pthreads et j’ai expérimenté un programme qui essaye de détecter les changements sur un tableau. La fonction array_modifier() choisit un élément aléatoire et bascule sa valeur (1 à 0 et vice versa) puis dort pendant un certain temps (assez grand pour que les conditions de course n’apparaissent pas, je sais que c’est une mauvaise pratique). change_detector() parsing le tableau et lorsqu’un élément ne correspond pas à sa valeur précédente et qu’il est égal à 1, la modification est détectée et le tableau diff est mis à jour avec le délai de détection.

Lorsqu’il y a un change_detector() ( NTHREADS==1 ), il doit parsingr tout le tableau. Lorsqu’il y a plus de threads, chacun se voit atsortingbuer une partie du tableau. Chaque thread détecteur détectera uniquement les modifications dans sa partie de la masortingce, vous devez donc additionner les temps de capture des 4 threads pour obtenir le temps total nécessaire pour capturer tous les changements.

Voici le code:

 #include  #include  #include  #include  #include  #include  #define TIME_INTERVAL 100 #define CHANGES 5000 #define UNUSED(x) ((void) x) typedef struct { unsigned int tid; } parm; static volatile unsigned int* my_array; static unsigned int* old_value; static struct timeval* time_array; static unsigned int N; static unsigned long int diff[NTHREADS] = {0}; void* array_modifier(void* args); void* change_detector(void* arg); int main(int argc, char** argv) { if (argc < 2) { exit(1); } N = (unsigned int)strtoul(argv[1], NULL, 0); my_array = calloc(N, sizeof(int)); time_array = malloc(N * sizeof(struct timeval)); old_value = calloc(N, sizeof(int)); parm* p = malloc(NTHREADS * sizeof(parm)); pthread_t generator_thread; pthread_t* detector_thread = malloc(NTHREADS * sizeof(pthread_t)); for (unsigned int i = 0; i < NTHREADS; i++) { p[i].tid = i; pthread_create(&detector_thread[i], NULL, change_detector, (void*) &p[i]); } pthread_create(&generator_thread, NULL, array_modifier, NULL); pthread_join(generator_thread, NULL); usleep(500); for (unsigned int i = 0; i < NTHREADS; i++) { pthread_cancel(detector_thread[i]); } for (unsigned int i = 0; i tid; const unsigned int start = tid * (N / NTHREADS) + (tid < N % NTHREADS ? tid : N % NTHREADS); const unsigned int end = start + (N / NTHREADS) + (tid < N % NTHREADS); unsigned int r = start; while (1) { unsigned int tmp; while ((tmp = my_array[r]) == old_value[r]) { r = (r < end - 1) ? r + 1 : start; } old_value[r] = tmp; if (tmp) { struct timeval tv; gettimeofday(&tv, NULL); // detection time in usec diff[tid] += (tv.tv_sec - time_array[r].tv_sec) * 1000000 + (tv.tv_usec - time_array[r].tv_usec); } } } 

quand je comstack et exécute comme ceci:

 gcc -Wall -Wextra -O3 -DNTHREADS=1 file.c -pthread && ./a.out 100 

Je reçois:

 665 

mais quand je comstack et exécute comme ceci:

 gcc -Wall -Wextra -O3 -DNTHREADS=4 file.c -pthread && ./a.out 100 

Je reçois:

 152 190 164 242 

(cela se résume à 748).

Ainsi, le délai pour le programme multithread est plus grand.

Mon processeur a 6 kernelx.

Réponse courte Vous partagez la mémoire entre les threads et la mémoire entre les threads est lente.

Réponse longue Votre programme utilise un certain nombre de threads pour écrire dans my_array et un autre thread à lire dans my_array . Effectivement, my_array est partagé par un certain nombre de threads.

Supposons maintenant que vous effectuez une parsing comparative sur une machine multicœur et que vous espériez probablement que le système d’exploitation affectera différents cœurs à chaque thread.

N’oubliez pas que sur les processeurs modernes, écrire dans la RAM coûte très cher (des centaines de cycles de processeur). Pour améliorer les performances, les processeurs disposent de caches à plusieurs niveaux. Le cache le plus rapide est le petit cache L1. Un kernel peut écrire dans son cache L1 dans l’ordre de 2-3 cycles. Le cache L2 peut prendre de l’ordre de 20 à 30 cycles.

Désormais, dans de nombreuses architectures de CPU, chaque cœur a son propre cache L1, mais le cache L2 est partagé. Cela signifie que toutes les données partagées entre les threads (cœurs) doivent passer par le cache L2 qui est beaucoup plus lent que le cache L1. Cela signifie que l’access à la mémoire partagée a tendance à être assez lent.

En bout de ligne, si vous souhaitez que vos programmes multithreads fonctionnent correctement, vous devez vous assurer que les threads ne partagent pas de mémoire. Le partage de mémoire est lent.

A part Ne vous fiez jamais à volatile pour faire le bon choix lors du partage de mémoire entre thread, utilisez les opérations atomiques de votre bibliothèque ou utilisez des mutex. En effet, certains processeurs autorisent des lectures et écritures en panne pouvant faire des choses étranges si vous ne savez pas ce que vous faites.

Il est rare qu’un programme multithread s’adapte parfaitement au nombre de threads. Dans votre cas, vous avez mesuré un facteur d’accélération d’environ 0,9 (665/748) avec 4 fils. Ce n’est pas si bon.

Voici quelques facteurs à considérer:

Les frais généraux liés au démarrage des discussions et à la division du travail. Pour les petits travaux, le coût de démarrage de threads supplémentaires peut être considérablement plus élevé que le travail réel. Non applicable à ce cas, car les frais généraux ne sont pas inclus dans les mesures de temps.

Variations “aléatoires” . Vos threads ont varié entre 152 et 242. Vous devez exécuter le test plusieurs fois et utiliser la valeur moyenne ou la valeur médiane.

La taille du test. Généralement, vous obtenez des mesures plus fiables sur des tests plus volumineux (plus de données). Cependant, vous devez prendre en compte l’impact de la multiplication des données sur la mise en cache du cache L1 / L2 / L3. Et si les données sont trop volumineuses pour tenir dans la RAM, vous devez prendre en compte les E / S du disque. En règle générale, les implémentations multithread sont plus lentes, car elles veulent travailler sur plus de données à la fois, mais elles peuvent parfois être plus rapides, un phénomène appelé accélération super-linéaire .

Overhead causé par la communication inter-thread. Peut-être pas un facteur dans votre cas, puisque vous n’en avez pas beaucoup.

Frais généraux causés par le locking des ressources. Généralement, l’impact sur l’utilisation des processeurs est faible, mais il peut aussi avoir une incidence importante sur le temps réel total utilisé.

Optimisations matérielles. Certains processeurs modifient la fréquence d’horloge en fonction du nombre de cœurs utilisés.

Le coût de la mesure elle-même . Dans votre cas, un changement sera détecté dans les 25 (100/4) itérations de la boucle for . Chaque itération ne prend que quelques cycles d’horloge. Ensuite, vous appelez gettimeofday ce qui coûte probablement des milliers de cycles d’horloge. Vous gettimeofday plus ou moins le coût de l’appel de gettimeofday .

J’augmenterais le nombre de valeurs à vérifier et le coût de vérification de chaque valeur. J’envisagerais également de désactiver les optimisations du compilateur, car elles peuvent amener le programme à faire des choses inattendues (ou à sauter certaines choses complètement)