Warum können Arrays nicht zugeschnitten werden?

Auf der MSDN-Dokumentationssite wird Folgendes zur Array.ResizeMethode angegeben:

Wenn newSize größer als die Länge des alten Arrays ist, wird ein neues Array zugewiesen und alle Elemente werden vom alten Array in das neue kopiert.

Wenn newSize kleiner als die Länge des alten Arrays ist, wird ein neues Array zugewiesen und Elemente werden vom alten Array in das neue kopiert, bis das neue gefüllt ist. Die restlichen Elemente im alten Array werden ignoriert.

Ein Array ist eine Folge benachbarter Speicherblöcke. Wenn wir ein größeres Array benötigen, können wir meines Wissens keinen Speicher hinzufügen, da der Speicher daneben möglicherweise bereits von anderen Daten beansprucht wird. Wir müssen also eine neue Folge benachbarter Speicherblöcke mit der gewünschten größeren Größe beanspruchen, unsere Einträge dort kopieren und unseren Anspruch auf den alten Speicherplatz entfernen.

Aber warum ein neues Array mit kleinerer Größe erstellen? Warum kann das Array nicht einfach seinen Anspruch auf die letzten Speicherblöcke entfernen? Dann wäre es eine O (1) -Operation anstelle von O (n), wie es jetzt ist.

Hat dies etwas damit zu tun, wie die Daten auf Computerarchitektur- oder physischer Ebene organisiert sind?

Um Ihre Frage zu beantworten, hat dies mit dem Design des Speicherverwaltungssystems zu tun.

Wenn Sie Ihr eigenes Speichersystem schreiben, können Sie es theoretisch so gestalten, dass es sich genau so verhält, wie Sie es gesagt haben.

Die Frage wird dann, warum es nicht so entworfen wurde. Die Antwort ist, dass das Speicherverwaltungssystem einen Kompromiss zwischen effizienter Speichernutzung und Leistung eingegangen ist.

Beispielsweise verwalten die meisten Speicherverwaltungssysteme den Speicher nicht bis auf das Byte. Stattdessen teilen sie den Speicher in 8-KB-Blöcke auf. Dafür gibt es eine Reihe von Gründen, von denen sich die meisten auf die Leistung beziehen.

Einige der Gründe haben damit zu tun, wie gut der Prozessor den Speicher bewegt. Nehmen wir zum Beispiel an, der Prozessor konnte 8 KB Daten gleichzeitig viel besser kopieren als 4 KB. Das Speichern der Daten in 8-KB-Blöcken bietet dann einen Leistungsvorteil. Das wäre ein Design-Kompromiss, der auf der CPU-Architektur basiert.

Es gibt auch algorithmische Leistungskompromisse. Wenn Sie beispielsweise das Verhalten der meisten Anwendungen untersuchen, stellen Sie fest, dass Anwendungen in 99% der Fälle Datenblöcke mit einer Größe von 6 KB bis 8 KB zuweisen.

Wenn das Speichersystem es Ihnen erlauben würde, 4 KB zuzuweisen und freizugeben, würde ein freier 4 KB-Block übrig bleiben, den 99% der Zuweisungen nicht verwenden können. Wenn nicht zu viel 8 KB zugewiesen würden, obwohl nur 4 KB benötigt würden, wäre es viel wiederverwendbarer.

Betrachten Sie noch ein anderes Design. Angenommen, Sie hatten eine Liste mit freien Speicherplätzen, die beliebig groß sein können, und es wurde eine Anforderung zum Zuweisen von 2 KB Speicher gestellt. Ein Ansatz wäre, Ihre Liste des freien Speichers zu durchsuchen und einen zu finden, der mindestens 2 KB groß ist. Sehen Sie sich jedoch die gesamte Liste an, um den kleinsten Block zu finden, oder finden Sie den ersten, der groß genug ist und verwendet wird Das.

Der erste Ansatz ist effizienter, aber langsamer, der zweite Ansatz ist weniger effizient, aber schneller.

