std :: mappa per piccole raccolte sparse

Question

Data una struttura MyData, di cui esistono molti esempi (direi diversi milioni al massimo), per ogni istanza devo memorizzare un membro che può contenere valori per un massimo di 8 chiavi . La chiave sarà sempre una a distanza 0-7 ei valori saranno sempre un punto 3D di float (chiamiamolo Point3).

Al massimo, conterrebbe:

Key | Value 
------------- 
0 | [x,y,z] 
1 | [x,y,z] 
2 | [x,y,z] 
3 | [x,y,z] 
4 | [x,y,z] 
5 | [x,y,z] 
6 | [x,y,z] 
7 | [x,y,z] 

Tuttavia, nel 99,9% dei casi conterrà 0 o 1 coppie di valori-chiave, per esempio:

Key | Value 
------------- 
1 | [x,y,z] 

Come posso determinare in modo efficiente l'overhead di memoria, se presente, di memorizzare un valore a valore singolo o vuoto std::map<int, Point3>, rispetto alla memorizzazione di un array di 8 Point3 (4 byte per float * 3 valori * 8 slot = 96 byte) e un singolo BYTE con bit per quali slot contengono valori significativi?

In generale, la mia domanda è qual è l'overhead di memoria di uno spazio vuoto o quasi vuoto std::map?

Answer 1

L'overhead di memoria di una mappa non è che non valido. In genere si tratta di poche parole per nodo. Usare una mappa per iniziare sarebbe sicuramente OK sotto la regola "nessuna ottimizzazione prematura".

Detto questo, quando si esegue l'ottimizzazione, la mappa sarà in cima all'elenco di strutture dati da sostituire. Ma a quel punto, puoi profilare tutte le diverse operazioni che usi effettivamente. Con quale frequenza cambiano le chiavi e/o i valori? Questa è un'informazione cruciale da sapere prima di ottimizzare.

[modifica] Se dovessi suggerire una struttura, sarebbe un vettore di std::pair<int, Point3D>. La ragione è che questo probabilmente fornisce oggetti a 16 byte adatti all'allineamento. Non mi preoccuperei di ordinare le chiavi, perché è utile solo per i nodi dello 0,1% che hanno più coppie chiave/valore.

Answer 2

Dai un'occhiata al post del blog this. Esiste un'analisi molto approfondita dell'utilizzo della memoria di diversi contenitori STL (incluso std::map) e vengono prese in considerazione diverse piattaforme/compilatori.

Nel STL 64 bit che viene fornito con Visual Studio 2010 (Visual C++ 10):

---

mappa utilizza 32 byte per l'oggetto mappa stessa, allora ogni nodo della mappa è 26 byte più grande la dimensione dell'oggetto contenuto (probabilmente 32 byte dopo aver preso in considerazione l'allineamento e lo spreco). Il numero di nodi mappa necessari per una mappa è 1 più della dimensione della mappa.