LevelDB vs. std :: map

Question

Nella nostra applicazione che usiamo std::map da memorizzare (chiave, valore) dei dati e l'uso di serializzazione per memorizzare i dati su disco. Con questo approccio stiamo scoprendo che il disco I / O è la prestazione collo di bottiglia e trovare i valori utilizzando la chiave non è molto veloce.

mi sono imbattuto LevelDB e pensando di usarlo. Ma ho alcune domande.

1. la documentazione del LevelDB afferma che il suo fatto per (string, string) valore chiave coppia. Vuol dire che non posso usare per coppie di valori chiave personalizzati?
2. Sembra che la differenza tra std::map e LevelDB è che LevelDB è persistente e std::map opere in memoria. Quindi vuol dire il disco I / O collo di bottiglia sarà più problematico per LevelDB.

In particolare si fa a spiegare se LevelDB potrebbe essere migliore scelta di std::map?

PS: Ho provato ad utilizzare hash_maps ma sembra essere più lento di std::map

Answer 1

LevelDB fa proprio qualcosa di diverso std :: map.

Sei davvero dicendo che vuoi persistenza (ad alte prestazioni) per std :: map?

• guarda std :: map con un allocatore personalizzato. Allocare le voci da una memoria mappata regionali e l'utilizzo fsync per assicurare l'informazione colpisce il disco in momenti strategici in tempo.

  • mmap
  • spinta iostreams file mappati in memoria

• forse che si combinano con EASTL (che vanta una std :: map più veloce e prospera con ripartitori personalizzati - in realtà non hanno allocatore predefinito)

  • EASTL

• guarda accordare la hash_map (std :: unorderded_map); se hash_maps sono più lenti, si dovrebbe guardare in (a) messa a punto loadfactor (b) funzione di hash

  • docs

• , ultimo ma non meno importante: valutare l'uso di Boost serializzazione per la serializzazione binaria della mappa (qualunque implementazione hai scelto). Nella mia esperienza incremento delle prestazioni serializzazione è in cima alla lista.

  • Boost serializzazione

Answer 2

Quello che stai facendo ora è questa:

Diciamo che avete 1000000 record di un file. Hai letto il tutto file in std :: map, questo richiede circa ~ 1000000 operazioni. Si utilizza Trova / inserisce per individuare e / o inserire un elemento, questo richiede tempo logaritmica (circa 20 confronti). E ora salvare l'intero file di nuovo, il trasferimento di tutte queste 1000000 record al file.

Il problema è che beneficiate assolutamente nulla di usare std :: map. std :: map garantisce un modo rapido volte (logaritmica) di ricerca, ma l'inizializzazione e serializzazione l'intera mappa per ogni annulla di ricerca i suoi benefici.

Quello che vi serve è uno ridisegnare si programma in modo da caricare la carta una volta in avvio e serializzare una volta al termine. O, forse, se avete bisogno la semantica del database, andare a fare un'implementazione del database reale. Io suggerisco di usare SQLite, anche se potrebbe essere LevelDB altrettanto buono per te.