Noch interessanter wird es in Sprachen wie C # und Java, die "verwalteten Speicher" haben. In einem verwalteten Speichersystem wird der Speicher nicht einmal freigegeben. es hört einfach auf, sich daran zu gewöhnen, was der Müllsammler später, in einigen Fällen viel später, erkennt und befreit.

Weitere Informationen zur Speicherverwaltung und -zuordnung finden Sie in diesem Artikel auf Wikipedia:

https://en.wikipedia.org/wiki/Memory_management

Nicht verwendeter Speicher wird nicht tatsächlich nicht verwendet. Es ist die Aufgabe jeder Heap-Implementierung, die Löcher im Heap zu verfolgen. Der Manager muss mindestens die Größe des Lochs kennen und den Standort verfolgen. Das kostet immer mindestens 8 Bytes.

In .NET spielt System.Object eine Schlüsselrolle. Jeder weiß, was es tut, was nicht so offensichtlich ist, dass es weiterlebt, nachdem ein Objekt gesammelt wurde. Die zwei zusätzlichen Felder im Objektheader (Syncblock und Typhandle) werden dann zu einem Rückwärts- und Vorwärtszeiger auf den vorherigen / nächsten freien Block. Es hat auch eine Mindestgröße von 12 Bytes im 32-Bit-Modus. Garantiert, dass immer genügend Speicherplatz vorhanden ist, um die freie Blockgröße nach dem Sammeln des Objekts zu speichern.

Sie sehen das Problem jetzt wahrscheinlich. Die Reduzierung der Größe eines Arrays garantiert nicht, dass ein Loch erstellt wird, das groß genug ist, um in diese drei Felder zu passen. Nichts, was es tun könnte, als eine Ausnahme "kann das nicht" auszulösen. Kommt auch auf die Bitness des Prozesses an. Völlig zu hässlich, um darüber nachzudenken.

Ich habe nach einer Antwort auf Ihre Frage gesucht, da ich sie als sehr interessante Frage empfand. Ich habe diese Antwort gefunden , die eine interessante erste Zeile hat:

Sie können einen Teil eines Arrays nicht freigeben - Sie können nur free()einen Zeiger freigeben, von dem Sie ihn erhalten haben, malloc()und wenn Sie dies tun, geben Sie die gesamte von Ihnen angeforderte Zuordnung frei.

Das eigentliche Problem ist also das Register, das festhält, welcher Speicher zugewiesen ist. Sie können nicht einfach einen Teil des Blocks freigeben, den Sie zugewiesen haben, Sie müssen ihn vollständig freigeben oder Sie geben ihn überhaupt nicht frei. Das heißt, um diesen Speicher freizugeben, müssen Sie zuerst die Daten verschieben. Ich weiß nicht, ob die .NET-Speicherverwaltung diesbezüglich etwas Besonderes tut, aber ich denke, diese Regel gilt auch für die CLR.

Ich denke, das liegt daran, dass das alte Array nicht zerstört wird. Es ist immer noch da, wenn auf etwas anderes verwiesen wird und immer noch darauf zugegriffen werden kann. Aus diesem Grund wird das neue Array an einem neuen Speicherort erstellt.

Beispiel:

int[] original = new int[] { 1, 2, 3, 4, 5, 6 };
int[] otherReference = original; // currently points to the same object

Array.Resize(ref original, 3);

Console.WriteLine("---- OTHER REFERENCE-----");

for (int i = 0; i < otherReference.Length; i++)
{
    Console.WriteLine(i);
}

Console.WriteLine("---- ORIGINAL -----");

for (int i = 0; i < original.Length; i++)
{
    Console.WriteLine(i);
}

Drucke:

---- OTHER REFERENCE-----
0
1
2
3
4
5
---- ORIGINAL -----
0
1
2

Es gibt zwei Gründe für die Definition von Realloc wie es ist: Erstens wird absolut klar, dass es keine Garantie dafür gibt, dass der Aufruf von Realloc mit einer kleineren Größe denselben Zeiger zurückgibt. Wenn Ihr Programm diese Annahme macht, ist Ihr Programm fehlerhaft. Auch wenn der Zeiger in 99,99% der Fälle gleich ist. Wenn sich mitten in viel leerem Raum ein großer Block befindet, der zu einer Fragmentierung des Heapspeichers führt, kann realloc ihn nach Möglichkeit aus dem Weg räumen.

