wake-up-neo.com

Effizienz: Arrays vs. Zeiger

Der Speicherzugriff über Zeiger sei effizienter als der Speicherzugriff über ein Array. Ich lerne C und das oben Gesagte ist in K & R angegeben. Konkret sagen sie

Jede durch Array-Subskription erreichbare Operation kann auch mit Zeigern ausgeführt werden. Die Zeigerversion wird im Allgemeinen schneller sein

Ich habe den folgenden Code mit Visual C++ zerlegt (Mein Prozessor ist ein 686-Prozessor. Ich habe alle Optimierungen deaktiviert.)

int a[10], *p = a, temp;

void foo()
{
    temp = a[0];
    temp = *p;
}

Zu meiner Überraschung sehe ich, dass der Speicherzugriff über einen Zeiger 3 Anweisungen zu den beiden benötigt, die vom Speicherzugriff über ein Array erhalten werden. Unten ist der entsprechende Code.

; 5    : temp = a[0];

    mov eax, DWORD PTR _a
    mov DWORD PTR _temp, eax

; 6    : temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx

Bitte hilf mir zu verstehen. Was fehlt mir hier?


Wie aus vielen Antworten und Kommentaren hervorgeht, hatte ich eine Compile-Zeitkonstante als Array-Index verwendet, wodurch der Zugriff durch ein Array wahrscheinlich einfacher wurde. Unten ist der Assembly-Code mit einer Variablen als Index. Ich habe jetzt die gleiche Anzahl von Anweisungen für den Zugriff über Zeiger und Arrays. Meine weitergehenden Fragen sind immer noch gut. Der Speicherzugriff über einen Zeiger lohnt sich nicht als effizienter.

; 7    :        temp = a[i];

    mov eax, DWORD PTR _i
    mov ecx, DWORD PTR _a[eax*4]
    mov DWORD PTR _temp, ecx

; 8    : 
; 9    :    
; 10   :        temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx
55
Abhijith Madhav

Der Speicherzugriff über Zeiger soll effizienter sein als der Speicherzugriff über ein Array.

Das mag in der Vergangenheit der Fall gewesen sein, als Compiler relativ dumme Biester waren. Sie müssen nur einen Teil des von gcc ausgegebenen Codes in Hochoptimierungsmodi betrachten, um zu wissen, dass dies nicht mehr der Fall ist. Ein Teil dieses Codes ist sehr schwer zu verstehen, aber wenn Sie dies tun, ist seine Brillanz offensichtlich.

Ein anständiger Compiler generiert den gleichen Code für Zeigerzugriffe und Arrayzugriffe, und Sie sollten sich wahrscheinlich keine Gedanken über dieses Leistungsniveau machen. Die Leute, die Compiler schreiben, wissen weit mehr über ihre Zielarchitekturen als wir Sterblichen. Konzentrieren Sie sich mehr auf die Makroebene, wenn Sie Ihren Code optimieren (Algorithmusauswahl usw.), und vertrauen Sie darauf, dass Ihre Werkzeughersteller ihre Arbeit erledigen.


Tatsächlich wundert es mich, dass der Compiler nicht alles optimiert hat

temp = a[0];

zeile existiert nicht mehr, da temp in der nächsten Zeile mit einem anderen Wert überschrieben wird und a in keiner Weise als volatile gekennzeichnet ist.

Ich erinnere mich an einen urbanen Mythos von vor langer Zeit über einen Benchmark für den neuesten VAX Fortran-Compiler (der mein Alter zeigt), der seine Konkurrenten um mehrere Größenordnungen übertraf.

Es stellte sich heraus, dass der Compiler herausgefunden hat, dass das Ergebnis der Benchmark-Berechnung nirgendwo verwendet wurde, sodass die gesamte Berechnungsschleife in Vergessenheit geriet. Daher die wesentliche Verbesserung der Laufgeschwindigkeit.


