tr1 :: hash per boost :: thread :: id?

Question

Ho iniziato a utilizzare la classe dallo spazio dei nomi tr1 per accelerare l'accesso rispetto allo STL semplice (basato su albero) map. Tuttavia, volevo memorizzare i riferimenti all'ID thread in boost (boost::thread::id) e mi sono reso conto che l'API di quegli identificatori è così opaca da non poter ottenere chiaramente un hash di esso.

Sorprendentemente, spinta implementa parti del tr1 (tra cui hash e unordered_set), ma non definisce una classe hash che è in grado di hash un ID di thread.

Guardando la documentazione dei boost::thread::id ho trovato che gli ID di thread possono essere inviati a un ruscello, così la mia soluzione per fare hashing stato un po ':

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

Cioè, serializzare esso, si applicano l'hash al stringa risultante. Tuttavia, questo sembra essere meno efficiente rispetto all'utilizzo effettivo dell'STL map<boost::thread::id>.

Quindi, le mie domande: trovate un modo migliore per farlo? È una chiara incoerenza sia in boost che in tr1 di non forzare l'esistenza di una classe hash<boost::thread::id>?

Grazie.

Answer 1

L'overhead di stringifying thread::id (solo per calcolare l'hash stringa di seguito) è, come quasi detto tu, astronomico rispetto a qualsiasi prestazione a vantaggio di tr1::unordered_map potrebbe conferire vis-a-vis std::map. Quindi la risposta breve sarebbe: bastone con std :: map < filo :: id, ...>

Se assolutamente deve utilizzare contenitori non ordinate, tenta di utilizzare native_handle_type invece di thread::id, se possibile , ovvero preferisco tr1::unordered_map< thread::native_handle_type, ... >, invocando thread::native_handle() invece di thread::get_id() quando insert ing e find ing.

non tentare qualcosa di simile al seguente:

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

Potrebbe funzionare, ma è estremamente fragile e un bomba a tempo quasi garantito. Presuppone una conoscenza approfondita del funzionamento interno dell'implementazione thread::id. Ti verrà maledetto da altri sviluppatori. Non farlo se la manutenibilità è di qualche preoccupazione! Anche patching boost/thread/detail/thread.hpp per aggiungere size_t hash_value(const id& tid) come amico di thread::id è "migliore". :)

Answer 2

Perché vuoi memorizzarli in un set. A meno che tu non stia facendo qualcosa fuori dall'ordinario, ci sarà un piccolo numero di thread. Il sovraccarico del mantenimento di un set è probabilmente più alto del semplice metterli in un vettore e fare una ricerca lineare.

Se la ricerca si verifica più frequentemente rispetto all'aggiunta e all'eliminazione, è sufficiente utilizzare un vettore ordinato. Esiste un operatore < definito per boost :: thread :: id, quindi è possibile ordinare il vettore (o inserirlo nella posizione corretta) dopo ogni aggiunta o eliminazione e utilizzare lower_bound() per eseguire una ricerca binaria. Questa è la stessa complessità della ricerca di un set e dovrebbe avere un sovraccarico minore per piccole quantità di dati.

Se si ha ancora bisogno di fare questo, che ne dici di trattarlo come un byte sizeof (boost :: thread: id), e operare su quelli.

Questo esempio presuppone che la dimensione di boost :: thread :: id sia un multiplo della dimensione di un int, e che non vi sia alcun packing e nessuna funzione virtuale. Se ciò non è vero, dovrà essere modificato, o non funzionerà affatto.

MODIFICA: ho dato un'occhiata alla classe boost::thread::id e ha un boost::shared_pointer<> come membro, quindi il codice di seguito è orribilmente rotto. Penso che l'unica soluzione sia avere gli autori di boost::thread aggiungere una funzione di hash. Lascio l'esempio nel caso sia utile in qualche altro contesto.

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 domanda ovvia è perché si desidera utilizzare effettivamente un hash?

Capisco il problema con map/set per codice prestazioni critico, in effetti quei contenitori non sono molto cache-friendly perché gli elementi potrebbero essere allocati in posizioni di memoria molto diverse.

Come suggerito da KeithB (non voglio commentare l'uso della rappresentazione binaria poiché nulla garantisce che 2 ID abbiano la stessa rappresentazione binaria dopo tutto ...), utilizzando un ordinamento vector può accelerare il codice nel caso ci sia molto pochi oggetti.

I vettori/antecedenti ordinati sono molto più facili da usare nella cache, tuttavia presentano una complessità O (N) su inserimento/cancellazione a causa della copia coinvolta. Una volta raggiunto un paio di centinaia di thread (mai visto così tanti tra l'altro), potrebbe far male.

Esiste tuttavia una struttura dati che tenta di associare i vantaggi delle mappe e dei vettori ordinati: lo B+Tree.

È possibile visualizzarlo come una mappa per cui ogni nodo conterrebbe più di un elemento (in ordine). Vengono utilizzati solo i nodi foglia.

Per ottenere un po 'di prestazioni è possibile:

• link le foglie in modo lineare: cioè la radice memorizza nella cache un puntatore alla prima e ultima foglia e le foglie si stanno interconnessi, in modo che il viaggio lineare bypassare completamente l'interal i nodi.
• Cache l'ultima foglia accessibile nella radice, dopotutto è probabile che sia anche la successiva a cui si accede.

Le prestazioni asintotiche sono le stesse che per la mappa, perché è implementato come un albero binario bilanciato, ma poiché i valori sono raggruppati in gruppi, il codice può diventare più veloce di una costante.

La vera difficoltà è quella di adattare le dimensioni di ciascun "bucket", è necessario un po 'di profiling per questo, quindi sarebbe meglio se la tua implementazione permettesse qualche personalizzazione lì (dato che dipenderà dall'architettura su cui il codice è eseguito).

Answer 4

è possibile creare una classe che esegue il mapping tra thread :: id e qualcosa (es .: interi), che è possibile utilizzare come hash. l'unico svantaggio è che devi assicurarti che ci sia solo un'istanza dell'oggetto mappatura nel sistema.

Answer 5

Alcuni anni di ritardo per rispondere a questa domanda, ma questo si è rivelato il più rilevante quando si tenta di inserire un boost :: thread :: id in una std :: unordered_map come chiave.Ottenere l'handle nativo era un buon suggerimento nella risposta accettata, tranne per il fatto che non è disponibile per this_thread.

invece aumentare per qualche tempo ha un hash_value per filo :: id, quindi questo ha funzionato bene per me:

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

Naturalmente, la necessità di linkare libreria libboost_thread.