tr1 :: hachage pour boost :: thread :: id ?

Question

J'ai commencé à utiliser le unordered_set classe de la tr1 espace de noms pour accélérer l'accès au STL simple (arborescent) map.Cependant, je voulais stocker les références aux ID de thread dans boost (boost::thread::id), et j'ai réalisé que l'API de ces identifiants est si opaque que vous ne pouvez pas en obtenir clairement un hachage.

Étonnamment, boost implémente des parties du tr1 (y compris hash et unordered_set), mais il ne définit pas de classe de hachage capable de hacher un ID de thread.

En regardant la documentation de boost::thread::id J'ai découvert que les ID de thread peuvent être générés dans un flux. Ma solution pour effectuer le hachage était donc la suivante :

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());
    }
};

Autrement dit, sérialisez-le, appliquez le hachage à la chaîne résultante.Cependant, cela semble moins efficace que d'utiliser réellement le STL. map<boost::thread::id>.

Alors, mes questions :Trouvez-vous une meilleure façon de procéder ?Est-ce une incohérence évidente dans boost et tr1 de ne pas forcer l'existence d'un hash<boost::thread::id> classe?

Merci.

Answer 1

Les frais généraux liés à la stringification thread::id (uniquement pour calculer le hachage de chaîne par la suite) est, comme vous l'avez presque dit vous-même, astronomique par rapport aux avantages en termes de performances d'un tr1::unordered_map pourrait conférer vis-à-vis std::map.La réponse courte serait donc : restez fidèle à std::map< thread::id, ...>

Si tu absolument doit utiliser des conteneurs non commandés, Essayez d'utilisernative_handle_type au lieu de thread::id si possible, c'est-à-direpréférer tr1::unordered_map< thread::native_handle_type, ... >, invoquant thread::native_handle() au lieu de thread::get_id() quand inserting et finding.

NE tentez PAS quelque chose comme ce qui suit:

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());
   }
};

Cela pourrait fonctionner, mais il est extrêmement fragile et constitue une bombe à retardement presque garantie.Cela suppose une connaissance approfondie du fonctionnement interne du thread::id mise en œuvre.Cela vous fera maudire par d'autres développeurs.Ne le faites pas si la maintenabilité pose problème !Même les correctifs boost/thread/detail/thread.hpp ajouter size_t hash_value(const id& tid) en tant qu'ami de thread::id est mieux".:)

Answer 2

La question est évidente: pourquoi voudriez-vous réellement utiliser un hachage?

Je comprends la question avec map / set pour la performance code critique, en effet ces conteneurs ne sont pas cache très sympathique car les éléments peuvent être attribués à des emplacements de mémoire très différents.

Comme suggéré KeithB (je ne commenterai pas sur l'utilisation de la représentation binaire puisque rien ne garantit que 2 ids ont la même représentation binaire après tout ...), en utilisant un vector peut accélérer Sorted le code dans le cas où il y a très peu articles.

Sorted vecteurs / Deques sont beaucoup plus convivial aux caches, mais ils souffrent d'un O (N) complexité à l'insertion / effacer en raison de la copie concernée. Une fois que vous atteignez un fils quelques centaines (jamais vu que beaucoup d'ailleurs), il pourrait faire du mal.

Il y a cependant une structure de données qui tente d'associer les avantages des cartes et triées vecteurs: B + Arbre .

Vous pouvez le voir comme une carte pour lequel chaque noeud contiendrait plus d'un élément (en ordre de tri). Seuls les nœuds feuilles sont utilisés.

Pour obtenir un peu plus les performances, vous pouvez:

• Lier les feuilles linéaire:.-À-dire la racine met en cache un pointeur vers la première et la dernière feuille et les feuilles sont eux-mêmes reliés entre eux, de sorte que Voyage linéaire complètement court-circuiter les noeuds INTERAL
• Cache la dernière feuille accédé à la racine, après tout il est probable que aura aussi le prochain accès.

Les performances asymptotiques sont les mêmes que pour la carte, car il est mis en œuvre comme un arbre binaire équilibré, mais parce que les valeurs sont emballées dans des groupes, vous êtes code peut devenir plus rapide par une constante.

La vraie difficulté est d'adapter la taille de chaque « seau », vous aurez besoin d'un profilage pour que donc il serait préférable que votre mise en œuvre a permis il y a une certaine personnalisation (car elle dépendra de l'architecture sur laquelle le code est exécuter).

Answer 3

Pourquoi voulez-vous conserver dans un ensemble. À moins que vous faire quelque chose hors de l'ordinaire, il y aura un petit nombre de threads. Les frais généraux du maintien d'un ensemble est probablement plus élevé que de les mettre dans un vecteur et de faire une recherche linéaire.

Si la recherche se produira plus fréquemment que l'ajout et la suppression, vous pouvez simplement utiliser un vecteur trié. Il y a un lower_bound() pour faire une recherche binaire. Ceci est la même complexité que la recherche d'un ensemble, et devrait avoir moins de frais généraux pour les petites quantités de données.

Si vous avez encore besoin de faire cela, que diriez-vous simplement traiter comme un sizeof (boost :: thread: id). Octets, et fonctionnant sur les

Cet exemple suppose que la taille de boost :: :: id fil est un multiple de la taille d'un int, et qu'il n'y a pas d'emballage, et aucune fonction virtuelle. Si ce n'est pas vrai, il devra être modifié, ou ne fonctionnera pas du tout.

EDIT: Je pris un coup d'œil à la classe boost::thread::id, et il a une boost::shared_pointer<> en tant que membre, de sorte que le code ci-dessous est horriblement brisée. Je pense que la seule solution est d'avoir les auteurs de boost::thread ajouter une fonction de hachage. Je quitte l'exemple juste au cas où son utilité dans un autre contexte.

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

Quelques années en retard à répondre à cette question, mais cela est apparu comme le plus pertinent en essayant de mettre un coup de pouce :: fil :: id dans un std :: unordered_map comme la clé. Obtenir la poignée native a été une bonne suggestion dans la réponse acceptée, sauf qu'il ne soit pas disponible pour this_thread.

Au lieu de cela augmenter pendant un certain temps a un hash_value pour le fil :: id, donc cela a bien fonctionné pour moi:

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);
    }
  };
}

Bien sûr, besoin de créer un lien avec les bibliothèques libboost_thread.

Answer 5

vous pouvez créer la classe qui fait correspondance entre fil :: id et quelque chose (ex .: entiers), que vous pouvez utiliser comme hachage. le seul inconvénient est que vous devez assurer qu'il n'y a qu'une seule instance d'objet de mappage dans le système.