Suche Parralel STL (Threadsichere STL Container)

[DaRpH]

Hallo,

Kennt jemand eine Implementierung von der STL die Threadsichere Contaner beinhaltet.

Das ganze sollte auf Linux und WIndows sein Dienst verrichten.

Ich habe schon einiges von STAPL gelesen blos leider ist das anscheinend Experimentell und auch ein gut gehütetes Geheimnis, da ich kein Downloadlink finde.

Die TBB von Intel mit den concurrent_* containern sind wegen GNU Lizenz leider keine Option. Habe zwar gehört das es dafür wohl auch ein kommerzielles Modell gibt aber wollte eher auf einer Boost/BSD artigen Lizenz fahren.

Habe ich eine Biblothek übersehen, oder gibt es zum jetzigen Zeitpunkt einfach noch keine weiteren?

Danke schonmal

[hustbaer]

Was für threadsichere Container willst du denn (=was sollen die können und wie soll das Interface aussehen)? Und 2. Frage: wofür willst du diese einsetzen.

Im Allgemeinen eignen sich die normalen STL Container (std::vector, std::list, ...) nicht dafür "von innen heraus" threadsicher gemacht zu werden (=geht nicht, zumindest sicher nicht mit std::vector, und bin mir ziemlich sicher auch nicht mit std::list). Von aussen synchronisieren ist dagegen kein Problem.

Und im Allgemeinen ist es auch schneller Zugriffe über einen Usermode spin-sleep-lock zu synchronisieren (Boost.Thread bietet sowas, nennt sich dort einfach mutex), als "non-blocking" Varianten zu verwenden. Und wenn du einen spin-sleep-lock verwenden willst, dann kannst du das von aussen genausogut, ist keine Zauberei. Oder du implementierst deine eigene Klasse mit Hilfe einer normalen Collection und eines solchen locks.

Und falls du nur eine Implementierung suchst deren Container in mehreren Threads verwenden werden können wenn man selbst von aussen synchronisiert wo es nötig ist: nimm einfach die STL die mit dem Compiler mit kommt, die kann das dann. Zumindest die von MSVC bei Windows, und GCC wohl so ziemlich überall.

[DaRpH]

Also ich habe mich eher auf Queue, List, Map bezogen. Das man das von aussen einfach nachrüsten kann ist meiner Meinung leider nicht so da man nie weis was die Implementationen nun wirklich innerhalb der Funktionen treiben. Und jeden Zugriff locken ist ja sehr Zeitintensiv.

STAPL sowie TBB locken zB Bereiche (anstatt jeden Write) und können den Sortiervorgang deutlich parallelisieren.

für was ich das einsetzen will: Wfür setzt man die STL ein? Für alles mögliche blos in diesem Fall im Zusammenhang mit zB OpenMP welches iterieren über STL Container nur langsam(viele locks) ermöglicht und ich daher nicht will das OpenMP sich um das locken kümmert.

TBB: http://www.threadingbuildingblocks.org/ver.php?fid=91 beinhaltet laut doku threadischere hashmap, queue und vector
STAPL: http://parasol.tamu.edu/stapl/ ähnlich wie TBB wohl aber noch mehr

[sri]

Solange Du an den TBB keine Änderungen vornimmst, kannst Du sie problemlos auch bei kommerziellen Projekten einsetzen (GPL mit Runtime-Erweiterung). Veränderungen und Erweiterungen müssen dagegen auch anderen zur Verfügung gestellt werden. Wenn Du das nicht möchtest, dann kannst Du entweder für $299 eine Lizenz erwerben (pro System) oder für $599 den Intel-Compiler kaufen. Dort sind die TBB sowie die IPP gleich dabei.

[hustbaer]

STAPL sowie TBB locken zB Bereiche (anstatt jeden Write) und können den Sortiervorgang deutlich parallelisieren.

Das geht z.B. mit std::vector genauso, bloss muss man dann den sort selber schreiben.

Für alles mögliche blos in diesem Fall im Zusammenhang mit zB OpenMP welches iterieren über STL Container nur langsam(viele locks) ermöglicht und ich daher nicht will das OpenMP sich um das locken kümmert.

Ich hab' ehrlich gesagt den Eindruck dass du mit der ganzen Threading Geschichte noch nicht so viel Erfahrung hast. Wenn du OpenMP verwenden willst und dich nicht selbst um das Locking kümmern, dann wird es *immer* *viel* *langsamer* sein als wenn du a) fertige komponenten mit fertigen algorithmen verwendest oder b) das Locking selbst übernimmst, und zwar genau dort wo es nötig ist/Sinn macht.
Die "Mischung" quasi "sich nicht selbst ums Locking kümmern, aber schon selbst irgendwas in OpenMP basteln" ist ... einfach nicht optimal.

Threadsichere Container machen IMO nur an ganz wenigen Stellen Sinn, z.B. bei Queues zwischen Threads (Producer-Consumer), oder spezielle Container für Implementierungen von Caches (File-Cache, ...) auf grossen SMP Systemen (4 Cores+).

