Realistische Verwendung des C99-Schlüsselworts „restrict“?

Ich habe einige Dokumentationen und Fragen/Antworten durchgesehen und gesehen, dass es erwähnt wurde. Ich habe eine kurze Beschreibung gelesen, die besagt, dass es im Grunde ein Versprechen des Programmierers wäre, dass der Zeiger nicht verwendet wird, um auf etwas anderes zu zeigen.

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

restrict besagt, dass der Zeiger das einzige ist, was auf das zugrunde liegende Objekt zugreift. Es eliminiert 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 kann, 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 muss if richtig handhaben dest, src1und src2 sich überlappen, was bedeutet, dass von Anfang bis Ende jeweils eine Multiplikation durchgeführt werden muss. Indem restrictkann der Compiler diesen Code mithilfe der Vektoranweisungen optimieren.

Wikipedia hat einen Eintrag auf restrictmit einem anderen Beispiel, hier.

Das Wikipedia-Beispiel ist sehr erhellend.

Es zeigt deutlich wie Es ermöglicht das Speichern einer Montageanleitung.

Ohne Einschränkung:

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

Pseudo-Assembly:

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 x may point to a (a aliased by x) thus 
; the value of x will change when the value of a
; changes.
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-Assembly:

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" is no longer needed.
load R2 ← *b
add R2 += R1
set R2 → *b

Tut GCC das wirklich?

GCC 4.8 Linux x86-64:

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

Mit -O0Sie sind 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 den Uneingeweihten, die Berufungskonvention ist:

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

Die GCC-Ausgabe war noch klarer als der Wiki-Artikel: 4 Anweisungen vs. 3 Anweisungen.

Arrays

Bisher haben wir Einsparungen bei einzelnen Anweisungen, aber wenn Zeiger Arrays darstellen, die durchlaufen werden sollen, ein häufiger Anwendungsfall, dann könnten eine Reihe von Anweisungen eingespart 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;
    }
}

Durch restrictein intelligenter Compiler (oder Mensch), könnte dies optimieren zu:

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

was potenziell viel effizienter ist, da es auf einer anständigen libc-Implementierung (wie glibc) für die Assemblierung optimiert werden kann: Ist es in Bezug auf die Leistung besser, std::memcpy() oder std::copy() zu verwenden?

Tut 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 -O0beide sind gleich.

Mit -O3:

• mit Einschränkung:

  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 memset ruft wie erwartet an.

• ohne Einschränkung: keine stdlib-Aufrufe, nur 16 Iterationen breit Schleife abrollen was ich hier nicht wiedergeben möchte 🙂

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

C99

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

restrict besagt, dass zwei Zeiger nicht auf überlappende Speicherbereiche zeigen können. Die häufigste Verwendung ist für Funktionsargumente.

Dies schränkt ein, wie die Funktion aufgerufen werden kann, ermöglicht jedoch weitere Optimierungen zur Kompilierzeit.

Wenn der Anrufer dem nicht folgt restrict Vertrag, undefiniertes Verhalten.

Das C99 N1256-Entwurf 6.7.3/7 “Type Qualifiers” sagt:

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

und 6.7.3.1 „Formale Definition von Beschränkung“ liefert die blutigen Details.

Strenge Aliasing-Regel

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

Siehe: Was ist die strikte Aliasing-Regel?

Siehe auch

• C++14 hat noch kein Analogon für restrictaber GCC hat __restrict__ als Erweiterung: Was bedeutet das Schlüsselwort „restrict“ in C++?
• Viele Fragen, die sich stellen: Laut den blutigen Details, ist dieser Code UB oder nicht?
  • Restriktionskennzeichner anhand von Beispielen verstehen
  • Eingeschränkte Zeigerfragen
  • Ist es legal, einen eingeschränkten Zeiger einem anderen Zeiger zuzuweisen und den zweiten Zeiger zu verwenden, um den Wert zu ändern?
• Eine “Wann zu verwenden”-Frage: Wann ist die Verwendung einzuschränken und wann nicht
• Der zugehörige GCC __attribute__((malloc))was besagt, dass der Rückgabewert einer Funktion keinem Alias ​​zugeordnet ist: GCC: __attribute__((malloc))

Der folgende C99-Code gibt je nach entweder 0 oder 1 zurück beschränken Qualifikation :

__attribute__((noinline))
int process(const int * restrict const a, int * const b) {
    *b /= (*a + 1) ;
    return *a + *b ;
}

int main(void) {
    int data[2] = {1, 2};
    return process(&data[0], &data[0]);
}

Mit dem Snippet können Sie realistische Beispiele erstellen, insbesondere wenn *a ist eine Schleifenbedingung.

Kompilieren mit gcc -std=c99 -Wall -pedantic -O3 main.c.