Nicht-monotoner Speicherverbrauch in Python2-Wörterbüchern

Question

Kann jemand diese nicht-monotonische Speicherverwendung eines Wörterbuchs in CPython 2.7 erklären?

>>> import sys 
>>> sys.getsizeof({}) 
280 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5}) 
280 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6}) 
1048 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7}) 
1048 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'e 
ight': 8}) 
664 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'e 
ight': 8, 'nine': 9}) 
664 

Python3 ist hier sinnvoll, es gibt die Größe von {'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7} als 480.

ich schon versucht, diese auf Ubuntu 15.10 und OS X 10.11.

Answer 1

TLDR: Die 6- und 7-Eintrag-Literale schreiben die Hashtabelle schlecht vor und vervierfachen dann die Größe bei der Größenänderung.

---

Wenn CPython 2.7 a literal dict auswertet, bevor es in den Einträgen beginnt Befüllen der Opcode den dict zu erstellen ist BUILD_MAP verwendet. Dies nimmt ein Argument, einen Hinweis dafür, wie viele Einträge die dict enthält, which it uses to presize the dict:

TARGET(BUILD_MAP) 
    { 
     x = _PyDict_NewPresized((Py_ssize_t)oparg); 
     PUSH(x); 
     if (x != NULL) DISPATCH(); 
     break; 
    } 

Dies sollte die Anzahl der Male minimieren die dict während der Erstellung der Größe verändert werden, aber da sie berücksichtigen nicht die Load-Faktor, es ist nicht ganz zu beseitigen Größenänderungen.

Wie die source code comments angeben, soll _PyDict_NewPresized "ein neues Wörterbuch erstellen, das so groß ist, dass es eine geschätzte Anzahl von Elementen enthält". Die genaue Größe der Hashtabelle in dem erstellten dict wird durch eine Anzahl von Implementierungsdetails beeinflusst, beispielsweise die minimale Größe (#define PyDict_MINSIZE 8) und die Anforderung, dass die Größe eine Potenz von 2 sein muss (um zu vermeiden, dass in der Implementierung eine Division erforderlich ist).

Für dict-Literale mit bis zu 7 Einträgen initialisiert _PyDict_NewPresized eine Hash-Tabelle mit 8 Einträgen; Bei 8 Einträgen initialisiert es eine Hash-Tabelle mit 16 Einträgen, da die von ihm verwendete Größenänderungsroutine immer eine Kapazität auswählt, die größer als das Argument ist.

---

Dicts resize on insertion when they become at least 2/3 full. Für die 6- und 7-Eintrag dict Literale, beginnt die dict mit 8 Einträgen aus, so dass ein Resize am 6. Insertion auftritt. Die dict ist klein genug, dass die Größe ändern, die Größe der Hash-Tabelle vervierfacht:

return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used); 

mp->ma_used die Anzahl der verwendeten Einträge in der Hash-Tabelle ist, 6 an dieser Stelle. 6 ist kleiner als 50000, also rufen wir dictresize(mp, 4 * 6) auf, die die Hash-Tabelle auf 32 Einträge ändert, wobei die kleinste Potenz von 2 größer als 24 ist.

Im Gegensatz dazu begann die Hash-Tabelle für das Diktat-Literal mit 8 Einträgen mit 16 Einträgen. Das Diktat wird während der Erstellung nicht zu 2/3 voll, so dass die anfängliche Hash-Tabelle mit 16 Einträgen die Diktat-Erstellung überlebt und das resultierende Diktat kleiner ist als bei den 6- und 7-Eintrag-Literalen.

---

Python 3 verwendet ein different growth policy unter anderem dict Implementierung Änderungen, weshalb Sie unterschiedliche Ergebnisse in Python sah 3.

Answer 2

Nun, ich habe ein bisschen ausprobiert und mal sehen:

dct = {'four': 3, 'three': 2, 'two': 1, 'one': 0} 
print(sys.getsizeof(dct))        # = 272 
print(sys.getsizeof(dict(dct)))      # = 272 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 272 

dct = {'four': 3, 'three': 2, 'five': 4, 'two': 1, 'one': 0} 
print(sys.getsizeof(dct))        # = 272 
print(sys.getsizeof(dict(dct)))      # = 272 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 272 

dct = {'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'one': 0} 
print(sys.getsizeof(dct))        # = 1040 
print(sys.getsizeof(dict(dct)))      # = 656 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

dct = {'seven': 6, 'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'one': 0} 
print(sys.getsizeof(dct))        # = 1040 
print(sys.getsizeof(dict(dct)))      # = 656 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

dct = {'seven': 6, 'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'eight': 7, 'one': 0} 
print(sys.getsizeof(dct))        # = 656 
print(sys.getsizeof(dict(dct)))      # = 1040 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

Ich bin nicht sicher, welche Art von Optimierung hier geschieht, aber ich nehme an, es ist, weil diese Strukturen anders verwenden „Best Practices“. Ich meine wann, wie viel Speicher für die Hash-Tabelle ,. Wenn Sie zum Beispiel elf oder mehr Elemente haben Sie eine andere seltsame Diskrepanz erhalten:

dct = {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10:10, 11:11} 
print(sys.getsizeof(dct))        # = 1808 
print(sys.getsizeof(dict(dct)))      # = 1040 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

das so ist wahrscheinlich nur eine Art von Speicherverbrauch „Optimierung“, wenn Wörterbücher auf unterschiedliche Weise zu schaffen, warum gibt es diesen nicht-monotonen Ausreißer für die wörtliche Syntax bei 6 oder 7 Elementen: Ich weiß es nicht. Vielleicht ist eine Speicheroptimierung schief gelaufen und es ist ein Bug, dem zu viel Speicher zugewiesen wurde? Ich habe den Quellcode (noch) nicht gelesen.