============
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:

:import:session15/mutual.cpp

---- SHELL (path=session15) ---------------------------------------------------
g++ -O3 -g -I/home/numerik/pub/hpc/session15 -std=c++11 -o mutual mutual.cpp
./mutual
-------------------------------------------------------------------------------

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:

---- CODE (type=cpp) ----------------------------------------------------------
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`.

:navigate: up    -> doc:index
           back  -> doc:session15/page02
           next  -> doc:session15/page04