jeudi 3 octobre 2013

thread_local

Voyons maintenant une autre fonctionnalité C++11 ajoutée dans g++ 4.8, longtemps attendue par les aficionados, et complètement ignorée par les autres: thread_local. Ce mot-clé s'ajoute devant une variable globale, variable statique, ou variable de classe statique, et indique que cette variable sera locale au thread, c'est à dire que chaque thread aura accès à son bout de mémoire propre. Prenons un exemple bête pour illustrer cela. Voici un programme qui fait tourner 4 threads, lesquels incrémentent une variable miaou, puis l'impriment. L'affichage est protégé par un mutex, mais pas l'accès à la variable. Puis, lorsque tous les threads sont complets, l'on affiche le résultat.

#include <thread>
#include <mutex>
#include <iostream>

std::mutex mutex;

int miaou = 0;

void run()
{
  for(size_t i = 0; i < 1000000; ++i) ++miaou;
  std::lock_guard<std::mutex> lock(mutex);
  std::cout << miaou << std::endl;
}

int main()
{
  std::thread t1(&run);
  std::thread t2(&run);
  std::thread t3(&run);
  std::thread t4(&run);
  t1.join();
  t2.join();
  t3.join();
  t4.join();
  std::cout << miaou << std::endl;
  return 0;
}

Ayant fait tourner le programme, l'on obtient un résultat de ce type:

1164088
1177191
1229070
1222696
1222696

Les threads se sont battus pour la variable, et son évolution est donc plutôt ésotérique. Maintenant, passons miaou comme étant thread_local:

#include <thread>
#include <mutex>
#include <iostream>

std::mutex mutex;

thread_local int miaou = 0;

void run()
{
  for(size_t i = 0; i < 1000000; ++i) ++miaou;
  std::lock_guard<std::mutex> lock(mutex);
  std::cout << miaou << std::endl;
}

int main()
{
  std::thread t1(&run);
  std::thread t2(&run);
  std::thread t3(&run);
  std::thread t4(&run);
  t1.join();
  t2.join();
  t3.join();
  t4.join();
  std::cout << miaou << std::endl;
  return 0;
}

Le résultat, cette fois-ci, est complètement déterministe:

1000000
1000000
1000000
1000000
0

Chaque thread a obtenu sa propre variable miaou, et l'a incrémenté jusqu'à 1000000. Le thread principal a également obtenu sa variable, et n'en a rien fait, sa valeur est donc 0.

Bien entendu, mon exemple est complètement artificiel. Quels pourraient donc être les utilisations de la fonctionnalité?

Gérer une mémoïsation thread safe, par exemple, peut être fait en utilisant une variable statique thread_local. Voyons donc le bon vieil exemple de Fibonacci mémoïsé:

#include <unordered_map>
#include <iostream>

size_t fib(size_t n)
{
  if(n <= 2)
    return 1;
  
  static std::unordered_map<size_t, size_t> memo;
  auto result = memo.insert(std::make_pair(n, 0));
  if(!result.second)
  {
    return result.first->second;
  }
  else
  {
    return (result.first->second = (fib(n - 1) + fib(n - 2)));
  }
}

int main()
{
  for(size_t i = 1; i <= 50; ++i)
  {
    std::cout << fib(i) << std::endl;
  }

  return 0;
}

Voilà un petit programme qui affichera les 50 premiers nombres de Fibonacci, transformant l'algorithme récursif usuel à complexité exponentielle en un algorithme à complexité linéaire (on laissera de côté l'algorithme linéaire sans mémoïsation, ainsi que l'algorithme logarithmique dont on parlera peut-être un autre jour). Rien que pour rigoler, enlevez la mémoïsation, et admirez votre CPU en train de souffrir.

Tout va bien jusque là? Alors voyons ce qu'il se passe lorsque vous avez plusieurs threads accédant à la même fonction.

#include <thread>
#include <mutex>
#include <unordered_map>
#include <iostream>

size_t fib(size_t n)
{
  if(n <= 2)
    return 1;
  
  static std::unordered_map<size_t, size_t> memo;
  auto result = memo.insert(std::make_pair(n, 0));
  if(!result.second)
  {
    return result.first->second;
  }
  else
  {
    return (result.first->second = (fib(n - 1) + fib(n - 2)));
  }
}

std::mutex mutex;

void run()
{
  for(size_t i = 1; i <= 50; ++i)
  {
    size_t f = fib(i);
    std::lock_guard<std::mutex> lock(mutex);
    std::cout << i <<  " " << f << std::endl;
  }  
}

int main()
{
  std::thread t1(&run);
  std::thread t2(&run);
  std::thread t3(&run);
  std::thread t4(&run);
  std::thread t5(&run);
  std::thread t6(&run);
  std::thread t7(&run);
  std::thread t8(&run);
  t1.join();
  t2.join();
  t3.join();
  t4.join();
  t5.join();
  t6.join();
  t7.join();
  t8.join();
  
  return 0;
}

Le résultat est bien entendu indéfini, et en effet, en faisant tourner quelques fois, l'on obtient le cas où un thread accède à la map avant qu'elle ne soit mis à jour, et l'on obtient par exemple fib(50) = 2971215073 au lieu de 12586269025. Passez donc la map statique comme étant thread_local, comme ceci:

size_t fib(size_t n)
{
  if(n <= 2)
    return 1;
  
  thread_local static std::unordered_map<size_t, size_t> memo;
  auto result = memo.insert(std::make_pair(n, 0));
  if(!result.second)
  {
    return result.first->second;
  }
  else
  {
    return (result.first->second = (fib(n - 1) + fib(n - 2)));
  }
}

Maintenant, chaque thread a son propre cache, quel que soit le nombre de threads et le moment auquel ils ont été créés. L'on pourrait bien sûr partager le cache, au prix d'un mutex. Il est donc parfois plus efficace de donner son cache à chaque thread, ce qui est trivial avec le nouveau mot-clé.

Une autre utilisation possible pourrait être dans des routines de log, par exemple, chaque thread stocke les messages localement, et c'est uniquement lorsque le nombre de messages dépasse un certain seuil qu'un mutex global est pris et les messages envoyés vers l'écran ou dans un fichier. Ou encore, une fonction ayant besoin d'un buffer dynamique pourrait le déclarer en statique afin d'éviter une allocation si l'appel suivant n'a pas besoin d'un buffer plus grand, et être thread safe avec un buffer thread_local. Il n'y a plus qu'à essayer!

Aucun commentaire: