Mappa hash C/C++ ad altissime prestazioni (tabella, dizionario)

Question

Ho bisogno di mappare le chiavi primitive (int, forse lunghe) per strutturare i valori in una struttura dati mappa hash ad alte prestazioni.

Il mio programma avrà alcune centinaia di queste mappe e ogni mappa avrà generalmente al massimo qualche migliaio di voci. Tuttavia, le mappe saranno "rinfrescanti" o "sbattendo" costantemente; immagina di elaborare milioni di messaggi add e delete al secondo.

Quali librerie in C o C++ hanno una struttura dati adatta a questo caso d'uso? Oppure, come consiglieresti di costruirti da solo? Grazie!

Answer 1

Si consiglia di provare Google SparseHash (o la versione C11 Google SparseHash-c11) e vedere se è adatto alle proprie esigenze. Hanno un'implementazione efficiente per la memoria e una ottimizzata per la velocità. Ho fatto un benchmark molto tempo fa, era la migliore implementazione di hashtable disponibile in termini di velocità (ma con degli svantaggi).

Answer 2

Quali librerie in C o C++ hanno una struttura dati adatta a questo caso d'uso? Oppure, come consiglieresti di costruirti da solo? Grazie!

Controlla LGPL'd Judy arrays. Non mi sono mai abituato, ma mi è stato pubblicizzato in poche occasioni.

Si può anche provare a confrontare i contenitori STL (std :: hash_map, ecc.). A seconda della piattaforma/dell'implementazione e dell'ottimizzazione del codice sorgente (preallocare quanto più è possibile la gestione dinamica della memoria è costoso) potrebbero essere abbastanza performanti.

Inoltre, se le prestazioni della soluzione finale superano il costo della soluzione, è possibile provare a ordinare al sistema RAM sufficiente per inserire tutto in semplici array. Le prestazioni di accesso per indice sono imbattibili.

Le operazioni di aggiunta/eliminazione sono molto (100 volte) più frequenti rispetto all'operazione di ricezione.

Questo suggerisce di concentrarsi sul miglioramento degli algoritmi. Se i dati sono solo scritti, non letti, perché mai scriverli?

Answer 3

Basta usare boost::unordered_map (o tr1 ecc.) Per impostazione predefinita. Poi profila il tuo codice e vedi se quel codice è il collo di bottiglia. Solo allora vorrei suggerire di analizzare con precisione le tue esigenze per trovare un sostituto più veloce.

Answer 4

Prima verifica se soluzioni esistenti come libmemcache soddisfano le tue necessità.

Altrimenti ...

mappe Hash sembra essere la risposta definitiva al vostro requisito. Fornisce o (1) ricerca basata sui tasti. La maggior parte delle librerie STL fornisce una sorta di hash in questi giorni. Quindi usa quello fornito dalla tua piattaforma.

Una volta eseguita la parte, è necessario testare la soluzione per verificare se l'algoritmo di hashing predefinito è sufficientemente buono per le proprie esigenze.

Se non lo è, si dovrebbe esplorare alcuni buoni algoritmi veloci di hashing trovati in rete

1. buon numero primo vecchio moltiplicare algo
2. http://www.azillionmonkeys.com/qed/hash.html
3. http://burtleburtle.net/bob/
4. http://code.google.com/p/google-sparsehash/

Se ciò non è sufficiente, è possibile eseguire il rolling di un modulo di hashing da solo, che risolve il problema che hai visto con i contenitori STL che hai testato e uno degli algoritmi di hashing sopra. Assicurati di pubblicare i risultati da qualche parte.

Oh ed è interessante che tu abbia più mappe ... forse puoi semplificare avendo la tua chiave come un numero di 64 bit con i bit alti usati per distinguere la mappa a cui appartiene e aggiungere tutte le coppie di valori chiave a un gigante hash. Ho visto hash che hanno centinaia o migliaia di simboli che funzionano perfettamente sull'algoritmo di hashing dei numeri primi.

È possibile verificare come questa soluzione esegue rispetto a centinaia di mappe .. Credo che potrebbe essere meglio da un punto di vista della memoria profiling ... per favore inviare i risultati da qualche parte se si arriva a fare questo esercizio

credo che più che l'algoritmo di hashing potrebbe essere la costante aggiunta/cancellazione della memoria (può essere evitato?) e il profilo di utilizzo della cache della CPU che potrebbe essere più fondamentale per le prestazioni della vostra applicazione

buona fortuna

Answer 5

Prova tabelle hash da Miscellaneous Container Templates. Il numero di telefono closed_hash_map ha all'incirca la stessa velocità di quello di Google dense_hash_map, ma è più facile da usare (nessuna restrizione sui valori contenuti) e ha anche altri vantaggi.

Answer 6

da fonti Android (quindi Apache 2 licenza)

https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils

sguardo hashmap.c, sceglie include/cutils/hashmap.h, se non hai bisogno di filo di sicurezza è possibile rimuovere il codice mutex , un'implementazione di esempio è in libcutils/str_parms.c

Answer 7

Se si dispone di un programma con multithreading, è possibile trovare alcune tabelle hash utili in intel thread building blocks library. Ad esempio, tbb :: concurrent_unordered_map ha la stessa API di std :: unordered_map, ma le sue funzioni principali sono thread-safe.

Anche dare un'occhiata a facebook folly library, ha prestazioni elevate simultanee hash table e skip list.

Answer 8

http://incise.org/hash-table-benchmarks.html gcc ha un'implementazione molto molto buona. Tuttavia, la mente che deve rispettare una pessima decisione standard:

Se un rimaneggiamento accade, tutti gli iteratori non sono considerati validi, ma i riferimenti e puntatori ai singoli elementi restano valide. Se non viene eseguito alcun rifacimento effettivo , nessuna modifica.

http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/

Ciò significa in pratica la norma dice che l'attuazione deve essere basata su liste concatenate. Impedisce l'indirizzamento aperto con prestazioni migliori.

Penso che Google Sparse utilizzi l'indirizzamento aperto, sebbene in questi benchmark solo la versione densa superi la concorrenza. Tuttavia, la versione sparsa supera di gran lunga qualsiasi concorrenza nell'utilizzo della memoria. (inoltre non ha alcun plateau, pura linea retta rispetto al numero di elementi)

Answer 9

Suggerirei uthash. Basta includere #include "uthash.h" quindi aggiungere un UT_hash_handle alla struttura e scegliere uno o più campi nella struttura per agire come la chiave. Una parola sulla performance here.

Answer 10

khash è molto efficiente. C'è un benchmark dettagliato dell'autore: https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/ e mostra anche khash beat molte altre librerie di hash.