Les performances du code concurrent utilisant dispatch_group_async sont BEAUCOUP plus lent que la version mono-thread

J'ai récemment fait des expériences sur l'utilisation de nombres randoms pour générer des courbes en cloche "à dissortingbution normale".

L'approche est simple:

Créer un tableau d'entiers et le mettre à zéro. (J'utilise 2001 entiers)
Calculer à plusieurs resockets des index dans ce tableau et indexer cette input dans le tableau, comme suit
- Boucle soit 999 ou 1000 fois. À chaque itération:
  - Seed un index de tableau avec la valeur centrale (1000)
  - Générer un nombre random = + 1 / -1. et ajoutez-le à l'index du tableau
  - à la fin de la boucle, incrémentez la valeur à l'index du tableau calculé.

Comme les valeurs randoms 0/1 ont tendance à se produire aussi souvent, la valeur de l'indice final de la boucle interne ci-dessus tend à restr proche de la valeur centrale. Les valeurs d'index beaucoup plus grandes / plus petites que la valeur de départ sont de plus en plus inhabituelles.

Après un grand nombre de répétitions, les valeurs du tableau prennent la forme d'une courbe en cloche de dissortingbution normale. Cependant, la fonction random de haute qualité arc4random_uniform () que j'utilise est assez lente, et il faut BEAUCOUP d'itérations pour générer une courbe régulière.

Je voulais tracer 1 000 000 000 (un milliard) de points. En cours d'exécution sur le fil principal, cela prend environ 16 heures.

J'ai décidé de réécrire le code de calcul pour utiliser dispatch_async, et l'exécuter sur mon Mac Pro 8 cœurs.

J'ai fini par utiliser dispatch_group_async () pour soumettre 8 blocks, avec un dispatch_group_notify () pour notifier le programme quand tous les blocs ont fini de traiter.

Pour simplifier le premier passage, tous les 8 blocs écrivent dans le même tableau de valeurs NSUInteger. Il y a une petite chance d'une condition de concurrency sur une écriture de lecture / modification à l'une des inputs du tableau, mais dans ce cas, cela entraînerait simplement la perte d'une valeur. Je prévoyais d'append un verrou à l'incrément de tableau plus tard (ou peut-être même de créer des arrays séparés dans chaque bloc, puis de les additionner après.)

Quoi qu'il en soit, j'ai refactorisé le code pour utiliser dispatch_group_async () et calculer 1/8 des valeurs totales dans chaque bloc, et mettre mon code à l'arrêt. À mon avis, le code concurrent, tout en maximisant tous les cœurs sur mon Mac, fonctionne BEAUCOUP plus lent que le code monothread.

Quand je cours sur un seul thread, j'obtiens environ 17 800 points par seconde. Lorsqu'il est exécuté à l'aide de dispatch_group_async, la performance chute à plus de 665 points / seconde, soit environ 1/26 aussi vite . J'ai modifié le nombre de blocs que je soumets – 2, 4 ou 8, cela n'a pas d'importance. La performance est horrible. J'ai aussi essayé de soumettre simplement les 8 blocs en utilisant dispatch_async sans dispatch_group. Cela n'a pas d'importance non plus.

Il n'y a actuellement aucun blocage / locking en cours: tous les blocs fonctionnent à pleine vitesse. Je suis complètement mystifié de savoir pourquoi le code concurrent s'exécute plus lentement.

Le code est un peu confus maintenant parce que je l'ai refactorisé pour travailler soit seul-thread ou simultanément afin que je puisse tester.

Voici le code qui exécute les calculs:

randCount = 2; #define K_USE_ASYNC 1 #if K_USE_ASYNC dispatch_queue_t highQ = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0); //dispatch_group_async dispatch_group_t aGroup = dispatch_group_create(); int totalJobs = 8; for (int i = 0; i<totalJobs; i++) { dispatch_group_async(aGroup, highQ, ^{ [self calculateNArrayPoints: KNumberOfEnsortinges /totalJobs usingRandCount: randCount]; }); } dispatch_group_notify(aGroup, dispatch_get_main_queue(), allTasksDoneBlock ); #else [self calculateNArrayPoints: KNumberOfEnsortinges usingRandCount: randCount]; allTasksDoneBlock(); #endif

