Regeln für die Verwendung des Schlüsselworts “restrict” in C?

Ich versuche zu verstehen, wann und wann nicht zu verwenden restrict Schlüsselwort in C und in welchen Situationen es einen greifbaren Nutzen bringt.

Nach dem Lesen, “Entmystifizierung des Restrict-Keywords“, (der einige Faustregeln für die Verwendung enthält), habe ich den Eindruck, dass, wenn einer Funktion Zeiger übergeben werden, die Möglichkeit berücksichtigt werden muss, dass sich die Daten, auf die gezeigt wird, mit anderen übergebenen Argumenten überschneiden (Alias). Funktion. Gegeben eine Funktion:

foo(int *a, int *b, int *c, int n) {
    for (int i = 0; i<n; ++i) {
        b[i] = b[i] + c[i];
        a[i] = a[i] + b[i] * c[i];
    } 
}

der Compiler muss neu geladen werden c im zweiten Ausdruck, weil vielleicht b und c zeigen auf die gleiche Stelle. Auch darauf muss gewartet werden b gespeichert werden, bevor es geladen werden kann a aus dem gleichen Grunde. Darauf muss dann gewartet werden a gespeichert werden und neu geladen werden müssen b und c am Anfang der nächsten Schleife. Wenn Sie die Funktion so aufrufen:

int a[N];
foo(a, a, a, N);

dann können Sie sehen, warum der Compiler dies tun muss. Verwenden restrict teilt dem Compiler effektiv mit, dass Sie dies niemals tun werden, damit er die redundante Last von fallen lassen kann c und laden a Vor b wird gelagert.

In einem anderen SO-Beitrag liefert Nils Pipenbrinck ein Arbeitsbeispiel für dieses Szenario, das den Leistungsvorteil demonstriert.

Bisher habe ich gesammelt, dass es eine gute Idee ist, es zu verwenden restrict Bei Zeigern übergeben Sie Funktionen, die nicht eingebettet werden. Anscheinend kann der Compiler herausfinden, dass sich die Zeiger nicht überlappen, wenn der Code inline ist.

Jetzt fangen die Dinge an, für mich verschwommen zu werden.

In Ulrich Dreppers Aufsatz „Was jeder Programmierer über Speicher wissen sollte“ macht er die Aussage, dass „sofern nicht restriktiv verwendet wird, alle Zeigerzugriffe potenzielle Aliasing-Quellen sind“, und er gibt ein spezifisches Codebeispiel einer Submatrix-Matrix multiplizieren, wo er sie verwendet restrict.

Wenn ich jedoch seinen Beispielcode entweder mit oder ohne kompiliere restrict Ich bekomme in beiden Fällen identische Binärdateien. Ich benutze gcc version 4.2.4 (Ubuntu 4.2.4-1ubuntu4)

Was ich im folgenden Code nicht herausfinden kann, ist, ob er umgeschrieben werden muss, um ihn umfassender zu nutzen restrictoder ob die Aliasanalyse in GCC nur so gut ist, dass sie herausfinden kann, dass keines der Argumente sich gegenseitig aliasiert. Wie kann ich zu rein pädagogischen Zwecken die Verwendung oder Nichtverwendung vornehmen? restrict Angelegenheit in diesem Code – und warum?

Zum restrict zusammengestellt mit:

gcc -DCLS=$(getconf LEVEL1_DCACHE_LINESIZE) -DUSE_RESTRICT -Wextra -std=c99 -O3 matrixMul.c -o matrixMul

Einfach entfernen -DUSE_RESTRICT nicht zu verwenden restrict.

#include <stdlib.h>
#include <stdio.h>
#include <emmintrin.h>

#ifdef USE_RESTRICT
#else
#define restrict
#endif

#define N 1000
double _res[N][N] __attribute__ ((aligned (64)));
double _mul1[N][N] __attribute__ ((aligned (64)))
    = { [0 ... (N-1)] 
    = { [0 ... (N-1)] = 1.1f }};
double _mul2[N][N] __attribute__ ((aligned (64)))
    = { [0 ... (N-1)] 
    = { [0 ... (N-1)] = 2.2f }};

#define SM (CLS / sizeof (double))

void mm(double (* restrict res)[N], double (* restrict mul1)[N], 
        double (* restrict mul2)[N]) __attribute__ ((noinline));

void mm(double (* restrict res)[N], double (* restrict mul1)[N], 
        double (* restrict mul2)[N])
{
 int i, i2, j, j2, k, k2; 
    double *restrict rres; 
    double *restrict rmul1; 
    double *restrict rmul2; 

    for (i = 0; i < N; i += SM)
        for (j = 0; j < N; j += SM)
            for (k = 0; k < N; k += SM)
                for (i2 = 0, rres = &res[i][j],
                    rmul1 = &mul1[i][k]; i2 < SM;
                    ++i2, rres += N, rmul1 += N)
                    for (k2 = 0, rmul2 = &mul2[k][j];
                        k2 < SM; ++k2, rmul2 += N)
                        for (j2 = 0; j2 < SM; ++j2)
                          rres[j2] += rmul1[k2] * rmul2[j2];
}

int main (void)
{

    mm(_res, _mul1, _mul2);

 return 0;
}

Es ist ein Hinweis auf den Code-Optimierer. Die Verwendung von „restrict“ stellt sicher, dass eine Zeigervariable in einem CPU-Register gespeichert werden kann und eine Aktualisierung des Zeigerwerts nicht in den Speicher geleert werden muss, sodass ein Alias ​​ebenfalls aktualisiert wird.

