Pool-Pattern

Eine Synchronisierung mit Hilfe einer Mutex-Variablen ist nicht kostenfrei. Auf der Thales liegen die Kosten für die Verwendung eines std::lock_guard bei 36 Nanosekunden -- selbst wenn nur ein einziger Thread aktiv ist. Das ist also mehr als dreifach so teuer wie die Erzeugung einer gleichverteilten ganzen Zahl mit Hilfe von std::mt19937! Sollten sich in einem worst case scenario zwei Threads permanent um eine Mutex-Variable konkurrieren, steigt die Zeitdauer auf über 240 Nanosekunden.

Folgendes Beispiel demonstriert dies für zwei solche Threads:

session15/mutual.cpp

#include <cstdio>
#include <mutex>
#include <thread>
#include <vector>
#include <hpc/aux/walltime.h>

class Counter {
   public:
      Counter() : counter(0) {
      }
      unsigned long long int increment() {
         std::lock_guard<std::mutex> lock(mutex);
         return ++counter;
      }
   private:
      std::mutex mutex;
      unsigned long long int counter;
};

int main() {
   constexpr unsigned int nof_threads = 2;
   using CounterValue = unsigned long long int;
   constexpr CounterValue max_counter = 1LL << 24;

   std::vector<std::thread> threads(nof_threads);
   hpc::aux::WallTime<double> wall_time;
   Counter counter;
   wall_time.tic();
      for (auto& t: threads) {
         t = std::thread([&]{
            while (counter.increment() < max_counter)
               ;
         });
      }
      for (auto& t: threads) {
         t.join();
      }
   auto t = wall_time.toc();
   std::printf("avg time per lock = %.2lf ns\n",
      t / max_counter * 1000000000LL);
}

$shell> g++ -O3 -g -I/home/numerik/pub/hpc/session15 -std=c++11 -o mutual mutual.cpp
$shell> ./mutual
avg time per lock = 202.53 ns

Wenn wir davon ausgehen, dass in einer Anwendung in größerem Umfang Pseudo-Zufallszahlen benötigt werden und dies ggf. mehrfach mit verschiedenen Threads, dann erscheinen beide bisherigen Ansätze nicht hilfreich. Im Grunde benötigen wir für jeden Thread seinen eigenen Pseudo-Zufallszahlengenerator, wir sollten aber in der Lage sein, diesen aufzubewahren, bis das nächste Mal wiederum ein Thread einen Pseudo-Zufallszahlengenerator benötigt.

Wenn die Erzeugung von Objekten nicht billig ist, solche Objekte aber immer wieder für beschränkte Zeit benötigt werden, dann ist das Pool-Pattern hilfreich. Eine Pool-Klasse funktioniert ähnlich wie eine Verleih-Bibliothek: Objekte können ausgeliehen und wieder zurückgegeben werden. Wenn alle Objekte vergeben sind, können Pools entweder den Aufrufer warten lassen, bis ein Objekt zurückgegeben wird oder spontan ein neues Objekt erzeugen. Im konkreten Fall der Pseudo-Zufallszahlengeneratoren erscheint es sinnvoll, letztere Strategie zu verfolgen.

Ein erster Entwurf einer entsprechenden Klasse könnte so aussehen:

template<typename T>
struct RandomEnginePool {
      using EngineType = T;
      T get() {
         /* check if we have a free engine in unused */
         {
            std::lock_guard<std::mutex> lock(mutex);
            if (unused.size() > 0) {
               T rg = unused.front();
               unused.pop_front();
               return rg;
            }
         }
         /* prepare new random generator */
         return T(r());
      }
      void free(T engine) {
         std::lock_guard<std::mutex> lock(mutex);
         unused.push_back(engine);
      }
   private:
      std::mutex mutex;
      std::random_device r;
      std::list<T> unused;
};

In der STL (standard template library) von C++ findet sich auch eine Klasse für doppelt verkettete lineare Listen, std::list über die Header-Datei <list>. Lineare Listen können mit konstanten Aufwand wachsen (und wieder schrumpfen). Nur die Suche eines Element wäre teuer -- die wir hier aber nicht benötigen, da uns das nächstbeste Element genügt. Die lineare Liste unused verwahrt hier die gerade nicht benutzten, ausleihbaren Generatoren. Mit push_back wird ein Objekt an das Ende der Liste angehängt, mit front wird das vorderste Element abgerufen, jedoch nicht entfernt -- dies geschieht erst mit pop_front.

Aufgabe

Ersetzen Sie in Ihrem Testprogramm die Verwendung von MyRandomGenerator durch das Pool-Pattern unter Verwendung von RandomEnginePool. Als Template-Parameter empfiehlt sich hier wieder std::mt19937.