Realistische Verwendung des C99-Schlüsselworts "einschränken"?

182

Ich habe einige Dokumentationen und Fragen / Antworten durchgesehen und gesehen, dass sie erwähnt wurden. Ich las eine kurze Beschreibung und erklärte, dass es im Grunde ein Versprechen des Programmierers wäre, dass der Zeiger nicht verwendet wird, um auf eine andere Stelle zu zeigen.

Kann jemand einige realistische Fälle anbieten, in denen es sich lohnt, dies tatsächlich zu verwenden?

user90052
quelle
4
memcpyvs memmoveist ein kanonisches Beispiel.
Alexandre C.
@AlexandreC.: Ich denke nicht, dass dies besonders zutreffend ist, da das Fehlen eines "Einschränkungs" -Qualifikators nicht bedeutet, dass die Programmlogik mit Überladung von Quelle und Ziel funktioniert, und das Vorhandensein eines solchen Qualifikators würde auch nicht verhindern, dass eine aufgerufene Methode dies tut Bestimmen, ob sich Quelle und Ziel überschneiden, und wenn ja, Dest durch src + (dest-src) ersetzen, das, da es von src abgeleitet ist, einen Alias ​​erhalten darf.
Supercat
@supercat: Deshalb habe ich es als Kommentar gesetzt. 1) Das restrictQualifizieren von Argumenten, um memcpyim Prinzip eine aggressive Optimierung einer naiven Implementierung zu ermöglichen, und 2) das bloße Aufrufen memcpyermöglichen es dem Compiler anzunehmen, dass die ihm gegebenen Argumente keinen Alias ​​darstellen, was eine gewisse Optimierung um den memcpyAufruf herum ermöglichen könnte .
Alexandre C.
@AlexandreC.: Es wäre für einen Compiler auf den meisten Plattformen sehr schwierig, ein naives Memcpy - selbst mit "Einschränken" - so zu optimieren, dass es bei weitem nicht so effizient ist wie eine auf das Ziel zugeschnittene Version. Anrufseitige Optimierungen würden das Schlüsselwort "einschränken" nicht erfordern, und in einigen Fällen können Bemühungen, diese zu vereinfachen, kontraproduktiv sein. Zum Beispiel könnten viele Implementierungen von memcpy ohne zusätzliche Kosten memcpy(anything, anything, 0);als No-Op angesehen werden und sicherstellen, dass if pein Zeiger auf mindestens nbeschreibbare Bytes ist memcpy(p,p,n). wird keine nachteiligen Nebenwirkungen haben. Solche Fälle können auftreten ...
Supercat
... natürlich kann es bei bestimmten Arten von Anwendungscode (z. B. einer Sortierroutine, bei der ein Element mit sich selbst ausgetauscht wird) und bei Implementierungen, bei denen keine nachteiligen Nebenwirkungen auftreten, effizienter sein, diese Fälle vom allgemeinen Fallcode behandeln zu lassen, als dies zu tun Sonderfalltests hinzufügen. Leider scheinen einige Compiler-Autoren der Meinung zu sein, dass es besser ist, von Programmierern zu verlangen, dass sie Code hinzufügen, den der Compiler möglicherweise nicht optimieren kann, um "Optimierungsmöglichkeiten" zu ermöglichen, die Compiler ohnehin nur sehr selten nutzen würden.
Supercat

Antworten:

180

restrictsagt, dass der Zeiger das einzige ist, was auf das zugrunde liegende Objekt zugreift. Es beseitigt das Potenzial für Zeiger-Aliasing und ermöglicht eine bessere Optimierung durch den Compiler.

Angenommen, ich habe eine Maschine mit speziellen Anweisungen, die Vektoren von Zahlen im Speicher multiplizieren können, und ich habe den folgenden Code:

void MultiplyArrays(int* dest, int* src1, int* src2, int n)
{
    for(int i = 0; i < n; i++)
    {
        dest[i] = src1[i]*src2[i];
    }
}

Der Compiler Bedürfnisse richtig handhaben, wenn dest, src1und src2überlappen, was bedeutet es eine Multiplikation zu einem Zeitpunkt tun müssen, von Anfang bis zum Ende. Auf diese Weise restrictkann der Compiler diesen Code mithilfe der Vektoranweisungen optimieren.

Wikipedia hat einen Eintrag auf restrict, mit einem anderen Beispiel hier .