pdate: Der Grund dafür, dass optimierter Code in Ihrem speziellen Fall effizienter ist, liegt in der Art und Weise, wie Sie den Speicherort finden. a befindet sich an einem festen Ort, der zum Zeitpunkt des Verbindens/Ladens festgelegt wird, und der Verweis darauf wird gleichzeitig festgelegt. Also wird a[0] oder tatsächlich a[any constant] an einem festen Ort sein.

Und p selbst wird aus dem gleichen Grund auch an einem festen Ort sein. Aber*p (der Inhalt von p) ist variabel und erfordert daher eine zusätzliche Suche, um den richtigen Speicherort zu finden.

Sie werden wahrscheinlich feststellen, dass eine weitere Variable x auf 0 gesetzt ist (nicht const) und die Verwendung von a[x] auch zusätzliche Berechnungen einführt.


In einem Ihrer Kommentare geben Sie an:

Das von Ihnen vorgeschlagene Verhalten führte zu 3 Anweisungen für den Speicherzugriff auch über Arrays (Index abrufen, Wert des Array-Elements abrufen, in Temp speichern). Die Effizienz sehe ich aber immer noch nicht. :

Meine Antwort darauf ist, dass Sie sehr wahrscheinlich --- (nicht eine Effizienz bei der Verwendung von Zeigern sehen. Moderne Compiler müssen mehr als nur herausfinden, dass Array-Operationen und Zeigeroperationen in denselben zugrunde liegenden Maschinencode umgewandelt werden können.

Tatsächlich kann der Zeigercode ohne aktivierte Optimierung weniger effizient sein. Betrachten Sie die folgenden Übersetzungen:

int *pa, i, a[10];

for (i = 0; i < 10; i++)
    a[i] = 100;
/*
    movl    $0, -16(%ebp)              ; this is i, init to 0
L2:
    cmpl    $9, -16(%ebp)              ; from 0 to 9
    jg      L3
    movl    -16(%ebp), %eax            ; load i into register
    movl    $100, -72(%ebp,%eax,4)     ; store 100 based on array/i
    leal    -16(%ebp), %eax            ; get address of i
    incl    (%eax)                     ; increment
    jmp     L2                         ; and loop
L3:
*/

for (pa = a; pa < a + 10; pa++)
    *pa = 100;
/*
    leal    -72(%ebp), %eax
    movl    %eax, -12(%ebp)            ; this is pa, init to &a[0]
L5:
    leal    -72(%ebp), %eax
    addl    $40, %eax
    cmpl    -12(%ebp), %eax            ; is pa at &(a[10])
    jbe     L6                         ; yes, stop
    movl    -12(%ebp), %eax            ; get pa
    movl    $100, (%eax)               ; store 100
    leal    -12(%ebp), %eax            ; get pa
    addl    $4, (%eax)                 ; add 4 (sizeof int)
    jmp     L5                         ; loop around
L6:
*/

An diesem Beispiel können Sie tatsächlich erkennen, dass das Zeigerbeispiel länger ist und nnötigerweise. Es lädt pa mehrfach in %eax, ohne dass es sich ändert, und wechselt tatsächlich %eax zwischen pa und &(a[10]). Die Standardoptimierung ist hier im Grunde genommen gar keine.

Wenn Sie auf Optimierungsstufe 2 wechseln, erhalten Sie folgenden Code:

    xorl    %eax, %eax
L5:
    movl    $100, %edx
    movl    %edx, -56(%ebp,%eax,4)
    incl    %eax
    cmpl    $9, %eax
    jle     L5

für die Array-Version und:

    leal    -56(%ebp), %eax
    leal    -16(%ebp), %edx
    jmp     L14
L16:
    movl    $100, (%eax)
    addl    $4, %eax
L14:
    cmpl    %eax, %edx
    ja      L16

für die Zeigerversion.

Ich werde hier keine Analyse der Taktzyklen durchführen (da es zu viel Arbeit ist und ich im Grunde genommen faul bin), aber ich werde auf eine Sache hinweisen. Es gibt keinen großen Unterschied im Code für beide Versionen in Bezug auf Assembler-Anweisungen, und angesichts der Geschwindigkeit, mit der moderne CPUs tatsächlich ausgeführt werden, werden Sie keinen Unterschied bemerken, wenn Sie nicht Milliarden davon tun Operationen. Ich bevorzuge es immer, Code zur besseren Lesbarkeit zu schreiben, und mache mir nur dann Gedanken über die Leistung, wenn dies zu einem Problem wird.

Abgesehen davon bezieht sich diese Aussage auf:

5.3 Zeiger und Arrays: Die Zeigerversion ist im Allgemeinen schneller, aber zumindest für die Uneingeweihten etwas schwieriger, sie sofort zu erfassen.

stammt aus den frühesten Versionen von K & R, einschließlich meiner alten Version von 1978, in der noch Funktionen geschrieben sind:

getint(pn)
int *pn;
{
    ...
}

Compiler haben seit damals einen furchtbaren langen Weg zurückgelegt.

70
paxdiablo

Wenn Sie Embedded-Plattformen programmieren, werden Sie schnell feststellen, dass die Zeigermethode viel schneller ist als die Verwendung eines Index.

struct bar a[10], *p;

void foo()
{
    int i;

    // slow loop
    for (i = 0; i < 10; ++i)
        printf( a[i].value);

    // faster loop
    for (p = a; p < &a[10]; ++p)
        printf( p->value);
}

Die langsame Schleife muss jedes Mal a + (i * sizeof (struct bar)) berechnen, während die zweite nur jedes mal sizeof (struct bar) zu p hinzufügen muss. Die Multiplikationsoperation verwendet mehr Taktzyklen als viele Prozessoren.

Sie sehen wirklich Verbesserungen, wenn Sie ein [i] mehrfach in der Schleife referenzieren. Einige Compiler speichern diese Adresse nicht im Cache, sodass sie innerhalb der Schleife möglicherweise mehrmals neu berechnet wird.

Aktualisieren Sie Ihr Beispiel, um eine Struktur zu verwenden und auf mehrere Elemente zu verweisen.

11
tomlogic

Im ersten Fall kennt der Compiler direkt die Adresse des Arrays (dies ist auch die Adresse des ersten Elements) und greift darauf zu. Im zweiten Fall kennt er die Adresse des Zeigers und liest den Zeigerwert, der auf diesen Speicherplatz zeigt. Das ist eine zusätzliche Umkehrung, daher ist es hier vermutlich langsamer.

8

Die Geschwindigkeit wird vor allem in Schleifen gewonnen. Wenn Sie ein Array verwenden, würden Sie einen Zähler verwenden, den Sie erhöhen. Um die Position zu berechnen, multipliziert das System diesen Zähler mit der Größe des Array-Elements und fügt dann die Adresse des ersten Elements hinzu, um die Adresse zu erhalten. Mit Zeigern müssen Sie nur zum nächsten Element gehen Erhöhen Sie den aktuellen Zeiger mit der Größe des Elements, um das nächste zu erhalten, vorausgesetzt, alle Elemente befinden sich im Speicher nebeneinander.

Die Zeigerarithmetik benötigt daher beim Durchführen von Schleifen etwas weniger Berechnungen. Zeiger auf das rechte Element zu haben, ist schneller als die Verwendung eines Index innerhalb eines Arrays.

Die moderne Entwicklung entfernt jedoch langsam viele Zeigeroperationen. Prozessoren werden immer schneller und Arrays lassen sich einfacher verwalten als Zeiger. Außerdem verringern Arrays die Anzahl der Fehler im Code. Das Array erlaubt Indexprüfungen, um sicherzustellen, dass Sie nicht auf Daten außerhalb des Arrays zugreifen.

7
Wim ten Brink

Wie paxdiablo sagte: Jeder neue Compiler wird sie sehr ähnlich machen.

Mehr noch, ich sah Situationen, in denen Array schneller als Zeiger war. Dies war auf einem DSP-Prozessor, der Vektoroperationen verwendet. 

In diesem Fall ähnelte die Verwendung von Arrays der Verwendung von limits - Zeigern. Durch die Verwendung von zwei Arrays weiß der Compiler -implicitly, dass sie nicht auf dieselbe Position verweisen. Wenn Sie jedoch mit 2 Zeigern arbeiten, kann der Compiler denken, dass sie auf dieselbe Position zeigen und die Pipe-Auskleidung überspringen.

zum Beispiel:

int a[10],b[10],c[10];
int *pa=a, *pb=b, *pc=c;
int i;

// fill a and b.
fill_arrays(a,b);

// set c[i] = a[i]+b[i];
for (i = 0; i<10; i++)
{
   c[i] = a[i] + b[i];
}

// set *pc++ = *pa++ + *pb++;
for (i = 0; i<10; i++)
{
   *pc++ = *pa++ + *pb++;
}

In Fall 1 kann der Compiler problemlos a und b hinzufügen und den Wert in c speichern.

In Fall 2 führt der Compiler keine Pipeline durch, weil er beim Speichern von C möglicherweise a oder b überschreibt. 

7
Yousf

Zeiger drücken natürlich einfache Induktionsvariablen aus, während Subskriptionen etwas kompliziertere Compiler-Optimierungen erfordern


In vielen Fällen erfordert die Verwendung eines subskribierten Ausdrucks, dass dem Problem eine zusätzliche Ebene hinzugefügt wird. Eine Schleife, die einen Index i inkrementiert, kann als Zustandsmaschine verwendet werden, und der Ausdruck a [i] erfordert bei jeder Verwendung technisch, dass i mit dem multipliziert wird Größe jedes Elements und zur Basisadresse hinzugefügt.

Um dieses Zugriffsmuster in Zeiger umzuwandeln, muss der Compiler die gesamte Schleife analysieren und feststellen, dass beispielsweise auf jedes Element zugegriffen wird. Dann kann der Compiler die mehreren Instanzen des Multiplizierens des Index durch die Elementgröße mit einem einfachen Inkrement des vorherigen Schleifenwerts ersetzen. Dieser Prozess kombiniert Optimierungen, die als Eliminierung allgemeiner Teilausdrücke und Verringerung der Induktionsvariablenstärke. Bezeichnet werden.

Beim Schreiben mit Zeigern ist nicht der gesamte Optimierungsprozess erforderlich, da der Programmierer normalerweise nur durch das Array geht, um mit zu beginnen.

Manchmal kann der Compiler die Optimierung durchführen und manchmal nicht. In den letzten Jahren ist es üblicher, einen ausgeklügelten Compiler zur Hand zu haben. Zeiger-basierter Code ist also nicht immer schneller.

Da Arrays normalerweise zusammenhängend sein müssen, besteht ein weiterer Vorteil für Zeiger darin, inkrementell zugewiesene Verbundstrukturen zu erstellen.

7
DigitalRoss

Dies ist eine sehr alte Frage und wurde beantwortet, als solche brauche ich keine Antwort! Ich habe jedoch keine einfache Antwort bemerkt, also eine Antwort geben.

ANTWORT: Ein indirekter Zugriff (Zeiger/Array) "fügt" möglicherweise eine zusätzliche Anweisung hinzu, um die (Basis-) Adresse zu laden, aber alle darauf folgenden Zugriffe (Elemente im Falle von Array/Members im Falle eines Zeigers auf Struktur) sollten nur eine Anweisung sein weil es sich lediglich um das Hinzufügen eines Offsets zu der (Basis-) Adresse handelt, die bereits geladen ist. In gewisser Weise wird es so gut wie der direkte Zugang sein. Daher ist in der Mehrzahl der Fälle der Zugriff über Array/Pointer gleichwertig und Elementzugriffe sind ebenso gut wie ein direkter Zugriff auf eine Variable.

Ex. Wenn ich ein Array (oder einen Zeiger) mit 10 Elementen oder eine Struktur mit 10 Elementen habe (auf die über einen Zeiger auf die Struktur zugegriffen wird) und auf ein Element/Member zugreifen, ist die eine mögliche zusätzliche Anweisung nur einmal am Anfang erforderlich. Alle Element/Member-Zugriffe sollten danach nur noch eine Anweisung sein.

3
RcnRcf

Hier erhalten Sie gute Antworten auf Ihre Frage, aber da Sie gerade lernen, ist es wichtig, darauf hinzuweisen, dass Effizienz auf dieser Ebene selten wahrnehmbar ist.

Wenn Sie ein Programm auf maximale Leistung optimieren, sollten Sie mindestens genauso viel Aufmerksamkeit darauf verwenden, größere Probleme in der Programmstruktur zu finden und zu beheben. Nachdem diese behoben wurden, können Low-Level-Optimierungen einen weiteren Unterschied ausmachen.

Hier ist ein Beispiel, wie das gemacht werden kann.

2
Mike Dunlavey

Zeiger waren früher schneller als Arrays. Vor einiger Zeit, als die C-Sprache entworfen wurde, waren die Zeiger um einiges schneller. Heutzutage können Optimierer Arrays jedoch normalerweise besser optimieren als Zeiger, da Arrays stärker eingeschränkt sind. 

Befehlssätze moderner Prozessoren wurden ebenfalls entwickelt, um den Array-Zugriff zu optimieren. 

Die Quintessenz ist, dass Arrays heutzutage oft schneller sind, insbesondere wenn sie in Schleifen mit Indexvariablen verwendet werden. 

Natürlich würden Sie immer noch Zeiger für Verknüpfungslisten verwenden wollen, aber die alte Zeitoptimierung, einen Zeiger durch ein Array zu ziehen, anstatt eine Indexvariable zu verwenden, ist jetzt wahrscheinlich eine Desoptimierung.

2
John Knoeller

Da 0 als Konstante definiert ist, ist a [0] auch eine Konstante, und der Compiler weiß, wo er sich zur Kompilierzeit befindet. Im "normalen" Fall müsste der Compiler die Elementadresse aus Basis + Offset berechnen (wobei der Offset entsprechend der Elementgröße skaliert wird).

OTOH, p ist eine Variable, und die Indirektion erfordert eine zusätzliche Bewegung.

Generell wird der Array-Index ohnehin intern als Zeigerarithmetik behandelt, daher ist mir nicht ganz klar, welchen Punkt der K & R versucht hat.

1
filofel

Da die meisten Leute bereits detaillierte Antworten gegeben haben, gebe ich nur ein intuitives Beispiel. Wenn Sie Array und Zeiger in größerem Maßstab verwenden, ist die Effizienz der Zeigernutzung höher. Wenn Sie beispielsweise einen großen langen int-Datensatz sortieren möchten, indem Sie ihn in mehrere Teilmengen sortieren und diese dann zusammenführen.

long int * testData = calloc(N, sizeof(long int));

Für tägliche 8G-RAM-Maschinen im Jahr 2017 können wir N auf 400000000 festlegen, was bedeutet, dass Sie für diesen Originaldatensatz ungefähr 1,5G Speicher verwenden. Und wenn Sie MPI verwenden, können Sie Ihre Daten schnell trennen, indem Sie verwenden

MPI_Scatterv(testData, partitionLength, partitionIndex, MPI_LONG, MPI_IN_PLACE, N/number_of_thread, MPI_LONG, 0, MPI_COMM_WORLD);

Sie können paritionLength einfach als Zeiger behandeln, der N/number_of_thread Als Länge für jedes identische Teil speichert, und partitionIndex als Zeiger behandeln, der N/number_of_threads speichert, die Index zunehmend anstarren. Angenommen, Sie haben eine 4-Kern-CPU und trennen Ihren Job nur in 4 Threads. MPI wird auf jeden Fall die Arbeit in einem schnellen Sinn durch die Referenzen erledigen. Wenn Sie jedoch ein Array verwenden, muss diese Routine eine Zeigerarithmetik für das Array ausführen, um zuerst den Partitionspunkt zu finden. Welches ist nicht so direkt wie Zeiger. Wenn Sie den partitionierten Datensatz zusammenführen, möchten Sie möglicherweise auch mit K-way merge Beschleunigen. Sie benötigen einen temporären Speicherplatz, um die vier sortierten Datensätze zu speichern. Wenn Sie hier einen Zeiger verwenden, müssen Sie nur 4 Adressen speichern. Wenn Sie jedoch ein Array verwenden, werden 4 ganze Sub-Arrays gespeichert, was nicht effizient ist. Wenn Sie nicht mit MPI_Barrier Sicherstellen, dass Ihr Programm threadsicher ist, kann es vorkommen, dass MPI sich sogar über eine schlechte Speicherimplementierung beschwert. Ich habe eine 32G-Maschine zum Sortieren von 400000000 langen Werten auf 8 Threads nach Array-Methode und Zeigermethode, ich habe 11.054980s und 13.182739s entsprechend. Und wenn ich die Größe auf 1000000000 erhöhe, wird mein Sortierprogramm nicht erfolgreich ausgeführt, wenn ich ein Array verwende. Aus diesem Grund verwenden viele Benutzer Zeiger für alle Datenstrukturen, mit Ausnahme der Skalare in C.

1
Lingbo Tang

"Die Zeigerversion ist im Allgemeinen schneller" bedeutet, dass es für den Compiler in den meisten Fällen einfacher ist, effizienteren Code mit einem Zeiger zu generieren (der lediglich dereferenziert werden muss) als mit einem Array und einem Index (was den Compiler bedeutet) Adresse vom Anfang des Arrays verschieben). Bei den modernen Prozessoren und den optimierenden Compilern ist der Arrayzugriff im typischen Fall jedoch nicht langsamer als der Zeigerzugriff.

