Maximale Anzahl der Element in einer Liste

[Timor B.]

Hallo,

ich würde gerne wissen wie viele Elemente ich in einer Liste haben kann. Ich bin Anfangs von -Theoretisch- Unendlich vielen ausgegangen.
Auch wenn die nahe liegende Vermutung int.MaxValue heißt, stimmt das nicht. Auch uint.MaxValue ist nicht Korrekt.
Ich habe mich entschlossen ein Programm zu machen um es heraus zu finden:
[highlight=c#]
List<int> IntList = new List<int>();

for (int i = 0; i < int.MaxValue; i++)
{
IntList.Add(i);
}[/highlight]
Hier bekomme ich nach 134.217.728 Durchläufen eine OutOfMemory Exception.
Das gleiche bei uint.MaxValue;

Aber die Exception kommt nicht immer bei 134.217.728 Einträgen. Sie scheint - und das ist unlogisch - variabel zu sein.
Wenn ich die Liste mit Objekten fülle ist schneller Schluss:
[highlight=c#]
List<List<int>> ObjList = new List<List<int>>();

for (int i = 0; i < int.MaxValue; i++)
{
List<int> IntList = new List<int>();
ObjList.Add(IntList);
}[/highlight]
Hier Knallts schon bei 33.554.432 Durchläufen.
Jetzt stellen sich mir 2 Fragen:

• Warum ist das ende des (Internen) Listen Index nicht bei int.MaxValue?
• Warum ist die Anzahl der Einträge abhängig, von dem was ich in die Liste gebe?

Leider habe ich keine Antwort im großen WWW finden können.
Weiß irgendjemand mehr?

Vielen Dank für's lesen,
Timor B.

[Christian Marquardt]

Sie scheint - und das ist unlogisch - variabel zu sein.

Warum unlogisch? Könnte es nicht sein, dass die Größe ist unbegrenzt ist und sich somit nach dem zur Verfügung stehenden Speicher richtet........

Sicherlich ist früher Schluß, wenn du die Liste mit Objekten füllst -> die benötigen mehr Speicher.

[Timor B.]

Ja das ist mir jetzt klar, dass Objekte mehr Speicher verbrauchen.
Aber warum liegt der Grenzwert bei ausgerechnet dieser Zahl? Ich habe 8GB RAM und es werden nur ~500 MB Speicher benutzt.
Das Programm ist 32 Bit. Ein Integer braucht 4 Byte Speicherplatz. Ich habe pro Prozess 2^32 bit Speicherplatz also 4294967296 Bit (= 4 GB)
Ich könnte also insgesamt 1GB mit meinen Integern Verbraten. Warum kommt die Exception schon bei 500 MB?
Auch habe ich getestet ob ich bei viel belegtem RAM die Eception früher bekomme: Fehlanzeige.

[Christian Marquardt]

Wahrscheinlich liegt nicht soviel zusammenhängender Speicher vor....und da du die Liste nicht mit einer Größe konstruierst muss wohl auch bei jedem neuen Element kopiert werden...aber theoretische Programmierung ist nicht so mein Ding

[gfoidl]

Hallo,

in .net kann ein einzelnes Objekt maximal 2GB groß sein, dieser Wert ist fest kodiert in der CLR.
Für die OutOfMemoryException siehe .NET Memory usage - A restaurant analogy

mfG Gü

[Ralf Jansen]

Bei OutOfMemoryException geht es üblicherweise nie darum das einem der phyikalische Speicher ausgeht sondern fast immer das der adressierbare Speicher, insbesondere bei 32bit Anwendungen, nicht mehr das nötige hergibt. In deinem 32bittigen Adressraum (denn du auch nicht zur Gänze ausnutzen kann) geht es halt eng zu wenn du Objekt anlegst die in einer ähnlichen Größenordnung liegen wie der zur Verfügung stehende Adressraum.

In deinem konkreten Testfall mit der stetig anwachsenden Liste hast du dir im Prinzip selbst ein Bein gestellt. Beim Add wird ein intern verwaltet Array befüllt das irgendeine Größe hat(AFAIK ist der Startgröße 4) . Bei erreichen seiner max.Größe wird es in der Größe verdoppelt und der Inhalt kopiert. Während dem kopieren hast du also beide Listen im Speicher und die müssen logischerweise damit auch an verschieden Speicheradressen liegen. Du legst also ständig neue Arrays an die sich über deinen Adressraum verteilen.
Da der Garbage Kollektor die alte Arrays auch nicht sofort wegwirft sondern erst wenn er bei einem Kollektorlauf der Meinung ist das die Kosten des Aufräumens kleiner sind als die möglichen Probleme durch den Speicherverbrauch fragmentiert dein Speicher und zu irgendeinem, beliebig aussehenden, Zeitpunkt steht einfach keine genügend großer zusammenhängender Adressbereich mehr zur Verfügung um eine Speicheranforderung zu erfüllen. Wie Christian schon andeutete wenn du weist das du eine große Liste brauchst dann initialisieren die Liste auch schon in einer passenden Größe(gibts nen passenden Konstruktor für) um die Speicherfragmentierung zu verhindern und den Garbage Collector zu entlasten. Wäre natürlich auch hilfreich einfach eine 64bit Anwendung draus zu machen. Auch wenn du nie mehr als 4GB brauchst bei der 64bit Adressraumgröße ist bei aktuellen Anwendungen nicht mehr mit Fragmentierungsproblemen zu rechnen.

[gfoidl]

Hallo,

bei der 64bit Adressraumgröße ist bei aktuellen Anwendungen nicht mehr mit Fragmentierungsproblemen zu rechnen.

dennoch kann in .net ein einzelnes Objekt nicht größer als 2GB werden. Hier gilt es dann, das große Objekt in mehrer Objekte aufzuteilen. In Summe können die Objekte natürlich größer als 2GB werden.

den Speicherverbrauch fragmentiert

hinzu kommt, dass dies nur für "small object heap" (SOH) gilt. Beim Large object heap (LOH), indem Objekte größer als 85e3 Bytes gelegt werden, findet afaik keine Defragmentierung statt und eine Garbage Collection viel seltener als beim SOH. Dies ist eine häufige Ursache für die OutOfMemoryException.

mfG Gü

[fanderlf]

An dieser Stelle wäre evtl. auch interessant warum man so etwas überhaupt wissen muss, ausser zum reinen Selbstzweck. Gerade bei solchen Geschichten helfen Caches enorm. Diese haben auch automatisch eine Logik eingebaut welche Objekte wieder freigibt wenn eine gewisse Größe überschritten wird. Ich halte es für wenig sinnvoll so große Objekte im Speicher zu halten. Wenn Du extreme Kontrolle über Deinen Speicherverbrauch brauchst, dann bist Du mit .Net und C# wahrscheinlich sowieso in der falschen Welt unterwegs.

[gfoidl]

Hallo Florian,

wie ein Cache hier helfen soll, weiß ich nicht, aber das ist (mir) auch egal. Ob es sinnvoll ist, so große Objekte im Speicher zu haben od. nicht, hängt vom Anwendungsfall ab. Im Bereich der Numerik, Bildverarbeitung, etc. ist es nicht unüblich - um nicht zu sagen: normal - so große Objekte zu haben und da hilft ein Cache gar nichts.

Auch hat das mit einer extremen Kontrolle des Speicherverbrauchs nichts zu tun, weder ist .net dafür eine falsche Plattform. Es ist jedoch richtig, dass in .net durch den Garbage Collector (GC) die Speicherverwaltung sehr erleichtert wird. Ich halte es jedenfalls für gut zu wissen wie der GC arbeitet und auch wo seine Grenzen sind, damit dies in der Programmierung berücksichtigt werden kann.
Alleine die Tatsache, dass viele bei einer OutOfMemoryException an ausgehenden RAM denken, verdeutlicht dies, obwohl die Ursache ein ganz andere ist.

mfG Gü

[Ralf Jansen]

dass viele bei einer OutOfMemoryException an ausgehenden RAM denken, verdeutlicht dies, obwohl die Ursache ein ganz andere ist.

Das Leute das glauben hat vermutlich was mit dem Namen der Exception zu tun Es wäre so einfach wenn das Ding z.B CanNotAllocateMemoryException hieße. Das weist einerseits auf das Problem hin gibt aber keinen Hinweis auf die Ursache. Leider steckt aber im Namen OutOfMemoryExceptionscheinbar schon der Grund (OutOfMemory) und nicht einfach nur das Symptom.

[gfoidl]

Hallo Ralf,

stimmt - vermutlich wurde die Bezeichnung unter dem Ballmer-Peak gewählt.

mfG Gü

[fanderlf]

@Günther: Na in der Regel bestehen so große Objekte ja aus kleineren Stücken. Jetzt kann ich doch zum Beispiel einen Cache verwenden in den ich eine bestimmte Datenmenge laden kann. Dem Cache gebe ich noch eine gewisse Größe - hat der Cache nun zu viele Daten wenn ich neue hinzufüge, dann wirft er die ersten wieder raus... das wäre dann wohl eigentlich eher sowas wie ein Stream Ich denke Du weisst was ich meine. Vielleicht etwas unglücklich ausgedrückt.

[gfoidl]

Hallo Florian,

ich weiß schon was du meinst. Aber beim Beispiel der Bildbearbeitung hilft der Cache nichts, da eben ein Image-Objekt groß ist. In der Numerik kann die Objekt-Größe schon durch die Änderung von double[,] zu double[][] umgangen werden (jagged Arrays sind generell sinnvoller, da sie besser von der CLR unterstützt werden).

Lassen wir das Thema um den Cache somit ruhen...

mfG Gü

[Ralf Jansen]

das wäre dann wohl eigentlich eher sowas wie ein Stream

Das ist das übliche. Wenn man sich aber schon in solchen programmiertechnischen Grenzgebieten bewegt sollte man auch die Grenze zwischen den beiden Heaps kennen. Wenn man einen solchen Stream implementiert sollte man in den meisten Fällen schön drauf achten das die Buffergröße kleiner als die von Gü erwähnten 85KB gewählt wird.

[Timor B.]

Die Sache mit der Code-Fragmentierung war keine schlechte Idee. Aber enthält die Liste nicht einfach nur Pointer, welche nur 4 byte groß sind? Den die Liste weiß ja nicht was man in sie hinein gibt. Das ist ja das tolle an der Liste.
Dann ist es evtl eine "Doubly linked list". Also noch je 2 pointer mehr. Jetzt bin ich bei 12 byte pro Index. Dann noch 4 byte für den integer und ich bin bei 16 byte. Wenn wir also die maximale Größe eines .Net-Objekts nehmen (2GB) und durch 16 Teilen bekomme ich 134217728 heraus. Genau die Zahl bei der es Knallt. Oder was Ralf Jansen sagt: 2 interne Arrays.

Aber! es ist noch nicht vorbei: Ich habe herausgefunden, dass wenn man in den Constructor eine größere Zahl als 134.217.728 eingibt, zb 240 Mio, kommt die Liste damit klar.
Somit ist das oben erwähnte doch nicht richtig.
Und auch hier ist etwas was mich wieder wundert: Setzte ich die Zahl 280 Mio in den Constructor wirft dieser mir bei seinem Aufruf eine OutOfMemory Exception entgegen. Warum?
In den Constructor setzt man ja nur die Kapazität die sie anfänglich haben soll. Sie lässt sich trotzdem erweitern. Zumindest sollte das so sein und was in Bereichen unter ca 80 Mio auch klappt.

Und hier noch eine Sache, welche mir beim Debuggen des Rätsels aufgefallen ist:

[highlight=c#]
int count = 80000000;//134217728
GC.Collect();
List<int> IntList = new List<int>(count);
for (int i = 0; i < 100000000; i++)
{
IntList.Add(i);
}
Console.WriteLine("Fertig");
Console.ReadKey();
[/highlight]
Hier läuft das Programm ohne zu zicken. Wenn ich aber den Integer auf 90000000 setze, erscheint wieder die OutOfMemory Exception. Warum? Ich habe eine Liste die sich - mit dem Programmcode bewiesen - mit 100 Mio Integern füllen lässt. Wenn ich aber die Kapazität, welche ich in den Constructor gebe, um 10 Mio erhöhe kommt eine Exception. Bei gleicher Anzahl an Integer die ich hinein geben will. Warum funktioniert es bei dem einen aber nicht bei dem anderen?
Dafür muss es eine Antwort geben. Ich will nicht raten, ich will nicht schätzen, ich will nicht vermuten. Ich will es wissen!

Um besser Debuggen zu könnnen bräuchte ich eine Funktion, welche mir hilft die genaue Größe an Bytes oder Bits eines Objekt zu bekommen. Weiß da jemand was?