Ist die Verwendung von Zeigervariablen nicht ein Speicheraufwand?

In Sprachen wie C und C ++ benötigen wir unter Verwendung von Zeigern auf Variablen einen weiteren Speicherort, um diese Adresse zu speichern. Ist das nicht ein Gedächtnisaufwand? Wie wird das kompensiert? Werden Zeiger in zeitkritischen Anwendungen mit geringem Arbeitsspeicher verwendet?

Tatsächlich liegt der Overhead nicht wirklich in den zusätzlichen 4 oder 8 Bytes, die zum Speichern des Zeigers benötigt werden. In den meisten Fällen werden Zeiger für die dynamische Speicherzuweisung verwendet. Dies bedeutet, dass wir eine Funktion zum Zuweisen eines Speicherblocks aufrufen. Diese Funktion gibt einen Zeiger zurück, der auf diesen Speicherblock verweist. Dieser neue Block an und für sich bedeutet einen erheblichen Mehraufwand.

Jetzt müssen Sie sich nicht mehr mit der Speicherzuweisung befassen, um einen Zeiger zu verwenden: Sie können ein Array von intstatisch deklariert haben oder auf dem Stapel, und Sie können einen Zeiger anstelle eines Indexes verwenden, um das ints zu besuchen , und das ist es alles sehr schön und einfach und effizient. Keine Speicherzuweisung erforderlich, und der Zeiger belegt normalerweise genau so viel Speicherplatz wie ein Ganzzahlindex.

Auch, wie Joshua Taylor uns in einem Kommentar erinnert, werden Zeiger verwendet, um etwas als Referenz zu übergeben. ZB struct foo f; init_foo(&f);würde f auf dem Stapel zuweisen und dann init_foo()mit einem Zeiger darauf aufrufen struct. Das ist sehr verbreitet. (Achten Sie nur darauf, diese Zeiger nicht "nach oben" zu übergeben.) In C ++ wird dies möglicherweise mit einem "reference" ( foo&) anstelle eines Zeigers ausgeführt, aber Referenzen sind nichts anderes als Zeiger, die Sie möglicherweise nicht ändern, und sie belegen den gleiche Menge an Speicher.

Der Hauptgrund, warum Zeiger verwendet werden, ist die dynamische Speicherzuweisung. Dies geschieht, um Probleme zu lösen, die auf andere Weise nicht gelöst werden könnten. Hier ist ein vereinfachtes Beispiel: Stellen Sie sich vor, Sie möchten den gesamten Inhalt einer Datei lesen. Wo wirst du sie aufbewahren? Wenn Sie einen Puffer mit fester Größe verwenden, können Sie nur Dateien lesen, die nicht länger als dieser Puffer sind. Mithilfe der Speicherzuordnung können Sie jedoch so viel Speicher zuweisen, wie zum Lesen der Datei erforderlich ist, und dann mit dem Lesen fortfahren.

Außerdem ist C ++ eine objektorientierte Sprache, und es gibt bestimmte Aspekte von OOP wie die Abstraktion , die nur mit Zeigern erreichbar sind. Auch Sprachen wie Java und C # machen umfangreiche Verwendung von Zeigern, sie einfach nicht erlauben , direkt die Zeiger zu manipulieren, wie dies zu verhindern , dass Sie mit ihnen gefährliche Sachen zu tun, aber immer noch, beginnen diese Sprachen nur dann Sinn zu machen , wenn Sie merkte, dass hinter den Kulissen alles mit Zeigern gemacht wird.

Zeiger werden also nicht nur in zeitkritischen Anwendungen mit geringem Arbeitsspeicher verwendet, sondern überall .

Ist das nicht ein Gedächtnisaufwand?

Sicher, eine zusätzliche Adresse (in der Regel 4/8 Bytes je nach Prozessor).

Wie wird das kompensiert?

Es ist nicht. Wenn Sie die für Zeiger erforderliche Indirektion benötigen, müssen Sie dafür bezahlen.

Werden Zeiger in zeitkritischen Anwendungen mit geringem Arbeitsspeicher verwendet?

