tr1 :: hash para boost :: thread :: id?

Question

Empecé a utilizar la clase unordered_set desde el espacio de nombres tr1 para acelerar el acceso contra el STL simple (basado en árbol) map. Sin embargo, quería almacenar las referencias a los hilos ID en boost (boost::thread::id), y me di cuenta de que la API de esos identificadores es tan opaca que no se puede obtener claramente un hash de ella.

Sorprendentemente, impulso implementa partes del tr1 (incluyendo hash y unordered_set), pero que no define una clase de hash que es capaz de hash de un ID de hilo.

En cuanto a la documentación de boost::thread::id me encontré con que los ID de hilo puede ser la salida a una corriente, por lo 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()); 
    } 
}; 

es decir, serializarlo, se aplica el hash a la cadena resultante. Sin embargo, esto parece ser menos eficiente que usar el STL map<boost::thread::id>.

Entonces, mis preguntas: ¿encuentran una forma mejor de hacer esto? ¿Es una incongruencia clara tanto en boost como en tr1 no forzar la existencia de una clase hash<boost::thread::id>?

Gracias.

Answer 1

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 < hilo :: identificación, ...>

Si absolutamente deben usar recipientes no ordenados, tratar de utilizar native_handle_type en lugar de thread::id si es posible , es decir, prefiera tr1::unordered_map< thread::native_handle_type, ... >, invocando thread::native_handle() en lugar de thread::get_id() cuando insert ing y find ing.

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. Asume un conocimiento íntimo del funcionamiento interno de la implementación thread::id. Te hará maldecir por otros desarrolladores. ¡No lo haga si la mantenibilidad es una preocupación! Incluso el parche boost/thread/detail/thread.hpp para agregar size_t hash_value(const id& tid) como amigo de thread::id es "mejor". :)

Answer 2

¿Por qué quiere almacenar estos en un conjunto. A menos que esté haciendo algo fuera de lo común, habrá un pequeño número de hilos. La sobrecarga de mantener un conjunto es probablemente más alta que solo ponerlos en un vector y hacer una búsqueda lineal.

Si la búsqueda ocurrirá con más frecuencia que la adición y eliminación, puede utilizar un vector ordenado. Hay un operador < definido para boost :: thread :: id, por lo que puede ordenar el vector (o insertarlo en el lugar correcto) después de cada adición o eliminación, y usar lower_bound() para hacer una búsqueda binaria. Esta es la misma complejidad que buscar un conjunto, y debe tener una sobrecarga menor para pequeñas cantidades de datos.

Si aún necesita hacer esto, ¿qué le parece tratarlo como un tamaño de bytes (boost :: thread: id), y operando en esos.

En este ejemplo, se supone que el tamaño de boost :: thread :: id es un múltiplo del tamaño de un int, y que no hay embalaje ni funciones virtuales. Si eso no es cierto, tendrá que ser modificado, o no funcionará en absoluto.

EDIT: Eché un vistazo a la clase boost::thread::id, y tiene un boost::shared_pointer<> como miembro, por lo que el código siguiente está horriblemente roto. Creo que la única solución es hacer que los autores de boost::thread agreguen una función hash. Dejo el ejemplo por si acaso es útil en 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]; 

Answer 3

La pregunta obvia es ¿por qué querrías usar realmente un hash?

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

Como sugirió KeithB (no comentaré sobre el uso de la representación binaria ya que nada garantiza que 2 ID tengan la misma representación binaria después de todo ...), utilizando un vector ordenado puede acelerar el código en caso de que haya pocos artículos.

Los vectores ordenados/deques son mucho más compatibles con la memoria caché, sin embargo, tienen una O (N) complejidad en la inserción/borrado debido a la copia involucrada. Una vez que alcanzas un par de cientos de hilos (nunca visto tantos por cierto), podría doler.

Sin embargo, existe una estructura de datos que intenta asociar los beneficios de los mapas y vectores ordenados: B+Tree.

Puede verlo como un mapa para el cual cada nodo contendría más de un elemento (en orden ordenado). Solo se usan los nodos de hoja.

para conseguir un poco más de rendimiento se puede:

• Enlace las hojas de forma lineal: es decir, la raíz almacena un puntero a la primera y última hoja y las hojas mismas están interconectados, por lo que los viajes lineal omiten por completo el interal nodos.
• Guarda en caché la última hoja visitada en la raíz, después de todo, es probable que también sea la siguiente a la que se acceda.

Las prestaciones asintóticas son las mismas que para el mapa, porque está implementado como un árbol binario equilibrado, pero debido a que los valores están empaquetados en grupos, su código puede volverse más rápido por una constante.

La dificultad real es adaptar el tamaño de cada "cubo", necesitará algunos perfiles para eso, por lo que sería mejor si su implementación permitiera alguna personalización allí (ya que dependerá de la arquitectura en la que el código es ejecutado).

Answer 4

puede crear una clase que haga un mapeo entre thread :: id y algo (por ej .: enteros), que puede usar como hash. el único inconveniente es que debe asegurarse de que solo haya una instancia de objeto de mapeo en el sistema.

Answer 5

Algunos años tarde para responder a esta pregunta, pero esta apareció como la más relevante al tratar de poner un impulso :: thread :: id en un std :: unordered_map como clave.Obtener el identificador nativo fue una buena sugerencia en la respuesta aceptada, excepto que no está disponible para this_thread.

lugar por algún tiempo impulsar tiene una rosca para hash_value :: 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.