Michael
quelle
3
@Michael - Wenn ich mich nicht irre, dann wäre das Problem nur, wenn destsich einer der Quellvektoren überlappt. Warum sollte es ein Problem geben, wenn src1und src2überlappen?
Ysap
1
Normalerweise wirkt sich einschränken nur aus, wenn auf ein Objekt verwiesen wird, das geändert wurde. In diesem Fall wird behauptet, dass keine versteckten Nebenwirkungen berücksichtigt werden müssen. Die meisten Compiler verwenden es, um die Vektorisierung zu erleichtern. Zu diesem Zweck verwendet Msvc die Laufzeitprüfung auf Datenüberlappung.
Tim18
Durch Hinzufügen des Schlüsselworts register zur Variablen for loop wird diese zusätzlich zum Hinzufügen von einschränken schneller.
2
Eigentlich ist das Schlüsselwort register nur eine Empfehlung. Und in Compilern seit ungefähr dem Jahr 2000 wird das i (und das n für den Vergleich) im Beispiel in ein Register optimiert, unabhängig davon, ob Sie das Schlüsselwort register verwenden oder nicht.
Mark Fischler
151

Das Wikipedia-Beispiel ist sehr aufschlussreich.

Es zeigt deutlich, wie eine Montageanweisung gespeichert werden kann .

Ohne Einschränkung:

void f(int *a, int *b, int *x) {
  *a += *x;
  *b += *x;
}

Pseudo-Assemblierung:

load R1  *x    ; Load the value of x pointer
load R2  *a    ; Load the value of a pointer
add R2 += R1    ; Perform Addition
set R2  *a     ; Update the value of a pointer
; Similarly for b, note that x is loaded twice,
; because a may be equal to x.
load R1  *x
load R2  *b
add R2 += R1
set R2  *b

Mit Einschränkung:

void fr(int *restrict a, int *restrict b, int *restrict x);

Pseudo-Assemblierung:

load R1  *x
load R2  *a
add R2 += R1
set R2  *a
; Note that x is not reloaded,
; because the compiler knows it is unchanged
; load R1  *x
load R2  *b
add R2 += R1
set R2  *b

Macht GCC das wirklich?

GCC 4.8 Linux x86-64:

gcc -g -std=c99 -O0 -c main.c
objdump -S main.o

Mit -O0sind sie gleich.

Mit -O3:

void f(int *a, int *b, int *x) {
    *a += *x;
   0:   8b 02                   mov    (%rdx),%eax
   2:   01 07                   add    %eax,(%rdi)
    *b += *x;
   4:   8b 02                   mov    (%rdx),%eax
   6:   01 06                   add    %eax,(%rsi)  

void fr(int *restrict a, int *restrict b, int *restrict x) {
    *a += *x;
  10:   8b 02                   mov    (%rdx),%eax
  12:   01 07                   add    %eax,(%rdi)
    *b += *x;
  14:   01 06                   add    %eax,(%rsi) 

Für die Uneingeweihten lautet die aufrufende Konvention :

  • rdi = erster Parameter
  • rsi = zweiter Parameter
  • rdx = dritter Parameter

Die GCC-Ausgabe war noch deutlicher als der Wiki-Artikel: 4 Anweisungen gegen 3 Anweisungen.

Arrays

Bisher haben wir Einsparungen bei einzelnen Befehlen, aber wenn Zeiger Arrays darstellen, die durchlaufen werden sollen, ein häufiger Anwendungsfall, dann könnte eine Reihe von Befehlen gespeichert werden, wie von Supercat erwähnt .

Betrachten Sie zum Beispiel:

void f(char *restrict p1, char *restrict p2) {
    for (int i = 0; i < 50; i++) {
        p1[i] = 4;
        p2[i] = 9;
    }
}

Wegen restrict, ein Smart - Compiler (oder Menschen), könnten diese optimieren:

memset(p1, 4, 50);
memset(p2, 9, 50);

Dies ist möglicherweise viel effizienter, da es für eine anständige libc-Implementierung (wie glibc) für die Assembly optimiert werden kann: Ist es in Bezug auf die Leistung besser, std :: memcpy () oder std :: copy () zu verwenden?

Macht GCC das wirklich?

GCC 5.2.1.Linux x86-64 Ubuntu 15.10:

gcc -g -std=c99 -O0 -c main.c
objdump -dr main.o

Mit -O0sind beide gleich.

Mit -O3:

  • mit einschränken:

    3f0:   48 85 d2                test   %rdx,%rdx
    3f3:   74 33                   je     428 <fr+0x38>
    3f5:   55                      push   %rbp
    3f6:   53                      push   %rbx
    3f7:   48 89 f5                mov    %rsi,%rbp
    3fa:   be 04 00 00 00          mov    $0x4,%esi
    3ff:   48 89 d3                mov    %rdx,%rbx
    402:   48 83 ec 08             sub    $0x8,%rsp
    406:   e8 00 00 00 00          callq  40b <fr+0x1b>
                            407: R_X86_64_PC32      memset-0x4
    40b:   48 83 c4 08             add    $0x8,%rsp
    40f:   48 89 da                mov    %rbx,%rdx
    412:   48 89 ef                mov    %rbp,%rdi
    415:   5b                      pop    %rbx
    416:   5d                      pop    %rbp
    417:   be 09 00 00 00          mov    $0x9,%esi
    41c:   e9 00 00 00 00          jmpq   421 <fr+0x31>
                            41d: R_X86_64_PC32      memset-0x4
    421:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)
    428:   f3 c3                   repz retq

    Zwei memsetAnrufe wie erwartet.

  • ohne Einschränkung: keine stdlib-Aufrufe, nur eine 16 Iterationen breite Schleife, die ich hier nicht reproduzieren möchte :-)