Alle anderen Dinge löst man am besten duch: möglichst selten locken/unlocken, und (wenn lock contention zu einem problem werden könnte): die Locks nur kurz halten. Durch intern threadsichere Container bekommst du das NIE hin, da die bei fast jedem Funktionsaufruf entweder locken müssten, oder interlocked instructions verwenden müssten -- was meinst noch teurer ist als ein schnelles lock + unlock.

Das man das von aussen einfach nachrüsten kann ist meiner Meinung leider nicht so da man nie weis was die Implementationen nun wirklich innerhalb der Funktionen treiben.

Pfuh, ja, wenn du meinst.
Mit der MSVC STL geht es, mit der GNU STL geht es, ... . Hat sich einfach als Standard eingebürgert, und die üblichen Regeln sind: alles "const" darf mehrfach parallel, alles "non const" darf nur exclusiv. Und du musst wohl davon ausgehen dass alles "non const" dir Iteratoren kaputt macht die ein anderer Thread davor geholt hat -> du solltest Locks halten und nicht freigeben wenn du Iteratoren später wieder verwenden willst. Dinge wie z.B. Referenzen auf die Elemente eines std::vector sind dagegen kein Problem.

[Tachyon]

sri schrieb:

Solange Du an den TBB keine Änderungen vornimmst, kannst Du sie problemlos auch bei kommerziellen Projekten einsetzen (GPL mit Runtime-Erweiterung). Veränderungen und Erweiterungen müssen dagegen auch anderen zur Verfügung gestellt werden. Wenn Du das nicht möchtest, dann kannst Du entweder für $299 eine Lizenz erwerben (pro System) oder für $599 den Intel-Compiler kaufen. Dort sind die TBB sowie die IPP gleich dabei.

Hmm, habe ich die GPL falsch verstanden? Ich dachte, bei der GPL reicht es schon, das Interface einzubinden um selbst der GPL zu unterliegen. Wenn ich also z.B. einen unter GPL stehenden Header bei mir einbinde und eine dazugehörende dll verwende, muss ich meinen eigenen Code dann auch unter der GPL veröffentlichen (selbst, wenn er die benutzen Sourcen nicht verändert).
Ist das, was Du beschreibst nicht eher die LGPL?

[sri]

Bei einer reinen GPL-Bibliothek hast Du recht. Die TBB kommen aber mit einer Runtime-Erweiterung daher, die es gestattet, die Bibliothek zu einer Anwendung zu linken, ohne die Anwendung selbst unter GPL stellen zu müssen (wie libstdc++).

Ich hatte zu diesem Thema vor einem knappen Jahr eine Telefonkonferenz mit Intel. Ergebnis war, dass ich die Open Source-Version in meine Anwendungen einbinden kann, wenn ich keine Änderungen an den TBB vornehme. Bei einer Änderung müsste ich den geänderten TBB-Code ebenfalls veröffentlichen. Wenn man das nicht möchte, muss man die kommerzielle Version verwenden.

[DaRpH]

Also stehen die Headerdateien praktisch nicht unter GPL oder wie^^ Was verstehst du unter Runtime erweiterung? Dll?

[sri]

Auf der TBB-Seite steht geschrieben:

Licensed under GPLv2 with the runtime exception.

Ein Link führt zu den Lizenzbestimmungen der libstdc++, dort steht:

The source code is distributed under the GNU General Public License version 2, with the so-called “Runtime Exception” as follows (or see any header or implementation file):

As a special exception, you may use this file as part of a free software
library without restriction. Specifically, if other files instantiate
templates or use macros or inline functions from this file, or you compile
this file and link it with other files to produce an executable, this
file does not by itself cause the resulting executable to be covered by
the GNU General Public License. This exception does not however
invalidate any other reasons why the executable file might be covered by
the GNU General Public License.

Hopefully that text is self-explanatory. If it isn't, you need to speak to your lawyer, or the Free Software Foundation.

[DaRpH]

Naja dann wirds wohl erstmal bei TBB bleiben.

@hustbaer:
mir gings sowieso hauptsächlich um die Queue für eigne Threadevents.
Das die Container langsamer bei Lock implementierung intern langsamer währen als bei eigner Implemetierung von extern stimmt jedoch keinesfalls. Ich mein mir ist klar das wenn man keine Threads verwenden will für einen vector dann nimmt man auch nicht die Threadsichere implemntierung. Wenn mans jedoch threadsicher braucht dann ist das allemal schneller als manuell das zu wrappen.

Einige Parallele Algorithmen wie zB sort werden anscheinend von der libstdc++ oder wie sie heist implementiert.

[hustbaer]

Das die Container langsamer bei Lock implementierung intern langsamer währen als bei eigner Implemetierung von extern stimmt jedoch keinesfalls.

Möglich dass wir von 2 verschiedenen Dingen reden. Du hast nach einer STL mit threadsicheren Container gefragt, daher bin ich davon ausgegangen dass du allgemeine, nicht spezialisierte Container meinst wie man sie in der STL findet, die für sich schon threadsafe sind. Und zwar auf allen operationen. Und sowas ist Quatsch, das versuchte ich dir hier zu erklären.