Et la méthode de calcul commune, qui est utilisée à la fois par la version mono-thread et la version simultanée:

 + (void) calculateNArrayPoints: (NSInteger) pointCount usingRandCount: (int) randCount; { int entry; int random_index; for (entry =0; entry<pointCount; entry++) { static int processed = 0; if (entry != 0 && entry%100000 == 0) { [self addTotTotalProcessed: processed]; processed = 0; } //Start with a value of 1000 (center value) int value = 0; //For each entry, add +/- 1 to the value 1000 times. int limit = KPinCount; if (randCount==2) if (arc4random_uniform(2) !=0) limit--; for (random_index = 0; random_index<limit; random_index++) { int random_value = arc4random_uniform(randCount); /* if 0, value-- if 1, no change if 2, value++ */ if (random_value == 0) value--; else if (random_value == randCount-1) value++; } value += 1000; _bellCurveData[value] += 1; //printf("\n\nfinal value = %d\n", value); processed++; } }

Ceci est un projet d'apprentissage rapide et sale. Il fonctionne à la fois sur Mac et iOS, il utilise donc une class d'utilitaires partagés. La class utilities n'est rien d'autre que des methods de class. Il n'y a aucune instance de la méthode utilitaires créée. Il a un nombre embarrassant de variables globales. Si je finis par faire quelque chose d'utile avec le code, je vais le refactoriser pour créer un singleton utilitaires, et convertir tous les globals en variables d'instance sur le singleton.

Pour l'instant, cela fonctionne, et l'utilisation hideuse de globals n'affecte pas le résultat, donc je le quitte.

Le code qui utilise la variable "traitée" est juste un moyen de déterminer combien de points ont été calculés en mode simultané. J'ai ajouté ce code après que j'ai découvert la performance horrible de la version simultanée, donc je suis confiant que ce n'est pas une cause du ralentissement.

Je suis perplexe ici. J'ai écrit une bonne quantité de code concurrent, et cette tâche est un problème " embarrassingly parallèle ", donc il n'y a aucune raison pour qu'elle ne tourne pas à plein régime sur tous les cœurs disponibles.

Est-ce que quelqu'un d'autre voit quelque chose qui pourrait causer cela, ou avoir d'autres idées à offrir?

arc4random utilise une section critique en modifiant son état. La section critique est super-rapide dans le cas non-contesté (en passant de déverrouillé à verrouillé), mais dans le cas contentieux (en essayant de verrouiller un mutex qui est déjà verrouillé) il doit appeler le operating system et mettre le fil dormir, ce qui diminue beaucoup la performance.

 u_int32_t arc4random() { u_int32_t rnd; THREAD_LOCK(); arc4_check_init(); arc4_check_stir(); rnd = arc4_getword(&rs); THREAD_UNLOCK(); return (rnd); }

où THREAD_LOCK() est défini comme

 #define THREAD_LOCK() \ do { \ if (__isthreaded) \ _pthread_mutex_lock(&arc4random_mtx); \ } while (0)

Source: Générateur de nombres randoms Arc4 pour OpenBSD

pour le rendre plus rapide

vous pouvez créer une class Arc4Random qui est un wrapper autour des fonctions arc4_ * statiques de arc4random.c. Ensuite, vous avez un générateur de nombres randoms qui n'est plus threadsafe, mais vous pouvez créer un générateur pour chaque thread.

C'est de la spéculation, donc je ne peux pas le confirmer d'une manière ou d'une autre sans réellement profiler le code (comme il se passe).

Cela dit, les serrures arc4random pour chaque appel, en passant par la collection de code source d'Apple . Comme vous utilisez arc4random_uniform potentiellement sur plusieurs threads, vous appelez cela au less une fois, voire plusieurs fois. Donc ma meilleure estimation ici est simplement que chaque tâche attend les appels de toutes les autres tâches à arc4random_uniform (ou _uniform peut être à son tour en attente sur lui-même si plusieurs appels sont lancés en parallèle et plusieurs appels à arc4random sont nécessaires).

La solution la plus simple consiste à simplement extraire le code source arc4random.c existant et à le modifier pour qu'il soit enveloppé dans une class tout en supprimant la synchronisation (comme je l'ai suggéré dans le chat, ou comme Michael l'a suggéré) ou pour utiliser le stockage local des threads (cela résout le problème de security des threads mais peut être tout aussi lent – ne l'ai pas essayé moi-même, donc montagne de sel). Gardez à l'esprit que si vous utilisez l'une ou l'autre route, vous aurez besoin d'une alternative pour accéder à /dev/random sur iOS. Je recommand d'utiliser SecRandomCopyBytes dans ce cas, car il devrait donner les mêmes résultats ou des résultats aussi bons que lire /dev/random .

Donc, bien que je sois presque sûr que c'est à arc4random , je ne peux pas dire avec certitude sans profilage, car il peut y avoir d'autres problèmes de performances avant arc4random commence à faire les choses.

Ok, merci à Michael et Noël pour vos réponses réfléchies.

En effet, il semble que arc4random () et arc4random_uniform () utilisent une variante d'un spin_lock, et les performances sont horribles dans l'utilisation multi-thread.

Il est logique qu'un spin-lock soit un très mauvais choix dans un cas où il y a beaucoup de collisions, car un spin-lock provoque le blocage du thread jusqu'à ce que le verrou soit libéré, ce qui lient ce kernel.

L'idéal serait de créer ma propre version d'arc4random qui maintient son propre tableau d'état dans les variables d'instance et qui n'est pas sûr pour les threads serait probablement la meilleure solution. Je voudrais ensuite refactoriser mon application pour créer une instance distincte de mon générateur random pour chaque thread.

Cependant, c'est un projet parallèle pour ma propre search. C'est plus d'effort que je suis prêt à dépenser si je ne suis pas payé.

Comme expérience, j'ai remplacé le code par rand (), et le cas monothread est un peu plus rapide, puisque rand () est un algorithm plus simple et plus rapide. Les nombres randoms ne sont pas aussi bons non plus. D'après ce que j'ai lu, rand () a des problèmes avec les templates cycliques dans les bits inférieurs, donc au lieu d'utiliser le rand ()% 2 typique, j'ai utilisé rand ()% 0x4000 à la place, pour utiliser le second ordre bit à la place.

Cependant, les performances ont encore diminué considérablement lorsque j'ai essayé d'utiliser rand () dans mon code multithread. Il doit également utiliser le locking interne.

Je suis ensuite passé à rand_r (), qui prend un pointeur vers une valeur de départ, en supposant que puisqu'il est sans état, il n'utilise probablement pas de locking.

Bingo. Je reçois maintenant 415,674 points / seconde sur mon Mac Pro 8 cœurs.