Ich habe dort nicht viel gearbeitet, aber ich würde es annehmen. Der Zeigerzugriff ist ein elementarer Aspekt der Assembly-Programmierung. Es sind nur geringe Mengen an Speicher erforderlich, und Zeigeroperationen sind schnell - selbst im Kontext dieser Art von Anwendungen.

Ich habe nicht ganz den gleichen Dreh wie Telastyn.

Systemglobale in einem eingebetteten Prozessor können mit bestimmten, fest codierten Adressen adressiert werden.

Globals in einem Programm werden als Versatz von einem speziellen Zeiger angesprochen, der auf die Stelle im Speicher verweist, an der Globals und Statics gespeichert sind.

Lokale Variablen erscheinen, wenn eine Funktion eingegeben wird, und werden als Versatz von einem anderen speziellen Zeiger angesprochen, der häufig als "Rahmenzeiger" bezeichnet wird. Dies schließt die Argumente für die Funktion ein. Wenn Sie mit dem Stapelzeiger vorsichtig umgehen, können Sie den Rahmenzeiger entfernen und direkt über den Stapelzeiger auf lokale Variablen zugreifen.

Sie zahlen also für die Indirektion von Zeigern, unabhängig davon, ob Sie durch ein Array gehen oder nur eine unauffällige lokale oder globale Variable abrufen. Es basiert nur auf einem anderen Zeiger, je nachdem, um welche Art von Variable es sich handelt. Gut kompilierter Code speichert diesen Zeiger in einem CPU-Register, anstatt ihn bei jeder Verwendung neu zu laden.

Ja natürlich. Aber es ist ein Spagat.

Anwendungen mit geringem Speicherbedarf werden typischerweise unter Berücksichtigung des Kompromisses zwischen dem Overhead einiger Zeigervariablen im Vergleich zum Overhead eines massiven Objekts konstruiert Programms (das im Arbeitsspeicher gespeichert werden muss, denken Sie daran!) Konstruiert, wenn Zeiger nicht verwendet werden könnten .

Diese Überlegung gilt für alle Programme, denn niemand möchte ein schreckliches, nicht zu wartendes Durcheinander mit doppeltem Code aufbauen, der zwanzigmal größer ist, als er sein muss.

In Sprachen wie C und C ++ benötigen wir unter Verwendung von Zeigern auf Variablen einen weiteren Speicherort, um diese Adresse zu speichern. Ist das nicht ein Gedächtnisaufwand?

Sie gehen davon aus, dass der Zeiger gespeichert werden muss. Das ist nicht immer der Fall. Jede Variable wird an einer Speicheradresse gespeichert. Angenommen, Sie haben als longdeklariert long n = 5L;. Dies reserviert Speicher für neine Adresse. Wir können diese Adresse verwenden, um ausgefallene Dinge zu tun *((char *) &n) = (char) 0xFF;, um Teile von zu manipulieren n. Die Adresse von nwird nirgendwo als zusätzlicher Aufwand gespeichert.

Wie wird das kompensiert?

Selbst wenn Zeiger explizit gespeichert werden (z. B. in Datenstrukturen wie Listen), ist die resultierende Datenstruktur oft eleganter (einfacher, verständlicher, einfacher zu handhaben usw.) als eine äquivalente Datenstruktur ohne Zeiger.

Werden Zeiger in zeitkritischen Anwendungen mit geringem Arbeitsspeicher verwendet?

Ja. Geräte, die Mikrocontroller verwenden, enthalten häufig sehr wenig Speicher, aber die Firmware verwendet möglicherweise Zeiger für die Verarbeitung von Interruptvektoren oder die Pufferverwaltung usw.

Einen Zeiger zu haben, kostet definitiv etwas Overhead, aber Sie können auch die Oberseite sehen. Der Zeiger ist wie ein Index. In C können Sie komplexe Datenstrukturen wie Zeichenfolgen und Strukturen nur aufgrund von Zeigern verwenden.

