Programmation multi-threadée

[newbie06]

Une question de débutant complet en programmation MT...

Tout d'abord le contexte : x86 multi-coeur sous Linux. Imaginons que j'ai un programme P qui balance quelques dizaines de Mo/s qui doivent être analysés ; ce trafic devrait être beaucoup plus élevé, mais on le réduit en permettant au(x) thread(s) d'analyse de lire des données du programme P.

J'espère que c'est clair, sinon il va falloir que je fasse un schéma et ça risque d'être pire...

Comment faire ça efficacement (i.e. Avec le moins de lock possible) en tenant compte du fait qu'on est sur un x86 ?

Peut-on se contenter pour le trafic P->T de créer un buffer (ou plusieurs ?) avec un pointeur de lecture et un d'écriture volatile, chacun ne pouvant être écrit que par T ou P ? P testerait que là où il veut écrire, ça a déjà été lu par T par exemple.

Je sais c'est surement très basique, mais il faut bien commencer quelque part

[Møgluglu]

En gros, tu as un cas de producteur-consommateur typique?
http://en.wikipedia.org/wiki/Producer-consumer_problem

Tes programmes P et T sont forcément des process différents, ou juste des threads d'un même process?

Dans tous les cas, je te conseille d'éviter de te poser trop de question sur la cohérence du modèle mémoire x86 et de la sémantique de volatile et d'utiliser des fonctions de bibliothèque bien classiques genre sémaphore, mutex, conditions...

En C++, boost::thread devrait avoir tout ce qu'il te faut... http://www.boost.org/doc/libs/1_39_0...on.condvar_ref

[Tramb]

Bien d'accord avec Monsieur Gluglu, ne cède pas à la tentation de l'interlocking pour démarrer, mais reste sur des critical sections.
Si j'ai bien compris tu as un seul thread d'analyse, donc il n'y a pas vraiment de problème de scaling vers un grand nombre de threads.

Le fait que tu penses à volatile pour faire de la synchro en C++ veut dire que tu as encore une vision restreinte du problème et même si tu fais une implémentation qui marche ou plutôt a l'air de marcher, tu auras tiré une bastos dans ta portabilité (plateforme et toolchain).

Bon courage et repasse poster quand t'es prêt à attaquer une FIFO interlocked

[newbie06]

Il s'agit bien d'un problème de producteur-consommateur. En revanche, il se peut qu'il y ait plusieurs consommateurs, mais vu mon niveau, autant commencer simple

C++ n'est pas une option (et ne le sera jamais, bouark). De toute façon, il existe des primitives équivalentes à celles de Boost en C, je suppose.

La portabilité n'est absolument pas envisagée : c'est du x86 sous Linux avec gcc (bon il y a de l'Opteron, du C2D, du C2Q et de l'i7, donc il doit y avoir des subtilités... à voir).

Je vais commencer par écouter vos conseils et utiliser des sémaphores.