Ob es davon profitiert oder nicht, hängt stark von den Implementierungsdetails des Optimierers und der CPU ab. Code-Optimierer investieren bereits viel in die Erkennung von Non-Aliasing, da es sich um eine so wichtige Optimierung handelt. Es sollte keine Probleme haben, dies in Ihrem Code zu erkennen.

Außerdem hat GCC 4.0.0-4.4 einen Regressionsfehler, der dazu führt, dass das Schlüsselwort “restrict” ignoriert wird. Dieser Fehler wurde in 4.5 als behoben gemeldet (ich habe jedoch die Fehlernummer verloren).

(Ich weiß nicht, ob Ihnen die Verwendung dieses Schlüsselworts tatsächlich einen erheblichen Vorteil verschafft. Es ist für Programmierer sehr einfach, sich mit diesem Qualifizierer zu irren, da es keine Durchsetzung gibt, sodass ein Optimierer nicht sicher sein kann, dass der Programmierer nicht “lügt”. )

Wenn Sie wissen, dass ein Zeiger A der einzige Zeiger auf einen Speicherbereich ist, das heißt, er hat keine Aliase (das heißt, jeder andere Zeiger B ist notwendigerweise ungleich A, B != A), können Sie das erkennen diese Tatsache an den Optimierer, indem er den Typ von A mit dem Schlüsselwort “restrict” qualifiziert.

Dazu habe ich hier geschrieben: http://mathdev.org/node/23 und versuchte zu zeigen, dass einige eingeschränkte Zeiger tatsächlich “linear” sind (wie in diesem Beitrag erwähnt).

Es ist erwähnenswert, dass neuere Versionen von clang sind in der Lage, Code mit einer Laufzeitprüfung auf Aliasing und zwei Codepfaden zu generieren: einen für Fälle, in denen potenzielles Aliasing vorhanden ist, und den anderen für Fälle, in denen offensichtlich keine Chance besteht.

Dies hängt natürlich davon ab, welche Datenmengen dem Compiler auffällig erscheinen sollen – wie sie es im obigen Beispiel wären.

Ich glaube, die wichtigste Rechtfertigung sind Programme, die STL stark nutzen – und besonders <algorithm> wo es schwierig oder unmöglich ist, das einzuführen __restrict Qualifikation.

All dies geht natürlich zu Lasten der Codegröße, beseitigt jedoch ein großes Potenzial für obskure Fehler, die sich aus Zeigern ergeben könnten, die als deklariert sind __restrict nicht ganz so nicht überlappend, wie der Entwickler dachte.

Ich wäre überrascht, wenn GCC nicht auch diese Optimierung bekommen hätte.

Kann es sein, dass die hier durchgeführte Optimierung nicht darauf angewiesen ist, dass Zeiger nicht mit einem Alias ​​versehen werden? Wenn Sie nicht mehrere mul2-Elemente vorab laden, bevor Sie das Ergebnis in res2 schreiben, sehe ich kein Aliasing-Problem.

Im ersten Codestück, das Sie zeigen, ist ziemlich klar, welche Art von Aliase-Problem auftreten kann. Hier ist es nicht so klar.

Beim erneuten Lesen des Artikels von Dreppers sagt er nicht ausdrücklich, dass eine Beschränkung irgendetwas lösen könnte. Es gibt sogar diesen Satz:

{Theoretisch sollte das in der C-Sprache in der Revision von 1999 eingeführte Schlüsselwort “restrict” das Problem lösen. Die Compiler haben jedoch noch nicht aufgeholt. Der Grund liegt hauptsächlich darin, dass zu viel falscher Code vorhanden ist, der den Compiler in die Irre führen und dazu führen würde, dass er falschen Objektcode generiert.}

In diesem Code wurden bereits Optimierungen des Speicherzugriffs innerhalb des Algorithmus durchgeführt. Die Restoptimierung scheint in dem im Anhang präsentierten vektorisierten Code durchgeführt worden zu sein. Für den hier vorgestellten Code gibt es also keinen Unterschied, da keine Optimierung auf der Grundlage von Beschränkungen erfolgt. Jeder Zeigerzugriff ist eine Quelle für Aliasing, aber nicht jede Optimierung beruht auf Aliasing.

Da die vorzeitige Optimierung die Wurzel allen Übels ist, sollte die Verwendung des Schlüsselworts “restrict” auf den Fall beschränkt werden, in dem Sie aktiv studieren und optimieren, und nicht dort verwendet werden, wo es verwendet werden könnte.

Wenn es überhaupt einen Unterschied gibt, bewegen mm zu einem separaten DSO (so dass gcc nicht mehr alles über den aufrufenden Code wissen kann) ist der Weg, dies zu demonstrieren.

Arbeiten Sie mit 32- oder 64-Bit-Ubuntu? Wenn 32-Bit, dann müssen Sie hinzufügen -march=core2 -mfpmath=sse (oder was auch immer Ihre Prozessorarchitektur ist), sonst wird SSE nicht verwendet. Zweitens müssen Sie, um die Vektorisierung mit GCC 4.2 zu aktivieren, die hinzufügen -ftree-vectorize Option (ab 4.3 oder 4.4 ist diese standardmäßig enthalten in -O3). Es kann auch erforderlich sein, hinzuzufügen -ffast-math (oder eine andere Option, die eine entspannte Gleitkomma-Semantik bietet), damit der Compiler Gleitkomma-Operationen neu anordnen kann.

Fügen Sie außerdem die hinzu -ftree-vectorizer-verbose=1 Option, um zu sehen, ob es gelingt, die Schleife zu vektorisieren oder nicht; Das ist eine einfache Möglichkeit, die Auswirkungen des Hinzufügens des Schlüsselworts „restrict“ zu überprüfen.