Angenommen, Sie möchten eine Variable als Referenz übergeben, dann ist es einfach, einen Zeiger zu verwalten, anstatt die gesamte Struktur zu replizieren und Änderungen zwischen ihnen zu synchronisieren (selbst zum Kopieren benötigen Sie einen Zeiger). Wie würden Sie mit nicht zusammenhängenden Speicherzuordnungen und Aufhebungen ohne Zeiger umgehen?

Sogar Ihre normalen Variablen haben einen Eintrag in der Symboltabelle, in dem die Adresse gespeichert ist, auf die Ihre Variable zeigt. Ich denke also nicht, dass es viel Overhead in Bezug auf den Speicher verursacht (nur 4 oder 8 Bytes). Sogar Sprachen wie Java verwenden Zeiger intern (Referenz), aber Sie können sie nicht manipulieren, da dies die Sicherheit von JVM beeinträchtigt.

Sie sollten Zeiger nur verwenden, wenn Sie keine andere Wahl haben als fehlende Datentypen. Strukturen (in c) wie die Verwendung von Zeigern können zu Fehlern führen, wenn sie nicht richtig gehandhabt werden und sind vergleichsweise schwerer zu debuggen.

Ist das nicht ein Gedächtnisaufwand?

Ja Nein Vielleicht?

Dies ist eine heikle Frage, da Sie sich den Adressierungsbereich des Speichers auf dem Computer und eine Software vorstellen müssen, die permanent den Speicherort auf eine Weise festhält, die nicht an den Stapel gebunden werden kann.

Stellen Sie sich beispielsweise einen Musik-Player vor, bei dem die Musikdatei auf Knopfdruck des Benutzers geladen und aus dem flüchtigen Speicher entfernt wird, wenn der Benutzer versucht, eine andere Musikdatei zu laden.

Wie verfolgen wir, wo die Audiodaten gespeichert sind? Wir brauchen eine Speicheradresse dazu. Das Programm muss nicht nur die Audiodaten im Speicher verfolgen, sondern auch, wo sie sich im Speicher befinden. Daher müssen wir eine Speicheradresse (dh einen Zeiger) behalten. Die Größe des für die Speicheradresse erforderlichen Speichers entspricht dem Adressierungsbereich des Geräts (Beispiel: 64-Bit-Zeiger für einen 64-Bit-Adressierungsbereich).

Es ist also eine Art "Ja", es erfordert Speicher, um eine Speicheradresse zu verfolgen, aber es ist nicht so, als könnten wir es für dynamisch zugewiesenen Speicher dieser Art vermeiden.

Wie wird das kompensiert?

Wenn Sie nur über die Größe eines Zeigers selbst sprechen, können Sie in einigen Fällen die Kosten vermeiden, indem Sie den Stapel verwenden. In diesem Fall können Compiler Anweisungen generieren, die die relative Speicheradresse effektiv fest codieren, wodurch die Kosten eines Zeigers vermieden werden. Dies macht Sie jedoch anfällig für Stapelüberläufe, wenn Sie dies für Zuweisungen mit großen variablen Größen tun, und es ist in der Regel unpraktisch (wenn nicht sogar unmöglich), dies für eine komplexe Reihe von Zweigen zu tun, die durch Benutzereingaben gesteuert werden (wie im Audiobeispiel) über).

Eine andere Möglichkeit besteht darin, zusammenhängendere Datenstrukturen zu verwenden. Beispielsweise kann eine Array-basierte Sequenz anstelle einer doppelt verknüpften Liste verwendet werden, für die zwei Zeiger pro Knoten erforderlich sind. Wir können auch eine Kreuzung dieser beiden Elemente wie eine nicht gerollte Liste verwenden, in der nur Zeiger zwischen jeder zusammenhängenden Gruppe von N Elementen gespeichert sind.

Werden Zeiger in zeitkritischen Anwendungen mit geringem Arbeitsspeicher verwendet?

