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

Question

Ich begann die unordered_set Klasse aus dem tr1 Namespace zu verwenden, um Zugang gegen die Ebene (Baum-basierte) STL map zu beschleunigen. Allerdings wollte ich Verweise auf Themen-ID im Boost speichern (boost::thread::id) und erkannte, dass die API dieser Identifikatoren so undurchsichtig ist, dass Sie nicht eindeutig einen Hash davon erhalten kann.

Überraschenderweise boost implementiert Teile des tr1 (einschließlich hash und unordered_set), aber es wird nicht definiert, eine Hash-Klasse, die ein Thread-ID-Hash in der Lage ist.

in der Dokumentation von boost::thread::id der Suche fand ich, dass Thread-IDs Ausgang zu einem Strom sein kann, so meine Lösung für Hashing tun war irgendwie:

struct boost_thread_id_hash
{
    size_t operator()(boost::thread::id const& id) const
    {
        std::stringstream ostr;
        ostr << id;
        std::tr1::hash<std::string> h;
        return h(ostr.str());
    }
};

Das heißt, serialisiert es, den Hash auf den resultierenden String anzuwenden. Dies scheint jedoch weniger effizient zu sein, als tatsächlich den STL map<boost::thread::id> verwendet wird.

Also, meine Fragen: Finden Sie einen besseren Weg, dies zu tun? Ist es eine klare Unvereinbarkeit sowohl Auftrieb und TR1 nicht die Existenz einer hash<boost::thread::id> Klasse zu zwingen?

Danke.

Answer 1

Der Kopf thread::id von stringifying (nur die Zeichenfolge Hash danach zu berechnen) ist, wie Sie selbst fast sagten, im Vergleich astronomische ein Leistungs ein tr1::unordered_map Vorteil könnten verleihen vis-a-vis std::map. So die kurze Antwort wäre: Stick mit std :: map

Wenn Sie absolut müssen ungeordnete Behälter verwenden, versuchen usenative_handle_type statt thread::id wenn möglich, dh tr1::unordered_map< thread::native_handle_type, ... > bevorzugen, thread::native_handle() Aufruf statt thread::get_id() wenn inserting und finding.

NICHT versuchen, so etwas wie die folgende :

struct boost_thread_id_hash {
   // one and only member of boost::thread::id is boost::thread::id::thread_data
   //   of type boost::detail::thread_data_ptr;
   // boost::thread::id::operator==(const id&) compares boost::thread::id::thread_data's
   size_t operator()(boost::thread::id const& id) const {
      const boost::detail::thread_data_ptr* pptdp = \
        reinterpret_cast< boost::detail::thread_data_ptr* >(&id);
      return h(pptdp->get());
   }
};

Es könnte funktionieren, aber ist extrem spröde und eine fast garantiert Zeitbombe. Er geht davon aus intimer Kenntnis der inneren Abläufe der thread::id Umsetzung. Es wird Sie bei von anderen Entwicklern verfluchten bekommen. Tun Sie es nicht, wenn Wartbarkeit ist, wenn eine Besorgnis! Auch boost/thread/detail/thread.hpp Patchen size_t hash_value(const id& tid) hinzufügen, wie ein Freund von thread::id „besser“ ist. :)

Answer 2

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

Ich verstehe das Problem mit map / set für die Leistung kritischen Code, in der Tat solche Behälter nicht sehr Cache freundlich sind, weil die Einzelteile zu sehr unterschiedlichen Speicherorten zugeordnet werden könnten.

Wie KeithB vorgeschlagen (Ich werde nicht kommentieren die binäre Darstellung verwendet wird, da nichts garantiert, dass 2-IDs die gleiche binäre Darstellung haben immerhin ...), eine sortierte vector verwenden, können Sie den Code für den Fall beschleunigen gibt es nur sehr wenige Elemente.

Sortiert Vektoren / deques sind viel Cache-freundlich, aber sie leiden unter einer O (N) Komplexität auf insert / löschen, da der Kopier beteiligt. Sobald Sie ein paar hundert Fäden (nie gesehen, dass viele von der Art und Weise) zu erreichen, könnte es schaden.