Zweitens gibt es Implementierungen, bei denen dies unbedingt erforderlich ist. Zum Beispiel hat MacOS X eine Implementierung, bei der ein großer Speicherblock verwendet wird, um Malloc-Blöcke von 1 bis 16 Bytes zuzuweisen, ein anderer großer Speicherblock für Malloc-Blöcke von 17 bis 32 Bytes, einer für Malloc-Blöcke von 33 bis 48 Bytes usw. Dies macht es sehr natürlich, dass jede Größenänderung, die im Bereich von 33 bis 48 Bytes bleibt, denselben Block zurückgibt, aber das Ändern auf 32 oder 49 Bytes muss den Block neu zuweisen.

Es gibt keine Garantie für die Leistung von Realloc. In der Praxis wird die Größe jedoch nicht ein bisschen kleiner. Die Hauptfälle sind: Ordnen Sie Speicher einer geschätzten Obergrenze der erforderlichen Größe zu, füllen Sie ihn aus und ändern Sie die Größe auf die tatsächlich viel kleinere erforderliche Größe. Oder weisen Sie Speicher zu und ändern Sie die Größe auf etwas sehr Kleines, wenn es nicht mehr benötigt wird.

Nur die Designer der .NET-Laufzeit können Ihnen ihre tatsächlichen Gründe mitteilen. Ich vermute jedoch, dass die Speichersicherheit in .NET von größter Bedeutung ist und es sehr teuer wäre, sowohl die Speichersicherheit als auch die veränderlichen Array-Längen aufrechtzuerhalten, ganz zu schweigen davon, wie kompliziert Code mit Arrays wäre.

Betrachten Sie den einfachen Fall:

var fun = 0;
for (var i = 0; i < array.Length; i++)
{
  fun ^= array[i];
}

Um die Speichersicherheit zu gewährleisten, arraymuss jeder Zugriff auf Grenzen überprüft werden, während sichergestellt werden muss, dass die Grenzen nicht von anderen Threads überprüft werden (die .NET-Laufzeit hat viel strengere Garantien als beispielsweise der C-Compiler).

Sie benötigen also eine thread-sichere Operation, die Daten aus dem Array liest und gleichzeitig die Grenzen überprüft. Es gibt keine solche Anweisung auf der CPU, daher ist Ihre einzige Option ein Synchronisationsprimitiv. Ihr Code wird zu:

var fun = 0;
for (var i = 0; i < array.Length; i++)
{
  lock (array)
  {
    if (i >= array.Length) throw new IndexOutOfBoundsException(...);

    fun ^= array[i];
  }
}

Das ist natürlich schrecklich teuer. Wenn Sie die Array-Länge unveränderlich machen, erhalten Sie zwei massive Leistungssteigerungen:

• Da sich die Länge nicht ändern kann, muss die Begrenzungsprüfung nicht synchronisiert werden. Dies macht jede einzelne Grenzüberprüfung erheblich billiger.
• ... und Sie können die Grenzen weglassen, um zu überprüfen, ob Sie die Sicherheit dafür nachweisen können.

In Wirklichkeit ist das, was die Laufzeit tatsächlich tut, eher so:

var fun = 0;
var len = array.Length; // Provably safe

for (var i = 0; i < len; i++)
{
  // Provably safe, no bounds checking needed
  fun ^= array[i];
}

Am Ende haben Sie eine enge Schleife, die sich nicht von der in C unterscheidet - aber gleichzeitig ist sie absolut sicher.

Lassen Sie uns nun die Vor- und Nachteile des Hinzufügens eines Arrays so sehen, wie Sie es möchten:

Vorteile:

• In dem sehr seltenen Szenario, in dem Sie ein Array verkleinern möchten, bedeutet dies, dass das Array nicht kopiert werden muss, um seine Länge zu ändern. Es würde jedoch auch in Zukunft eine Heap-Komprimierung erfordern, die viel Kopieren erfordert.
• Wenn Sie Objektreferenzen im Array speichern, können Sie einige Vorteile aus der Cache-Lokalität ziehen, wenn die Zuordnung des Arrays und der Elemente zufällig zusammengeführt wird. Dies ist natürlich noch seltener als Pro # 1.