Ja, sehr häufig, da viele leistungskritische Anwendungen in C oder C ++ geschrieben sind, die von der Zeigerverwendung dominiert werden (sie können sich hinter einem intelligenten Zeiger oder einem Container wie std::vectoroder befinden)std::string , aber die zugrunde liegende Mechanik läuft auf einen Zeiger hinaus, der verwendet wird um die Adresse in einem dynamischen Speicherblock zu verfolgen).

Nun zurück zu dieser Frage:

Wie wird das kompensiert? (Zweiter Teil)

Zeiger sind in der Regel spottbillig, es sei denn, Sie speichern wie eine Million von ihnen (was auf einem 64-Bit-Computer immer noch mickrig 8 Megabyte ist).

_{* Beachten Sie, wie Ben darauf hinwies, dass "dürftige" 8 Megabyte immer noch die Größe des L3-Caches haben. Hier habe ich "dürftig" mehr im Sinne der gesamten DRAM-Nutzung und der typischen relativen Größe zu den Speicherbausteinen verwendet, auf die eine gesunde Verwendung von Zeigern hinweisen wird.}

Wo Zeiger teuer werden, sind nicht Zeiger selbst, sondern:

1. Dynamische Speicherzuordnung. Dynamische Speicherzuweisung ist in der Regel teuer, da sie eine zugrunde liegende Datenstruktur durchlaufen muss (z. B. Buddy- oder Plattenzuweisung). Auch wenn diese häufig zu Tode optimiert sind, sind sie universell einsetzbar und für die Verarbeitung von Blöcken mit variabler Größe konzipiert, für die mindestens ein bisschen Arbeit erforderlich ist, die einer "Suche" ähnelt (wenn auch mit geringem Gewicht und möglicherweise sogar mit konstanter Zeit) Suchen Sie einen freien Satz zusammenhängender Seiten im Speicher.

2. Speicherzugriff. Dies ist in der Regel der größere Aufwand, über den Sie sich Sorgen machen müssen. Wann immer wir zum ersten Mal auf dynamisch zugewiesenen Speicher zugreifen, gibt es einen obligatorischen Seitenfehler sowie Cache-Fehler, die den Speicher in der Speicherhierarchie nach unten und in ein Register verschieben.

Speicherzugriff

Der Speicherzugriff ist einer der kritischsten Aspekte der Leistung jenseits von Algorithmen. Viele leistungskritische Bereiche wie AAA-Game-Engines konzentrieren einen Großteil ihrer Energie auf datenorientierte Optimierungen, die auf effizientere Speicherzugriffsmuster und -layouts hinauslaufen.

Eine der größten Leistungsschwierigkeiten von übergeordneten Sprachen, die jeden benutzerdefinierten Typ separat über einen Garbage Collector zuordnen möchten, besteht beispielsweise darin, dass sie den Speicher ziemlich stark fragmentieren können. Dies kann insbesondere dann der Fall sein, wenn nicht alle Objekte gleichzeitig zugeordnet sind.

Wenn Sie in diesen Fällen eine Liste mit einer Million Instanzen eines benutzerdefinierten Objekttyps speichern, kann der sequenzielle Zugriff auf diese Instanzen in einer Schleife sehr langsam sein, da er einer Liste mit einer Million Zeigern entspricht, die auf unterschiedliche Speicherbereiche verweisen. In diesen Fällen möchte die Architektur Speicher von oberen, langsameren und größeren Hierarchieebenen in großen, ausgerichteten Blöcken abrufen, in der Hoffnung, dass auf die umgebenden Daten in diesen Blöcken vor der Räumung zugegriffen werden kann. Wenn jedes Objekt in einer solchen Liste separat zugewiesen wird, wird es häufig mit Cache-Fehlern bezahlt, wenn jede nachfolgende Iteration möglicherweise aus einem völlig anderen Bereich im Speicher geladen werden muss, ohne dass auf benachbarte Objekte vor der Räumung zugegriffen wird.

Viele der Compiler für solche Sprachen leisten heutzutage sehr gute Arbeit bei der Auswahl von Befehlen und der Zuweisung von Registern, aber der Mangel an direkterer Kontrolle über die Speicherverwaltung kann tödlich sein (wenn auch oft weniger fehleranfällig) und dennoch Sprachen wie C und C ++ sehr beliebt.