In Ihrem Fall müssten Sie die Optimierung einschalten, um das gleiche Ergebnis zu erhalten.

1
Vlad

ich bin ein wenig überrascht, dass der ptr schneller ist als die array-diskussion. Der Beweis, dass dies nicht der Fall ist, wird anfänglich durch den asm-Code von Abhijith gegeben.

mov eax, dord ptr _a; // Wert direkt von Adresse _a laden

vs

mov eax, dword ptr _p; // Adresse/Wert von p in eax laden

und

mov ecx, dword ptr [eax]; // benutze die geladene Adresse, um auf den Wert zuzugreifen und ihn in ecx einzufügen

Ein Array stellt eine feste Adresse dar, so dass die CPU direkt darauf zugreifen kann. Bei der Option Ptr muss sie dereferenziert werden, damit die CPU auf den Wert zugreifen kann!

Der zweite Code-Stapel ist nicht vergleichbar, da der Array-Offset berechnet werden muss. Um dies zu erreichen, benötigen Sie mindestens 1/2 weitere Anweisungen!

Alles, was ein Compiler während der Kompilierzeit ableiten kann (feste Adressen, Offsets usw.), ist der Schlüssel zu performantem Code . Vergleichen von iterativem Code und Zuweisen von vars:

Array:

; 2791: tmp = buf_ai [l];

mov eax, DWORD PTR _l$[ebp]
mov ecx, DWORD PTR _buf_ai$[ebp+eax*4]
mov DWORD PTR _tmp$[ebp], ecx

vs

PTR

; 2796: tmp2 = * p;

mov eax, DWORD PTR _p$[ebp]
mov ecx, DWORD PTR [eax]
mov DWORD PTR _tmp2$[ebp], ecx

Plus

; 2801: ++ p;

mov eax, DWORD PTR _p$[ebp]
add eax, 4
mov DWORD PTR _p$[ebp], eax

Es ist nur für die ptr load address, bevor Sie es verwenden, im Vergleich zu Array use address und erhalten Sie gleichzeitig einen Wert!

freundliche Grüße

0
SwDev42