Wie kann ich den Speicherverbrauch von std::map abschätzen?

Question

Ich habe zum Beispiel eine std::map mit bekannter sizeof(A) und sizeof(B), wobei die map N Einträge enthält. Wie würden Sie den Speicherverbrauch schätzen? Ich würde sagen, es ist etwas wie

(sizeof(A) + sizeof(B)) * N * factor

Aber was ist der Faktor? Eine andere Formel vielleicht?

Vielleicht ist es einfacher, nach einer Obergrenze zu fragen?

Answer 1

Die Schätzung läge näher bei

(sizeof(A) + sizeof(B) + ELEMENT_OVERHEAD) * N + CONTAINER_OVERHEAD

Für jedes hinzugefügte Element fällt ein Overhead an, und es gibt auch einen festen Overhead für die Pflege der Datenstruktur, die für die Datenstruktur zum Speichern der Karte verwendet wird. Dies ist typischerweise ein binärer Baum, wie z.B. ein Rot-Schwarzer Baum . Zum Beispiel in der GCC C++ STL Implementierung ELEMENT_OVERHEAD wäre sizeof(_Rb_tree_node_base) y CONTAINER_OVERHEAD wäre sizeof(_Rb_tree) . Zu der obigen Abbildung sollten Sie auch den Overhead der Speicherverwaltungsstrukturen hinzufügen, die für die Speicherung der Elemente der Karte verwendet werden.

Es ist wahrscheinlich einfacher, eine Schätzung vorzunehmen, indem Sie den Speicherverbrauch Ihres Codes für verschiedene große Sammlungen messen.

Answer 2

Sie könnten verwenden MemTrack von Curtis Bartley. Es ist ein Speicherzuweiser, der den Standardzuweiser ersetzt und die Speichernutzung bis hin zur Art der Zuweisung verfolgen kann.

Ein Beispiel für eine Ausgabe:

-----------------------
Memory Usage Statistics
-----------------------

allocated type                        blocks          bytes  
--------------                        ------          -----  
struct FHRDocPath::IndexedRec          11031  13.7% 2756600  45.8%
class FHRDocPath                       10734  13.3%  772848  12.8%
class FHRDocElemPropLst                13132  16.3%  420224   7.0%
struct FHRDocVDict::IndexedRec          3595   4.5%  370336   6.2%
struct FHRDocMDict::IndexedRec         13368  16.6%  208200   3.5%
class FHRDocObject *                      36   0.0%  172836   2.9%
struct FHRDocData::IndexedRec            890   1.1%  159880   2.7%
struct FHRDocLineTable::IndexedRec       408   0.5%  152824   2.5%
struct FHRDocMList::IndexedRec          2656   3.3%  119168   2.0%
class FHRDocMList                       1964   2.4%   62848   1.0%
class FHRDocVMpObj                      2096   2.6%   58688   1.0%
class FHRDocProcessColor                1259   1.6%   50360   0.8%
struct FHRDocTextBlok::IndexedRec        680   0.8%   48756   0.8%
class FHRDocUString                     1800   2.2%   43200   0.7%
class FHRDocGroup                        684   0.8%   41040   0.7%
class FHRDocObject * (__cdecl*)(void)     36   0.0%   39928   0.7%
class FHRDocXform                        516   0.6%   35088   0.6%
class FHRDocTextColumn                   403   0.5%   33852   0.6%
class FHRDocTString                      407   0.5%   29304   0.5%
struct FHRDocUString::IndexedRec        1800   2.2%   27904   0.5%

Answer 3

Wenn Sie wirklich wissen wollen, wie groß der Speicherbedarf zur Laufzeit ist, verwenden Sie einen benutzerdefinierten Allokator und geben Sie ihn bei der Erstellung der Map an. Siehe Josuttis' Buch und este Seite von ihm (für einen benutzerdefinierten Zuweiser).

Vielleicht ist es einfacher, nach einer Obergrenze zu fragen?

Die Obergrenze hängt von der genauen Implementierung ab (z. B. von der verwendeten Variante des Balanced Tree). Vielleicht können Sie uns sagen, warum Sie diese Informationen benötigen, damit wir Ihnen besser helfen können?

Answer 4

Ich musste diese Frage kürzlich für mich selbst beantworten und schrieb einfach ein kleines Benchmark-Programm mit std::map, das ich unter MSVC 2012 im 64-Bit-Modus kompilierte.

Eine Karte mit 150 Millionen Knoten beansprucht ~ 15 GB, was bedeutet, dass die 8 Byte L, 8 Byte R, 8 Byte int key und 8 Byte datum, insgesamt 32 Byte, beanspruchen etwa 2/3 des Speichers der Karte für interne Knoten, 1/3 für die Blätter.

Ich persönlich empfand dies als überraschend schlechte Speichereffizienz, aber es ist, wie es ist.

Ich hoffe, dies ist eine praktische Faustregel.

PS: Der Overhead einer std::map entspricht der Größe eines einzelnen Knotens AFAICT.

Answer 5

Die Formel lautet eher wie folgt:

(sizeof(A) + sizeof(B) + factor) * N

wobei Faktor die Gemeinkosten pro Eintrag ist. C++-Maps werden in der Regel als Rot-Schwarz-Bäume implementiert. Es handelt sich dabei um binäre Bäume, so dass es mindestens zwei Zeiger für die linken und rechten Knoten gibt. Außerdem wird es einige Implementierungselemente geben - wahrscheinlich einen Elternzeiger und einen "Farb"-Indikator, so dass der Faktor etwa so aussehen kann

(sizeof( RBNode *) * 3 + 1) / 2

All dies ist jedoch in hohem Maße von der Implementierung abhängig - um dies herauszufinden, müssen Sie den Code Ihrer eigenen Bibliotheksimplementierung untersuchen.