Je me demande si du double buffering pour limiter les tests de sémaphore (je ne sais pas si j'emploie le bon terme) au swap de buffers ne serait pas plus efficace. A voir quand j'aurai déjà fait le cas simple...

Merci

[Tramb]

C++ n'est pas une option (et ne le sera jamais, bouark). De toute façon, il existe des primitives équivalentes à celles de Boost en C, je suppose.

Bouark toi-même sale kernhippie!
(Commence par les thread POSIX)

La portabilité n'est absolument pas envisagée : c'est du x86 sous Linux avec gcc (bon il y a de l'Opteron, du C2D, du C2Q et de l'i7, donc il doit y avoir des subtilités... à voir).

Ouais ouais on les connaît les projets où la portabilité est absolument pas envisagée, et après il faut passer à icc ou faire un portage PS3 ou que sais-je encore
Ceci dit le x86 est une archi qui pardonne beaucoup au niveau du code interlocké car il envoie des tonnes de memory barriers implicites, et à cause du don béni de la rétro compat binaire, ça restera le cas pendant encore 2 ou 3 millénaires. Donc t'auras pas de souci entre ces trois CPUs (au moins une bonne nouvelle )

Je me demande si du double buffering pour limiter les tests de sémaphore (je ne sais pas si j'emploie le bon terme) au swap de buffers ne serait pas plus efficace. A voir quand j'aurai déjà fait le cas simple...

Effectivement la ruse est de choisir ta granularité de locking astucieusement : si tu as besoin d'analyser sample par sample, tu dois locker souvent, sinon tu sacrifies un peu de latence et tu analyses des chunks de samples par exemple.
Dans ce cas là tu peux imaginer une liste chaînée interlockée de pages, l'API Win32 a ce qu'il faut pour ça. Et j'imagine que l'écosystème gcc doit avoir le même genre de choses, mais là je ne connais pas, désolé!

[Møgluglu]

Je me demande si du double buffering pour limiter les tests de sémaphore (je ne sais pas si j'emploie le bon terme) au swap de buffers ne serait pas plus efficace.

Dans le cas classique, on utilise un buffer circulaire comme FIFO, donc c'est déjà du n-uple buffering...
L'exemple avec les monitors de kikipédia est pas tellement plus compliqué que celui avec les sémaphores et gère les producteurs/consommateurs multiples, et tu as ça même dans les langages préhistoriques (pthreads).

Vu la classicité du problème, google doit pouvoir te trouver tout plein d'exemples.

[Eld]

C'est un problème de producteur consomateur, comme dit plus haut. Par contre, pour ce qui est de jeter les données que les threads ne peuvent pas analyser, il faut choisir une politique.

[newbie06]

Sur ce coup, j'ai honte, j'ai fait une FIFO avec des volatile. Allez, envoyez les insul^W remarques

 #include <stdlib.h>
 #include <stdio.h>
 #include <stdint.h>
 #include <stdarg.h>
 #include <pthread.h>
 #include <string.h>
 #include <unistd.h>
 
 #define NB_ITER   10
 #define BUF_SIZE  10000
 
 typedef uint16_t data_t;
 static data_t buf[BUF_SIZE];
 
 static volatile int g_index_read;
 static volatile int g_index_write;
 static volatile int g_done;
 
 typedef struct {
  int      total;
  uint64_t sum;
 } check_t;
 
 /* producer: wait for consumer to complete its job */
 static inline void wait_for_consumer(void)
 {
  /* the consumer doesn't write g_index_write */
  int index_write = g_index_write;
 
  while (g_index_read < index_write)
    /* usleep(1) */;
 }
 
 void *consumer(void *data)
 {
  int       consumer_total;
  uint64_t  consumer_sum;
  check_t  *ret = (check_t *)data;
 
  printf("consumer: Starting\n");
  consumer_total = 0;
  consumer_sum = 0;
 
  do {
    if (g_index_read > g_index_write && g_index_read == BUF_SIZE) {
      g_index_read = 0;
    } if (g_index_read < g_index_write) {
      consumer_total++;
      consumer_sum += buf[g_index_read++];
    }
  } while (!g_done);
 
  ret->total = consumer_total;
  ret->sum = consumer_sum;
  pthread_exit(NULL);
 }
 
 void producer(int iter, check_t *ret)
 {
  int      i, j, nb;
  int      producer_total;
  uint64_t producer_sum;
  data_t   data;
 
  printf("producer: Starting\n");
  srand(0);
  producer_total = 0;
  producer_sum = 0;
 
  for (i = 0; i < iter; i++) {
    nb = rand() % BUF_SIZE + 1;
    producer_total += nb;
    for (j = 0; j < nb; j++) {
      wait_for_consumer();
      /* produce data */
      if (g_index_write == BUF_SIZE) {
     /* buffer is full */
     g_index_write = 0;
      }
      data = rand();
      buf[g_index_write++] = data;
      producer_sum += data;
    }
  }
  wait_for_consumer();
  g_done = 1;
  ret->total = producer_total;
  ret->sum = producer_sum;
 }
 
 int main(int argc, const char *argv[])
 {
  pthread_t     tid;
  int           ret;
  check_t       consumer_check;
  check_t       producer_check;
  unsigned long iter;
 
  iter = NB_ITER;
  if (argc == 2)
    iter = strtoul(argv[1], NULL, 10);
 
  g_index_read = 0;
  g_index_write = 0;
  g_done = 0;
 
  /* create consumer */
  ret = pthread_create(&tid, NULL, consumer, &consumer_check);
  if (ret) {
    fprintf(stderr, "pthread_create: %s\n", strerror(ret));
    exit(1);
  }
 
  producer(iter, &producer_check);
 
  /* wait for consumer to end */
  ret = pthread_join(tid, NULL);
  if (ret) {
    fprintf(stderr, "pthread_join: %s\n", strerror(ret));
    exit(1);
  }
 
  printf("Producer: t=%d s=%ld\n", producer_check.total, producer_check.sum);
  printf("Consumer: t=%d s=%ld\n", consumer_check.total, consumer_check.sum);
 
  return 0;
 } 

[Yasko]

Tiens, c'est amusant, j'arrive à comprendre ton code, alors qu'il est en C.
En général, c'est pas bon signe.

[newbie06]

Oui, pas bon signe, comme tu dis

J'ai mesuré la vitesse : 5 millions de transactions par seconde. Une véritable catastrophe.

De toute évidence, soit il y a grosse cagade de ma part, soit il faut en passer par ce que je préconisais précédemment : double buffering...

[DaP]

Sur ce coup, j'ai honte, j'ai fait une FIFO avec des volatile.

Je me suis arrêté à la boucle d'attente active. Tu n'as pas envie de commencer avec une bête file producteur-consommateur bloquante comme tout le monde ?

[Møgluglu]

Non, newbie c'est un rebelle, on lui dit unanimement un truc il fait exactement le contraire.

[newbie06]

Faut dire que je ne comprends pas tous les mots que vous utilisez

Bon, je continue de réfléchir à tout ça, mais je souffre du NIH qui me pousse à commettre toutes les erreurs possibles, donc c'est long

[DaP]

Il y a un exemple avec les sémaphores ici : http://en.wikipedia.org/wiki/Producer-consumer_problem. En utilisant sem_wait() pour down() et sem_post() pour up() ça devrait le faire.
Sinon tu peux utiliser les variables conditionnelles de Pthreads en utilisant le pseudocode des moniteurs.

[Edit]

Si tu veux un truc tout fait : http://library.gnome.org/devel/glib/...us-Queues.html.

[newbie06]

Je pourrais prendre du code existant (je vais finir par le faire d'ailleurs), mais j'aimerais d'abord comprendre les trucs en me plantant

Personne n'a fait de bench là-dessus ?

[Tramb]

Bof conceptuellement la boucle qui spinlock ne me dérange pas dans certaines catégories d'appli mais il faut absolument envoyer un _mm_pause() dedans sinon ça va piquer

Je ne comprends pas pourquoi tu wait_for_consumer(), ça sérialise ton algo non? Tu n'as pas ce que tu souhaites, c'est à dire un producer qui crache autant que possible et le consumer qui traite autant que possible jusqu'à saturation du plus faible (ou parfait tuning de ton code )
Bon sinon tu refais vite fait le même en C++/STL avec une critical section et une std::deque pour avoir une implémentation lente de référence, espèce de saligaud.

Bon je passe sur le fait que ça ne marcherait pas sur PPC ou sur MSVC7 par exemple avec tes saloperies de volatile

Edit: Lis ça : http://www.alexonlinux.com/multithre...omic-variables

[newbie06]

J'ai fait un bench rapide avec un code trouvé sur le net : pc.c dans http://ftp.cs.hacettepe.edu.tr/pub/d...dtutorials.pdf

Pas brillant : < 5M transactions/seconde (en virant les usleep bien entendu ; d'ailleurs un ami me faisait remarquer que ne rien faire dans une boucle qui teste un "lock" est très mauvais car on risque de saturer les bus).

@Tramb: oui le wait_for_consumer est mauvais ; en passant à un burst aléatoire/wait_for_consumer ça va 20% plus vite (évident que c'est plus rapide)

[Møgluglu]

Au fait, pourquoi tu as besoin de tant de transactions par seconde?
Tu fais un concours ou il te faut du temps-réel avec contrainte de latence < 200 ns?

C'est pas possible de juste augmenter la granularité en traitant plus de données par transaction, comme Tramb propose?

[newbie06]

Au fait, pourquoi tu as besoin de tant de transactions par seconde?
Tu fais un concours ou il te faut du temps-réel avec contrainte de latence < 200 ns?

C'est pas possible de juste augmenter la granularité en traitant plus de données par transaction, comme Tramb propose?

Je n'ai strictement aucun problème de latence, sinon je n'aurais même pas évoqué de double buffering, tout newbie que je suis

Le contexte est assez simple : j'ai un simulateur très rapide (plusieurs centaines de millions d'instructions simulées par seconde) qui peut sortir des traces ; un exemple de trace est le point d'entrée d'un bloc de base (ça évite de sampler le PC pour chaque instruction). Ca donne un débit approximatif de 50-100M d'entiers/seconde. Le problème est de faire certaines analyses en ralentissant au minimum le simulateur.

Plus ça va, plus je pense qu'un simple double buffering avec lock sera la solution la plus efficace... Mais je suis une burne en MT, ce que je pense est sans doute faux

[Møgluglu]

Donc au lieu d'utiliser un buffer à n entrées de taille 1, ton idée de double-buffering revient à utiliser un buffer à deux entrées de taille n/2, non?

Si c'est le cas ça me semble généralisable à un buffer à n entrées de taille m...
(i.e., tu ne mets à jour ton index partagé que tout les m éléments que tu lis/écris, et au lieu d'un g_index_read++ tu fais un g_index_read+=m)

[fefe]

Traite tes donnees par paquets de 16k au lieu de 1 par 1, ca ira autrement plus vite . Tu peux tester 128k aussi mais a priori 16 c'est un bon debut .

[newbie06]

Bon, tout le monde est donc d'accord pour dire que mon code n'est pas une aberration complète, il faut juste envoyer plus de données à chaque transaction.

Sauf que:
- il manque un else
- ++ sur un volatile shared, c'est mal
- mon buffer est à moitié circulaire...

Je vais mettre en place ça dans le code réel voir ce que ça donne

[DaP]

Au fait les fonctions pthread_*() ne modifient pas errno, il faut prendre le code de retour de la fonction à la place d'utiliser perror(). Et strerror() n'est pas garantie thread-safe.
Je posterai le code que j'avais fait pour gérer les erreurs quand je l'aurai retrouvé.

Edit : ah oui, j'ai dû rêver pour perror().

[newbie06]

Au fait les fonctions pthread_*() ne modifient pas errno, il faut prendre le code de retour de la fonction à la place d'utiliser perror(). Et strerror() n'est pas garantie thread-safe.
Je posterai le code que j'avais fait pour gérer les erreurs quand je l'aurai retrouvé.

Je n'ai pas utilisé errno. Et pour strerror, merci du tuyau : il faut utiliser strerror_r

[Wanou]

C'est marrant, j'étais persuadé d'avoir laissé un troll par ici....




Aaahhh !!! Le voilà !
[Troll]
C'est sur que quand on voit la qualité de mon code en C, on ne s'étonne pas que je code en vbs.
[/Troll]

J'avais rien de plus à dire, merci.

[Tramb]

C'est pas un vrai troll, ça, juste une provocation de petit admin sys frustré qui croit savoir programmer.

[Yasko]

C'est marrant, j'étais persuadé d'avoir laissé un troll par ici....

Oui, faut croire qu'il a fait une mauvaise rencontre.
Ah, mais le revoilà, mais légèrement cabossé.

[newbie06]

Ha le troll est passé en mode auto flagellation.

[Neo_13]

Han, faut que je lanceflammise ici en modo frustré de faire du VBA ?

[Minuteman]

Han du VBA, comme tu fais pitié!