TR1 :: hash per boost :: :: filo id?

Question

Ho iniziato a utilizzare la classe unordered_set dallo spazio dei nomi tr1 per accelerare l'accesso contro la pianura (ad albero) STL map. Tuttavia, ho voluto per memorizzare i riferimenti alle discussioni ID di spinta (boost::thread::id), e si rese conto che l'API di questi identificatori è così opaco che non è possibile ottenere in modo chiaro 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 era 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, applicare l'hash per la stringa risultante. Tuttavia, questo sembra essere meno efficiente che in realtà utilizzando la map<boost::thread::id> STL.

Quindi, le mie domande: si fa a trovare un modo migliore di fare questo? E 'una chiara incoerenza sia in spinta e non TR1 forzare l'esistenza di una classe hash<boost::thread::id>?

Grazie.

Answer 1

L'overhead di stringifying thread::id (solo per calcolare l'hash della stringa in 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 potrebbe essere: bastone con std :: map

Se assolutamente deve utilizzare contenitori non ordinate, cercare di usenative_handle_type al posto di thread::id, se possibile, cioè preferiscono tr1::unordered_map< thread::native_handle_type, ... >, invocando thread::native_handle() invece di thread::get_id() quando inserting e finding.

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. Si presuppone una profonda conoscenza dei meccanismi interni di attuazione thread::id. Otterrà maledetti in da altri sviluppatori. Non farlo se la manutenibilità è di alcuna preoccupazione! Anche l'applicazione di patch per aggiungere boost/thread/detail/thread.hpp size_t hash_value(const id& tid) come amico di thread::id è "migliore". :)

Answer 2

La domanda ovvia è perché si vuole utilizzare effettivamente un hash?

Capisco il problema con map / set per il codice critico prestazioni, anzi quei contenitori non sono molto di cache amichevole perché le voci potrebbero essere assegnati a molto diverse locazioni di memoria.

Come suggerito KeithB (Non voglio commentare sull'uso della rappresentazione binaria poiché nulla garantisce che 2 id hanno la stessa rappresentazione binaria dopo tutto ...), utilizzando un vector ordinato può accelerare il codice nel caso ci sia molto pochi oggetti.

vettori Ordinati / deque sono molto più di cache-friendly, tuttavia essi soffrono di una O (N) complessità sull'inserto / cancellazione a causa della copia coinvolti. Una volta raggiunto un paio di centinaia di discussioni (mai visto che molti tra l'altro), potrebbe far male.

C'è comunque, una struttura dati che cerca di associare i benefici da mappe e ordinati vettori: B + Albero .

È possibile vederlo come una mappa per la quale ogni nodo dovrebbe contenere più di un elemento (in ordine ordinato). vengono utilizzati solo i nodi foglia.

Per avere un po 'di più le prestazioni è possibile:

• Collegare 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 i nodi interal
• Cache l'ultima foglia accede nella radice, dopo tutto è probabile che sarà anche il successivo accesso.

Le prestazioni asintotici sono gli stessi che per la carta, perché è implementato come un albero binario bilanciato, ma perché i valori sono confezionati in gruppi, si sono codice può diventare più veloce per una costante.

La vera difficoltà è quella di adattare la dimensione di ogni "bucket", avrete bisogno di un po 'di profilazione per che così sarebbe meglio se l'implementazione ha permesso qualche personalizzazione lì (in quanto dipenderà l'architettura su cui il codice è eseguito).

Answer 3

Perché si desidera memorizzare questi in un set. A meno che non fare qualcosa di straordinario, ci sarà un piccolo numero di thread. L'overhead di mantenere un insieme è probabilmente superiore ma semplicemente inserendole in un vettore e facendo una ricerca lineare.

Se la ricerca avverrà più frequentemente di aggiunta e l'eliminazione, si può semplicemente utilizzare un vettore ordinato. C'è un lower_bound() di fare una ricerca binaria. Questa è la stessa complessità ricerca in una serie, e dovrebbe avere minori costi per piccole quantità di dati.

Se hai ancora bisogno di fare questo, come su proprio trattarlo come un sizeof (boost :: filo: id). Byte, e che operano su quelli

Questo esempio presuppone che la dimensione di boost :: filetto :: id è un multiplo della dimensione di un int, e che non v'è nessun imballaggio, e funzioni virtuali. Se questo non è vero, esso dovrà essere modificato, o non funziona affatto.

EDIT: ho preso uno sguardo alla classe di boost::thread::id, ed ha una boost::shared_pointer<> come membro, in modo che il codice qui sotto è orribilmente rotto. Credo che l'unica soluzione è quella di avere dei boost::thread gli autori aggiungere una funzione di hash. Sto lasciando l'esempio nel caso in cui il suo 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 4

Alcuni anni di ritardo a rispondere a questa domanda, ma questo si presentò come il più rilevante uno quando si cerca di mettere un boost :: :: filo id in uno std :: unordered_map come chiave. Ottenere la maniglia nativo è stato un buon suggerimento nella risposta accettata se non 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.

Answer 5

è possibile creare classe che fa la mappatura tra il filo :: id e qualcosa (es .: numeri interi), che è possibile utilizzare come hash. l'unico inconveniente è che è necessario assicurarsi non v'è una sola istanza di oggetto di mapping nel sistema.