Ich hatte nicht die Geduld, sie zu vergleichen, aber ich glaube, dass die eingeschränkte Version schneller sein wird.

C99

Schauen wir uns der Vollständigkeit halber den Standard an.

restrictsagt, dass zwei Zeiger nicht auf überlappende Speicherbereiche zeigen können. Die häufigste Verwendung sind Funktionsargumente.

Dies schränkt den Aufruf der Funktion ein, ermöglicht jedoch mehr Optimierungen zur Kompilierungszeit.

Wenn der Anrufer dem restrictVertrag nicht folgt , undefiniertes Verhalten.

Der C99 N1256 Entwurf 6.7.3 / 7 "Typqualifizierer" sagt:

Die beabsichtigte Verwendung des Einschränkungsqualifizierers (wie der Registerspeicherklasse) besteht darin, die Optimierung zu fördern, und das Löschen aller Instanzen des Qualifizierers aus allen vorverarbeitenden Übersetzungseinheiten, aus denen ein konformes Programm besteht, ändert seine Bedeutung nicht (dh das beobachtbare Verhalten).

und 6.7.3.1 "Formale Definition von Beschränkung" gibt die blutigen Details an.

Strikte Aliasing-Regel

Das restrictSchlüsselwort wirkt sich nur auf Zeiger kompatibler Typen aus (z. B. zwei int*), da die strengen Aliasing-Regeln besagen, dass das Aliasing inkompatibler Typen standardmäßig ein undefiniertes Verhalten ist. Compiler können daher davon ausgehen, dass dies nicht der Fall ist, und optimieren.

Siehe: Was ist die strenge Aliasing-Regel?

Siehe auch

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
quelle
9
Das Qualifikationsmerkmal "einschränken" kann tatsächlich viel größere Einsparungen ermöglichen. Beispielsweise void zap(char *restrict p1, char *restrict p2) { for (int i=0; i<50; i++) { p1[i] = 4; p2[i] = 9; } }würden die Einschränkungsqualifizierer den Compiler den Code als "memset (p1,4,50); memset (p2,9,50);" umschreiben lassen. Restrict ist typbasiertem Aliasing weit überlegen. Es ist eine Schande, dass sich Compiler mehr auf Letzteres konzentrieren.
Supercat
@ Supercat tolles Beispiel, hinzugefügt, um zu antworten.
Ciro Santilli 法轮功 冠状 病. 事件 9
2
@ tim18: Das Schlüsselwort "einschränken" kann viele Optimierungen ermöglichen, die selbst aggressive typbasierte Optimierungen nicht können. Darüber hinaus macht es das Vorhandensein von "Einschränken" in der Sprache - im Gegensatz zu aggressivem typbasiertem Aliasing - niemals unmöglich, Aufgaben so effizient auszuführen, wie dies in ihrer Abwesenheit möglich wäre (da Code, der durch "Einschränken" gebrochen würde, dies einfach kann Verwenden Sie es nicht, während Code, der durch aggressive TBAA beschädigt wird, häufig weniger effizient umgeschrieben werden muss.
Supercat
2
@ tim18: Umgeben Sie Dinge, die in Backticks doppelte Unterstreichungen enthalten, wie in __restrict. Andernfalls werden die doppelten Unterstreichungen möglicherweise falsch interpretiert, um anzuzeigen, dass Sie schreien.
Supercat
1
Wichtiger als nicht zu schreien ist, dass die Unterstriche eine Bedeutung haben, die direkt für den Punkt relevant ist, den Sie ansprechen möchten.
Remcycles