Indirekte Optimierung des Zeigerzugriffs

In den leistungskritischsten Szenarien verwenden Anwendungen häufig Speicherpools, die Speicher aus zusammenhängenden Abschnitten bündeln, um die Referenzlokalität zu verbessern. In solchen Fällen kann sogar eine verknüpfte Struktur wie ein Baum oder eine verknüpfte Liste cachefreundlich gemacht werden, vorausgesetzt, das Speicherlayout ihrer Knoten ist zusammenhängender Natur. Dadurch wird die Dereferenzierung von Zeigern effektiv verbilligt, wenn auch indirekt, indem die Referenzlokalität verbessert wird, die bei der Dereferenzierung einbezogen wird.

Verfolgen von Zeigern

Angenommen, wir haben eine einfach verknüpfte Liste wie:

Foo->Bar->Baz->null

Das Problem ist, dass, wenn wir alle diese Knoten einem Allzweck-Allokator zuordnen (und möglicherweise nicht alle auf einmal), der tatsächliche Speicher möglicherweise in etwa so verteilt ist (vereinfachtes Diagramm):

Wenn wir anfangen, Zeiger zu verfolgen und auf den FooKnoten zuzugreifen , beginnen wir mit einem obligatorischen Fehler (und möglicherweise einem Seitenfehler), der einen Block aus seinem Speicherbereich von langsameren Speicherbereichen in schnellere Speicherbereiche verschiebt, wie folgt:

Dies bewirkt, dass wir einen Speicherbereich (möglicherweise auch eine Seite) zwischenspeichern, um nur auf einen Teil davon zuzugreifen und den Rest zu entfernen, während wir Zeiger um diese Liste herum verfolgen. Indem wir jedoch die Kontrolle über den Speicherzuweiser übernehmen, können wir eine solche Liste zusammenhängend wie folgt zuweisen:

... und damit die Geschwindigkeit, mit der wir diese Zeiger dereferenzieren und ihre Spitzenwerte verarbeiten können, erheblich verbessern. Obwohl sehr indirekt, können wir den Zeigerzugriff auf diese Weise beschleunigen. Wenn wir diese nur zusammenhängend in einem Array speichern würden, wäre dieses Problem natürlich nicht an erster Stelle zu sehen, aber der hier angegebene Speicherzuweiser, der uns die explizite Kontrolle über das Speicherlayout gibt, kann den Tag retten, an dem eine verknüpfte Struktur erforderlich ist.

_{* Hinweis: Dies ist ein sehr vereinfachtes Diagramm und eine Diskussion über die Speicherhierarchie und die Referenzlokalität, aber hoffentlich ist es für die Ebene der Frage angemessen.}

Ist das nicht ein Gedächtnisaufwand?

Es ist in der Tat ein Gedächtnisaufwand, aber ein sehr kleiner (bis zur Bedeutungslosigkeit).

Wie wird das kompensiert?

Es wird nicht entschädigt. Sie müssen erkennen, dass der Datenzugriff über einen Zeiger (dereferenzieren eines Zeigers) extrem schnell ist (wenn ich mich richtig erinnere, wird nur eine Assembly-Anweisung pro Dereferenzierung verwendet). Es ist schnell genug, um in vielen Fällen die schnellste Alternative zu sein.

Werden Zeiger in zeitkritischen Anwendungen mit geringem Arbeitsspeicher verwendet?

Ja.

Sie benötigen nur den zusätzlichen Speicherbedarf (normalerweise 4 bis 8 Byte pro Zeiger), während Sie diesen Zeiger benötigen. Es gibt viele Techniken, die dies erschwinglicher machen.