Es ist jedoch eine Datenstruktur, die die Vorteile von Karten zu verbinden versucht und sortierte Vektoren: die B + Baum .

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

Um mehr Leistung zu erhalten können Sie:

• Verknüpfen Sie die Blätter linear. Dh die Wurzel einen Zeiger auf das erste und das letzte Blatt-Caches und die Blätter selbst sind miteinander verbunden, so dass lineare Bewegung vollständig die interal Knoten umgehen
• Cache die zuletzt zugegriffen Blatt in der Wurzel, doch es ist wahrscheinlich, dass werde auch die nächste zugegriffen werden.

Die asymptotisch Leistungen gleich sind, als für die Karte, weil sie als Balanced Binary Tree implementiert ist, sondern weil die Werte in Gruppen verpackt sind, sind Sie Code schneller durch eine Konstante werden kann.

Die eigentliche Schwierigkeit besteht darin, die Größe der einzelnen „Eimer“ maßzuschneidern, Sie einige Profilierung dafür brauchen werden, so wäre es besser, wenn Ihre Implementierung dort einige Anpassungen erlaubt (wie es auf der Architektur abhängen wird, auf dem der Code ausgeführt).

Answer 3

Warum wollen Sie diese in einem Satz gespeichert werden sollen. Es sei denn, Sie etwas aus dem üblichen heraus zu tun, wird es eine kleine Anzahl von Threads sein. Der Aufwand zur Herstellung eines Satzes Aufrechterhaltung ist wahrscheinlich höher als sie gerade in einem Vektor setzen und eine lineare Suche zu tun.

Wenn das Suchen häufiger als das Hinzufügen und Löschen passieren wird, können Sie nur eine sortierte Vektor verwenden. Es gibt einen Operator lower_bound() eine binäre Suche zu tun. Dies ist die gleiche Komplexität wie ein Satz suchen, und sollte niedrigen Aufwand für kleine Datenmengen.

Wenn Sie noch brauchen, um dies zu tun, wie wäre es nur um es als sizeof Behandlung (boost :: thread: id). Bytes sind und auf denen

In diesem Beispiel wird davon ausgegangen, dass die Größe der boost :: Thread :: id ein Vielfaches der Größe eines int ist, und dass es keine Verpackung, und keine virtuellen Funktionen. Wenn das nicht wahr ist, wird es geändert werden, oder wird nicht funktionieren.

EDIT: Ich habe einen Blick auf die boost::thread::id Klasse, und es hat eine boost::shared_pointer<> als Mitglied hat, so dass der Code unten ist schrecklich gebrochen. Ich denke, dass die einzige Lösung, die Autoren von boost::thread fügen Sie eine Hash-Funktion zu haben. Ich bin das Beispiel nur für den Fall seiner nützlich in einem anderen Kontext zu verlassen.

boost::thread::id id;
unsigned* data;
// The next line doesn't do anything useful in this case.
data = reinterpret_cast<unsigned *>(&id);
unsigned hash = 0;

for (unsigned int i = 0; i < sizeof(boost::thread::id)/4; i++)
  hash ^= data[i];

Answer 4

Einige Jahre zu spät, diese Frage zu beantworten, aber dies zeigte sich als relevanteste wenn einen Schub zu setzen versucht :: thread :: id in einem std :: unordered_map als Schlüssel. Erhalten des nativen Griff wurde mit der Ausnahme ein guter Vorschlag in der akzeptierten Antwort, dass es für this_thread nicht verfügbar ist.

Stattdessen erhöhen für einige Zeit hat eine hash_value für Thread :: id, so dass dies funktionierte gut für mich:

namespace boost {
  extern std::size_t hash_value(const thread::id &v);
}

namespace std {
  template<>
  struct hash<boost::thread::id> {
    std::size_t operator()(const boost::thread::id& v) const {
      return boost::hash_value(v);
    }
  };
}

Natürlich müssen gegen libboost_thread Bibliothek verbinden.

Answer 5

Sie können Klasse erstellen, die Zuordnung zwischen Thread tut :: id und etwas (Bsp .: ganze Zahlen), die Sie als Hash verwenden können. der einzige Nachteil ist, dass Sie in dem System dort sicherzustellen, muss nur eine Instanz von Mapping-Objekt ist.