Wenn du threadsichere Algorithmen wie sort meinst, oder spezialisierte Container wie eine Producer-Consumer-Queue, dann ist das wieder etwas ganz anderes.

Ich mein mir ist klar das wenn man keine Threads verwenden will für einen vector dann nimmt man auch nicht die Threadsichere implemntierung. Wenn mans jedoch threadsicher braucht dann ist das allemal schneller als manuell das zu wrappen.

Nochmal: es gibt keinen threadsicheren vector und es kann keinen geben. Wenn du irgendwo eine Vektor Klasse findest wo die Teile des Interfaces/Contracts entfernt wurden die das unmöglich machen, und deren Funktionen alle intern synchronisiert sind, dann wird die garantiert langsamer sein, als wenn du deine Funktionen so implementierst dass du nur dort lockst wo es nötig ist. Eine intern threadsichere Klasse hat keine andere Wahl als in jeder einzelnen Memberfunktion zu locken, und das kann unmöglich schneller sein als wenn man es selbst von aussen macht.

Und was lock-free Algorithmen angeht: zeig mir einen der nicht langsamer ist als eine Version mit locking. Auf heutiger Hardware. Mit Ausnahme diverser Exoten wie unidirektionale single producer, single consumer pipes.

Einige Parallele Algorithmen wie zB sort werden anscheinend von der libstdc++ oder wie sie heist implementiert.

Ist das nicht die STL Implementierung vom g++?

[camper]

hustbaer schrieb:

Und was lock-free Algorithmen angeht: zeig mir einen der nicht langsamer ist als eine Version mit locking. Auf heutiger Hardware. Mit Ausnahme diverser Exoten wie unidirektionale single producer, single consumer pipes

Ist das nicht eher umgekehrt? Lock-freie Algorithmen spielen ihren Vorteil doch gerade bei starker Konkurrenz aus: bei jedem gleichzeitigen Versuch mehrerer Threads ist beim lockfreien Algorithmus einer garantiert erfolgreich - mithin ist ein gewisser (hoher) Durchsatz garantiert - während beim Locking der Durchsatz mit zunehmender Konkurrenz eher sinken wird. Natürlcih sieht die Situation bei geringer Konkurrenz anders aus, durch die relativ stark geordnete x86-Architektur sind Spinlocks hier zudem von vornherein schneller als man das allgemein erwarten kann.

[Blue-Tiger]

hustbaer schrieb:

Einige Parallele Algorithmen wie zB sort werden anscheinend von der libstdc++ oder wie sie heist implementiert.

Ist das nicht die STL Implementierung vom g++?

er meint wahrscheinlich http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html

[peterchen]

Ich kann hustbaer nur zustimmen:

Containerklassen selbst können nur sehr begrenzt parallelen Zugriff unterstützern. Der Container kann nur einzelne Funktionen locken - meist müssen aber in einem thread mehrere Zugriffe im Block ausgeführt werden.

Beispiel std::queue:

if (q.size() != 0)
{
   value = q.top();
   q.pop();
}

Hier nützt es gar nix, wenn die einzelnen Operationen threadischer sind: wenn Dir ein anderer Thread in der Zwischenzeit die queue leert, macht es BUMM!

Die Schnittstelle der Container müßte speziell auf diese Anwendung zugeschnitten sein (und - wie hustbaer sagt - alle Funktionen, die das nciht erlauben, müßten weg).

Ich befürchte, der Wunsch nach einer atomaren get-and-pop-Funktion beißt sich sogar mit der strong exception safety - Garantie für template-Container (bin mir nicht sicher für queue, das Pattern ist aber ähnlich dem Stack).

[DaRpH]

@peterchen:

auch sowas könnte man lösen und zwar wenn dieser container transaktionen bzw zugriff auf den lock von aussen zulässt aller:

queue q;
//...
{
  write_transaction<queue> mod(q);

  if (mod.size() != 0) 
  {
     value = mod.top();
     mod.pop();
  }
}

Die Kunst dahinter istja nur das die Container einzelne Aufrufe threadsicher macht und auch Transaktionen ermöglicht und in dem Fall das interne locking für die Zeit der schreibe transaktion deaktiviert und nur über das transaktionsobjekt zugriff zulässt.

Wenn man sich zusätzlich noch davon verabschieden kann das die Daten im Container immer aktuell sein müssen und mann im Hintergrund jeweils den Container mit den aktuellen Daten aufbaut (zB für große Hasmaps) dann kann man dies beinahe Lock-Free implementieren da man am Ende praktisch nurnoch intern im Container die Datenquelle von der alten Datenbasis auf die neue umstellen muss.

@hustbaer:
Lock-Free Algorithmen sind immer schneller sofern sie nicht alzu lang brauchen die Datenzugriffe Konfliktfrei zu verteilen. Und im stark konkurierendem Betrieb selbst dann, sonst würde sich der Aufwand ja nicht lohnen.

@blue tiger:
ja die habe ich gemeint aber die sind eben auch noch "experimentell"