tr1 :: hash für boost :: thread :: id?

Der Overhead von thread::id (nur um den String-Hash später zu berechnen) ist, wie Sie fast selbst sagten, astronomisch im Vergleich zu irgendwelchen Leistungsvorteilen, die ein tr1::unordered_map gegenüber std::map verleihen könnte. Die kurze Antwort wäre also: mit std :: map & lt; thread :: id, ... & gt;

Wenn Sie absolut ungeordnete Container verwenden müssen, versuchen möglichst native_handle_type anstelle von thread::id zu verwenden, dh bevorzugen Sie tr1::unordered_map< thread::native_handle_type, ... > , stattdessen thread::native_handle() von thread::get_id() wenn insert ing und find ing.

Versuchen Sie NICHT, Folgendes zu tun: :

Es könnte funktionieren, ist aber extrem spröde und eine fast garantierte Zeitbombe. Es setzt eine genaue Kenntnis der inneren Funktionsweise der thread::id -Implementierung voraus. Es wird dich von anderen Entwicklern verfluchen lassen. Tun Sie es nicht, wenn Wartbarkeit eine Rolle spielt! Sogar das Patchen von boost/thread/detail/thread.hpp zum Hinzufügen von size_t hash_value(const id& tid) als Freund von thread::id ist "besser". :)

Die offensichtliche Frage ist, warum sollten Sie eigentlich einen Hash verwenden?

Ich verstehe das Problem mit map / set für leistungskritischen Code. Diese Container sind nicht sehr Cache-freundlich, da die Elemente möglicherweise an sehr unterschiedlichen Speicherorten zugewiesen sind.

Wie KeithB vorgeschlagen hat (ich werde die Verwendung der Binärdarstellung nicht kommentieren, da nichts garantiert, dass 2 IDs immerhin die gleiche binäre Darstellung haben ...), kann die Verwendung eines sortierten vector den Code beschleunigen, falls dies der Fall ist sehr wenige Artikel.

Sortierte Vektoren / Deques sind viel mehr cachefreundlich, jedoch leiden sie an einer O (N) -Komplexität beim Einfügen / Löschen wegen des involvierten Kopierens. Wenn du einmal ein paar hundert Threads erreicht hast (so viele übrigens noch nie gesehen), könnte das weh tun.

Es gibt jedoch eine Datenstruktur, die versucht, die Vorteile von Karten und sortierten Vektoren zu verbinden: der B + Baum .

Sie können es als eine Karte anzeigen, für die jeder Knoten mehr als ein Element enthält (in sortierter Reihenfolge). Nur die Blattknoten werden verwendet.

Um mehr Leistung zu erhalten, können Sie:

• Verknüpfen Sie die Blätter linear: dh der Stamm speichert einen Zeiger auf das erste und letzte Blatt und die Blätter sind untereinander verbunden, so dass die lineare Bewegung die internen Knoten vollständig umgeht.
• Lege das Blatt, auf das zuletzt zugegriffen wurde, im Wurzelverzeichnis auf, denn es ist wahrscheinlich, dass es auch das nächste ist, auf das zugegriffen wird.

Die asymptotischen Leistungen sind die gleichen wie für die Karte, da sie als Balanced Binary Tree implementiert ist, aber weil die Werte in Gruppen gepackt sind, kann der Code durch eine Konstante schneller werden.

Die Schwierigkeit besteht darin, die Größe jedes "Buckets" anzupassen, Sie brauchen dafür ein Profiling, also wäre es besser, wenn Ihre Implementierung dort Anpassungen erlaubt (da dies von der Architektur abhängt, auf der der Code basiert) ausgeführt).

Warum möchten Sie diese in einem Set speichern? Wenn Sie nicht etwas Außergewöhnliches tun, wird es eine kleine Anzahl von Threads geben. Der Aufwand für die Pflege einer Menge ist wahrscheinlich höher als nur das Einfügen in einen Vektor und das Ausführen einer linearen Suche.

Wenn die Suche häufiger stattfindet als das Hinzufügen und Löschen, können Sie einfach einen sortierten Vektor verwenden. Es gibt ein & lt; Der Operator ist für boost :: thread :: id definiert, so dass Sie den Vektor nach jedem Hinzufügen oder Löschen an der richtigen Stelle sortieren und mit lower_bound() eine binäre Suche durchführen können. Dies ist die gleiche Komplexität wie das Durchsuchen einer Menge und sollte einen niedrigeren Aufwand für kleine Datenmengen haben.

Wenn Sie das immer noch tun müssen, dann behandeln Sie es einfach als sizeof (boost :: thread: id) Bytes, und arbeiten Sie damit.

In diesem Beispiel wird davon ausgegangen, dass die Größe von boost :: thread :: id ein Vielfaches der Größe eines int ist und dass es keine Pakete und keine virtuellen Funktionen gibt. Wenn das nicht stimmt, muss es geändert werden oder wird überhaupt nicht funktionieren.

BEARBEITEN: Ich habe mir die boost::thread::id -Klasse angeschaut und sie hat boost::shared_pointer<> als Mitglied, also ist der folgende Code schrecklich kaputt. Ich denke, die einzige Lösung ist, dass die Autoren von boost::thread eine Hash-Funktion hinzufügen. Ich verlasse das Beispiel nur für den Fall, dass es in einem anderen Kontext nützlich ist.

Einige Jahre zu spät, um diese Frage zu beantworten, aber dies erschien am relevantesten, als wir versuchten, boost :: thread :: id in eine std :: unordered_map als Schlüssel zu setzen. Das native Handle war ein guter Vorschlag in der angenommenen Antwort, außer dass es für this_thread nicht verfügbar ist.

Stattdessen hat Boost für einige Zeit einen Hash-Wert für thread :: id, also hat das für mich funktioniert:

Natürlich müssen Sie die libboost_thread-Bibliothek verlinken.

Sie können eine Klasse erstellen, die eine Zuordnung zwischen thread :: id und etwas (zB: integers) vornimmt, das Sie als Hash verwenden können. Der einzige Nachteil ist, dass Sie sicherstellen müssen, dass nur eine Instanz des Mapping-Objekts im System vorhanden ist.