Nachteile:

• Jeder Array-Zugriff würde selbst in engen Schleifen schrecklich teuer werden. Also würde jeder unsafestattdessen Code verwenden, und da geht Ihre Speichersicherheit.
• Jeder einzelne Code, der sich mit Arrays befasst, muss damit rechnen, dass sich die Länge des Arrays jederzeit ändern kann. Jeder einzelne Array-Zugriff würde ein benötigen try ... catch (IndexOutOfRangeException), und jeder, der über ein Array iteriert, müsste in der Lage sein, mit der sich ändernden Größe umzugehen - jemals gefragt, warum Sie keine Elemente hinzufügen oder entfernen könnenList<T> Sie iterieren?
• Eine enorme Menge an Arbeit für das CLR-Team, die nicht für eine andere, wichtigere Funktion verwendet werden konnte.

Es gibt einige Implementierungsdetails, die dies noch weniger vorteilhaft machen. Am wichtigsten ist, dass .NET-Heap nichts mit malloc/ freepattern zu tun hat . Wenn wir den LOH ausschließen, verhält sich der aktuelle MS.NET-Heap ganz anders:

• Zuordnungen erfolgen immer von oben, wie in einem Stapel. Dies macht die Zuweisung im Gegensatz dazu fast so billig wie die Stapelzuweisung malloc.
• Aufgrund der Zuordnungsmuster, um tatsächlich „frei“ Speicher, müssen Sie verdichten die Haufen nach tut eine Sammlung. Dadurch werden Objekte so verschoben, dass die freien Speicherplätze im Heap gefüllt werden. Dadurch wird die "Oberseite" des Heaps niedriger, sodass Sie mehr Objekte im Heap zuweisen oder einfach den Speicher für die Verwendung durch andere Anwendungen auf dem System freigeben können .
• Um die Cache-Lokalität beizubehalten (unter der Annahme, dass Objekte, die üblicherweise zusammen verwendet werden, auch nahe beieinander zugewiesen werden, was eine gute Annahme ist), muss möglicherweise jedes einzelne Objekt im Heap über dem freigegebenen Speicherplatz nach unten verschoben werden. Sie haben sich vielleicht eine Kopie eines 100-Byte-Arrays gespeichert, müssen dann aber trotzdem 100 MiB anderer Objekte verschieben.

