tr1::hash para boost::subproceso::id?

StackOverflow https://stackoverflow.com/questions/772192

Pregunta

Empecé a usar el unordered_set la clase de la tr1 espacio de nombres para acelerar el acceso en contra de la llanura (basada en el árbol) STL map.Sin embargo, yo quería almacenar referencias a las roscas de IDENTIFICACIÓN de refuerzo (boost::thread::id), y se dio cuenta de que la API de los identificadores es tan opaco que no se puede claramente obtener un hash de la misma.

Sorprendentemente, impulsar implementa partes de la tr1 (incluyendo hash y unordered_set), pero no define un hash de la clase que es capaz de hash de un IDENTIFICADOR de subproceso.

Buscando en la documentación de boost::thread::id He encontrado que el hilo IDs puede ser la salida de un arroyo, así que mi solución para hacer hash era una especie de:

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

Que es, serializar, aplicar el hash de la cadena resultante.Sin embargo, esto parece ser menos eficiente que en realidad el uso de la STL map<boost::thread::id>.

Así que, mis preguntas:¿Encontrar una mejor manera de hacer esto?Es una clara inconsistencia en tanto impulso y tr1 no forzar la existencia de un hash<boost::thread::id> la clase?

Gracias.

¿Fue útil?

Solución

La sobrecarga de stringifying thread::id (sólo para calcular el hash de la cadena después) es, como usted mismo ha dicho casi, astronómico en comparación con cualquier otra prestación que beneficia a un tr1::unordered_map podría conferir vis-a-vis std::map. Así que la respuesta corta sería: palo con std :: mapa <:: Identificación del hilo, ...>

Si absolutamente debe utilizar recipientes no ordenados, tratan de usenative_handle_type en lugar de thread::id si es posible, es decir, prefieren tr1::unordered_map< thread::native_handle_type, ... >, invocando thread::native_handle() en lugar de thread::get_id() cuando inserting y finding.

NO intente algo como lo siguiente: : 

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

Podría funcionar, pero es extremadamente frágil y una bomba de tiempo casi garantizado. Supone un conocimiento profundo del funcionamiento interno de la implementación thread::id. Se obtendrá malditos al por otros desarrolladores. No hacerlo si es mantenimiento de cualquier preocupación! Incluso parches boost/thread/detail/thread.hpp añadir size_t hash_value(const id& tid) como amigo de thread::id es "mejor". :)

Otros consejos

La pregunta obvia es ¿por qué quieres usar un hash ?

Entiendo el problema con map / set para el rendimiento código crítico, de hecho, los contenedores no son muy caché, ya que los elementos pueden ser asignados a diferentes ubicaciones de la memoria.

Como KeithB sugerido (no voy a comentar sobre el uso de la representación binaria, ya que nada garantiza que 2 identificadores tienen la misma representación binaria, después de todo...), el uso de un criterio de vector puede acelerar el código en caso de que hay muy pocos elementos.

Clasificados de vectores / deques son mucho más caché-amigable, sin embargo sufren de un O(N) la complejidad en insertar/borrar debido a la copia de los involucrados.Una vez que llegue a un par de cientos de hilos (nunca había visto que a muchos por el camino), se podría dañar.

Sin embargo, existe una estructura de datos que se intenta asociar los beneficios de los mapas y se ordenan los vectores:el En Un Árbol B+.

Puedes verlo como un mapa para que cada nodo contiene más de un elemento (en orden).Sólo los nodos hoja se utilizan.

Para conseguir algo más de rendimiento en el que puede:

  • Enlace de las hojas lineal:es decir, la raíz almacena en caché un puntero a la primera y la última hoja y las hojas están interconectados a sí mismos, por lo que el recorrido completo de la derivación de la interal nodos.
  • Almacenar en caché el último acceso de la hoja en la raíz, después de todo, es probable que también va a ser el siguiente acceso.

La asintótica de las actuaciones son los mismos que para el mapa, debido a que está implementado como un Árbol Binario Equilibrado, pero debido a que los valores están empaquetados en grupos, estás código puede llegar a ser más rápido por una constante.

La verdadera dificultad es adaptar el tamaño de cada "cubo", usted necesitará algunos perfiles para que así sería mejor si su implementación permitió a algunos de personalización de allí (ya que dependerá de la arquitectura en la que se ejecute el código).

¿Por qué desea almacenar estos en un conjunto. A menos que haga algo fuera de lo común, habrá un pequeño número de hilos. La sobrecarga de mantener un conjunto es probablemente mayor que simplemente ponerlos en un vector y haciendo una búsqueda lineal.

Si la búsqueda va a ocurrir con mayor frecuencia que agregar y eliminar, sólo puede utilizar un vector ordenados. Hay un lower_bound() hacer una búsqueda binaria. Esta es la misma complejidad que buscar un conjunto, y debe tener una menor carga para las pequeñas cantidades de datos.

Si usted todavía tiene que hacer esto, ¿por qué simplemente tratándolo como un sizeof (boost :: hilo: id). Bytes, y que operan en los

este ejemplo se supone que el tamaño de impulso :: hilo :: id es un múltiplo del tamaño de un int, y que no hay embalaje, y no hay funciones virtuales. Si eso no es verdad, tendrá que ser modificado, o no funciona en absoluto.

EDIT: Me tomó un vistazo a la clase boost::thread::id, y tiene un boost::shared_pointer<> como miembro, por lo que el código de abajo es terriblemente roto. Creo que la única solución es hacer que los autores de boost::thread agregar una función hash. Estoy dejando el ejemplo en caso de que su utilidad en algún otro contexto. 

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];

Algunos años más tarde para responder a esta pregunta, pero esto se presentó como la más relevante cuando se trata de uno poner un impulso :: hilo :: id en un std :: unordered_map como clave. Recibiendo el mango nativa fue una buena sugerencia en la respuesta aceptada, excepto que no está disponible para this_thread.

En lugar impulsar por algún tiempo tiene una hash_value para el hilo :: identificación, por lo que este funcionó bien para mí: 

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

Por supuesto, tienen que enlazar con la biblioteca libboost_thread.

puede crear la clase que hace el mapeo entre la rosca :: Identificación y algo (ej .: números enteros), que se puede utilizar como hash. el único inconveniente es que debe asegurarse de que sólo hay una instancia de objeto de asignación en el sistema.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top