Die grundlegendste Technik, die Zeiger leistungsfähig macht, besteht darin, dass Sie nicht jeden Zeiger behalten müssen. Manchmal können Sie einen Algorithmus verwenden, um einen Zeiger von einem Zeiger auf etwas anderes zu konstruieren. Das trivialste Beispiel hierfür ist die Array-Arithmetik. Wenn Sie ein Array mit 50 Ganzzahlen zuweisen, müssen Sie nicht 50 Zeiger beibehalten, einen für jede Ganzzahl. Normalerweise verfolgen Sie einen Zeiger (den ersten) und verwenden Zeigerarithmetik, um die anderen im laufenden Betrieb zu generieren. Manchmal kann es vorkommen, dass Sie einen dieser Zeiger vorübergehend auf ein bestimmtes Element des Arrays verweisen, aber nur dann, wenn Sie ihn benötigen. Sobald Sie fertig sind, können Sie es verwerfen, sofern Sie genügend Informationen gespeichert haben, um es später bei Bedarf neu zu generieren. Das mag trivial klingen, aber es ist genau die Art von Konservierungswerkzeugen, die Sie verwenden.

In extrem engen Speichersituationen kann dies verwendet werden, um die Kosten zu minimieren. Wenn Sie in einem sehr engen Speicherbereich arbeiten, wissen Sie normalerweise genau, wie viele Objekte Sie bearbeiten müssen. Anstatt eine Reihe von ganzen Zahlen nacheinander zuzuweisen und vollständige Zeiger auf diese zu setzen, können Sie Ihr Entwicklerwissen nutzen, dass Sie in diesem bestimmten Algorithmus niemals mehr als 256 ganze Zahlen haben werden. In diesem Fall können Sie einen Zeiger auf die erste Ganzzahl beibehalten und einen Index mit einem Zeichen (1 Byte) verfolgen, anstatt einen vollständigen Zeiger (4/8 Byte) zu verwenden. Sie können auch algorithmische Tricks verwenden, um einige dieser Indizes im laufenden Betrieb zu generieren.

Diese Art von Erinnerungsbewusstsein war in der Vergangenheit sehr beliebt. Beispielsweise würden NES-Spiele in hohem Maße von ihrer Fähigkeit abhängen, Daten zu stopfen und Zeiger algorithmisch zu generieren, anstatt sie alle im Großhandel speichern zu müssen.

Extreme Speichersituationen können auch dazu führen, dass Sie beispielsweise alle Speicherbereiche zuweisen, die Sie zum Zeitpunkt der Kompilierung bearbeiten. Dann wird der Zeiger, den Sie in diesem Speicher speichern müssen, im Programm und nicht in den Daten gespeichert. In vielen Situationen mit eingeschränktem Speicher verfügen Sie über separate Programm- und Datenspeicher (häufig ROM oder RAM), sodass Sie möglicherweise die Art und Weise anpassen können, in der Sie mit Ihrem Algorithmus die Zeiger in diesen Programmspeicher verschieben.

Grundsätzlich kann man nicht den ganzen Overhead loswerden. Sie können es jedoch steuern. Mit algorithmischen Techniken können Sie die Anzahl der Zeiger, die Sie speichern können, minimieren. Wenn Sie Zeiger auf dynamischen Speicher verwenden, werden Sie niemals die Kosten für die Speicherung eines Zeigers auf diesen dynamischen Speicherbereich unterschreiten, da dies die minimale Menge an Informationen ist, die für den Zugriff auf irgendetwas in diesem Speicherblock erforderlich ist. In extrem engen Speicherbeschränkungsszenarien ist dies jedoch in der Regel der Sonderfall (dynamischer Speicher und extrem enge Speicherbeschränkungen treten in der Regel nicht in den gleichen Situationen auf).

In vielen Situationen sparen Zeiger tatsächlich Speicher. Eine häufige Alternative zur Verwendung von Zeigern besteht darin, eine Kopie einer Datenstruktur zu erstellen. Eine vollständige Kopie einer Datenstruktur ist größer als ein Zeiger.

Ein Beispiel für eine zeitkritische Anwendung ist ein Netzwerkstapel. Ein guter Netzwerkstapel wird so entworfen, dass er "Nullkopie" ist - und dies erfordert den geschickten Einsatz von Zeigern.