Darüber hinaus bedeutet, wie Hans in seiner Antwort sehr gut erklärte, nur weil das Array kleiner ist, nicht unbedingt, dass aufgrund der Objektheader genügend Platz für ein kleineres Array in der gleichen Speichermenge vorhanden ist (denken Sie daran, wie .NET dafür ausgelegt ist Speichersicherheit? Die Kenntnis des richtigen Objekttyps ist ein Muss für die Laufzeit. Er weist jedoch nicht darauf hin, dass Sie das Array auch dann verschieben müssen, wenn Sie über genügend Speicher verfügen . Betrachten Sie ein einfaches Array:

ObjectHeader,1,2,3,4,5

Jetzt entfernen wir die letzten beiden Elemente:

OldObjectHeader;NewObjectHeader,1,2,3

Hoppla. Wir benötigen den alten Objektheader, um die Freiraumliste beizubehalten, da wir den Heap sonst nicht richtig komprimieren könnten. Nun könnte es möglich sein, den alten Objektheader über das Array hinaus zu verschieben, um die Kopie zu vermeiden, aber das ist noch eine weitere Komplikation. Dies stellt sich als ziemlich teures Feature für etwas heraus, das noöne jemals wirklich verwenden wird.

Und das ist alles noch in der verwalteten Welt. Mit .NET können Sie jedoch bei Bedarf auf unsicheren Code zurückgreifen - beispielsweise bei der Interaktion mit nicht verwaltetem Code. Wenn Sie Daten an eine native Anwendung übergeben möchten, haben Sie zwei Möglichkeiten: Sie können entweder das verwaltete Handle anheften, um zu verhindern, dass es erfasst und verschoben wird, oder Sie kopieren die Daten. Wenn Sie einen kurzen, synchronen Anruf tätigen, ist das Fixieren sehr billig (obwohl gefährlicher - der native Code hat keine Sicherheitsgarantien). Das Gleiche gilt beispielsweise für die Bearbeitung von Daten in einer engen Schleife wie bei der Bildverarbeitung - das Kopieren der Daten ist eindeutig keine Option. Wenn Sie Array.Resizedas vorhandene Array ändern dürfen , wird dies vollständig unterbrochenArray.Resize Sie müssen überprüfen, ob dem Array, dessen Größe Sie ändern möchten, ein Handle zugeordnet ist, und in diesem Fall eine Ausnahme auslösen.

Weitere Komplikationen, über die man viel schwerer nachdenken kann (Sie werden jede Menge Spaß daran haben, den Fehler zu verfolgen, der nur gelegentlich auftritt, wenn der Array.ResizeVersuch, die Größe eines Arrays zu ändern, das gerade passiert, festgesteckt wird Erinnerung).

Wie andere erklärt haben, ist nativer Code nicht viel besser. Sie müssen zwar nicht dieselben Sicherheitsgarantien einhalten (was ich nicht wirklich als Vorteil nutzen würde, aber na ja), aber es gibt immer noch Komplikationen in Bezug auf die Art und Weise, wie Sie Speicher zuweisen und verwalten. Wird aufgerufen realloc, um ein Array mit 10 Elementen und 5 Elementen zu erstellen? Nun, es wird entweder kopiert oder es wird immer noch die Größe eines Arrays mit 10 Elementen haben, da es keine Möglichkeit gibt, den verbleibenden Speicher auf vernünftige Weise zurückzugewinnen.

Um es kurz zusammenzufassen: Sie fragen nach einer sehr teuren Funktion, die in einem äußerst seltenen Szenario nur von sehr begrenztem Nutzen ist (falls vorhanden) und für die es eine einfache Problemumgehung gibt (Erstellen einer eigenen Array-Klasse). . Ich sehe nicht, dass die Messlatte für "Sicher, lassen Sie uns diese Funktion implementieren!" :) :)

In jedem Heap-Management-System gibt es möglicherweise viele ausgefeilte Datenstrukturen, die "unter der Haube" arbeiten. Sie können beispielsweise Blöcke entsprechend ihrer aktuellen Größe speichern. Es würde eine Menge Komplikationen hinzufügen, wenn Blöcke "geteilt, wachsen und schrumpfen" könnten. (Und es würde die Dinge wirklich nicht schneller machen.)

Daher ist die Implementierung immer sicher : Sie weist einen neuen Block zu und verschiebt die Werte nach Bedarf. Es ist bekannt, dass "diese Strategie auf jedem System immer zuverlässig funktioniert". Und es wird die Dinge wirklich überhaupt nicht verlangsamen.

Unter der Haube werden Arrays in einem kontinuierlichen Speicherblock gespeichert, sind jedoch in vielen Sprachen immer noch ein primitiver Typ.

Um Ihre Frage zu beantworten, wird der einem Array zugewiesene Speicherplatz als ein einzelner Block betrachtet und stackbei lokalen Variablen oder bss/data segmentsbei globalen Variablen gespeichert . AFAIK: Wenn Sie auf ein Array wie array[3]auf niedriger Ebene zugreifen , erhalten Sie vom OS einen Zeiger auf das erste Element und springen / überspringen, bis es (im obigen Beispiel dreimal) den erforderlichen Block erreicht. Es kann also eine architektonische Entscheidung sein, dass eine Arraygröße nach ihrer Deklaration nicht mehr geändert werden kann.

In ähnlicher Weise kann das Betriebssystem nicht wissen, ob es ein gültiger Index eines Arrays ist, bevor es auf den erforderlichen Index zugreift. Wenn es versucht, auf den angeforderten Index zuzugreifen, indem es nach dem jumpingProzess den Speicherblock erreicht, und feststellt, dass der erreichte Speicherblock nicht Teil des Arrays ist, wird ein ausgelöstException