wake-up-neo.net

Regeln für die Verwendung des einschränkenden Schlüsselworts in C?

Ich versuche zu verstehen, wann und wann nicht das Schlüsselwort restrict in C verwendet wird und in welchen Situationen es einen greifbaren Vorteil bietet.

Nach dem Lesen von " Demystifying The Restrict Keyword " (das einige Faustregeln bei der Verwendung enthält) habe ich den Eindruck, dass eine Funktion, die Zeiger übergeben wird, die Möglichkeit berücksichtigen muss, auf die die Daten möglicherweise verweisen Überlappen (Alias) mit anderen Argumenten, die an die Funktion übergeben werden. 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 c im zweiten Ausdruck neu laden, da b und c möglicherweise auf dieselbe Position verweisen. Es muss auch warten, bis b gespeichert ist, bevor a aus demselben Grund geladen werden kann. Es muss dann auf die Speicherung von a gewartet werden und muss b und c am Anfang der nächsten Schleife neu laden. 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. Durch die Verwendung von restrict wird dem Compiler effektiv mitgeteilt, dass Sie dies niemals tun werden, so dass er die redundante Last von c löschen und a laden kann, bevor b gespeichert wird.

In einem anderen SO - Beitrag liefert Nils Pipenbrinck ein Arbeitsbeispiel dieses Szenarios, das den Leistungsvorteil demonstriert.

Bisher habe ich festgestellt, dass es eine gute Idee ist, restrict für Zeiger zu verwenden, die Sie in Funktionen übergeben, die nicht inline sind. Wenn der Code eingebettet ist, kann der Compiler feststellen, dass sich die Zeiger nicht überlappen.

Jetzt fangen die Dinge für mich an zu verschwimmen. 

In der Arbeit von Ulrich Drepper " Was jeder Programmierer über Speicher wissen sollte " sagt er, dass "wenn nicht alle Beschränkungen verwendet werden, alle Zeigerzugriffe potentielle Quellen für Aliasing sind" und er gibt ein spezifisches Codebeispiel einer Submatrix Matrix multiplizieren, wo er restrict verwendet. 

Wenn ich jedoch seinen Beispielcode entweder mit oder ohne restrict kompiliere, bekomme ich 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 neu geschrieben werden muss, um restrict ausführlicher zu verwenden, oder ob die Aliasanalyse in GCC einfach so gut ist, dass sie in der Lage ist, herauszufinden, dass keines der Argumentaliasnamen vorliegt gegenseitig. Wie kann ich die Verwendung von restrict in diesem Code zu rein pädagogischen Zwecken machen - und warum?

Für restrict kompiliert mit:

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

Entfernen Sie einfach -DUSE_RESTRICT, um restrict nicht zu verwenden.

#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;
}
67

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

14

Es ist ein Hinweis an den Code-Optimierer. Durch die Verwendung von Einschränkungen wird sichergestellt, dass eine Zeigervariable in einem CPU-Register gespeichert werden kann und keine Aktualisierung des Zeigerwerts in den Speicher geschrieben werden muss, damit auch ein Alias ​​aktualisiert wird.

Ob sie dies ausnutzt oder nicht, hängt stark von den Implementierungsdetails des Optimierers und der CPU ab. Code-Optimierer sind bereits stark in die Erkennung von Nicht-Aliasing investiert, da dies eine so wichtige Optimierung darstellt. Es sollte keine Probleme haben, das in Ihrem Code zu erkennen.

13
Hans Passant

(Ich weiß nicht, ob Sie mit diesem Schlüsselwort einen erheblichen Vorteil erzielen. Es ist für Programmierer sehr leicht, sich mit diesem Qualifikationsmerkmal zu irren, da keine Durchsetzung vorliegt. Daher kann ein Optimierer nicht sicher sein, 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 Aliasnamen (dh, jeder andere Zeiger B ist notwendigerweise ungleich A, B! = A), können Sie feststellen diese Tatsache an den Optimierer durch Qualifizieren des A-Typs mit dem Schlüsselwort "einschränken".

Ich habe hier darüber geschrieben: http://mathdev.org/node/23 und habe gezeigt, dass einige eingeschränkte Zeiger tatsächlich "linear" sind (wie in diesem Beitrag erwähnt).

3

Es ist erwähnenswert, dass neuere Versionen von clang in der Lage sind, Code mit einer Laufzeitüberprüfung auf Aliasing und zwei Codepfaden zu generieren: einer für Fälle, bei denen potenzielles Aliasing vorliegt, und der andere für Fälle, bei denen offensichtlich ist, dass keine Chance besteht . 

Dies hängt eindeutig von den Datenmengen ab, die für den Compiler auffällig sind - wie im obigen Beispiel. 

Ich glaube, die Hauptbegründung ist für Programme, die häufig STL verwenden - und insbesondere <algorithm>, wo es schwierig oder unmöglich ist, den __restrict-Qualifier einzuführen. 

Natürlich geht dies alles auf Kosten der Codegröße, beseitigt jedoch ein großes Potenzial für verdeckte Fehler, die dazu führen könnten, dass Zeiger, die als __restrict deklariert wurden, nicht so überlappend sind, wie der Entwickler dachte. 

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

2
marko

Kann die Optimierung hier nicht von Zeigern abhängen, die nicht verfälscht werden? Wenn Sie nicht mehrere mul2-Elemente vor dem Schreiben des Ergebnisses in res2 vorladen, sehe ich kein Aliasing-Problem.

In dem ersten Code, den Sie zeigen, ist es ziemlich klar, welche Art von Alias-Problemen auftreten kann ... Hier ist es nicht so klar. 

Er liest Dreppers Artikel noch einmal und sagt nicht ausdrücklich, dass Einschränkungen etwas lösen könnten. Es gibt sogar diesen Satz:

{Theoretisch das Einschränkungsschlüsselwort eingeführt in die C-Sprache in der Die Revision von 1999 sollte das .__ lösen. Problem. Compiler haben nicht aufgeholt aber trotzdem. Der Grund ist hauptsächlich das Es ist zu viel falscher Code vorhanden, der würde den Compiler irreführen und verursachen es erzeugt einen falschen Objektcode.}

In diesem Code wurden Optimierungen des Speicherzugriffs bereits innerhalb des Algorithmus vorgenommen. Die Restoptimierung scheint in dem in Anhang enthaltenen vektorisierten Code zu erfolgen. Für den hier vorgestellten Code gibt es also keinen Unterschied, da keine Optimierung auf Restriktionen basiert. Jeder Zeigerzugriff ist eine Quelle für Aliasing, aber nicht jede Optimierung erfordert Aliasing.

Da die vorzeitige Optimierung die Wurzel allen Übels ist, sollte die Verwendung des Einschränkungs-Schlüsselworts auf den Fall beschränkt sein, dass Sie aktiv studieren und optimieren, und nicht dort, wo sie verwendet werden kann.

1
shodanex

Wenn es überhaupt einen Unterschied gibt, können Sie mm in ein separates DSO verschieben (so dass gcc nicht mehr alles über den aufrufenden Code wissen kann).

1
Logan Capaldo

Das Problem mit Ihrem Beispielcode besteht darin, dass der Compiler den Aufruf nur einfügt und feststellt, dass in Ihrem Beispiel kein Aliasing möglich ist. Ich schlage vor, dass Sie die main () - Funktion entfernen und sie mit -c kompilieren.

0
Kurt Roeckx

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

Fügen Sie außerdem die Option -ftree-vectorizer-verbose=1 hinzu, um zu sehen, ob die Schleife vektorisiert werden kann oder nicht. Dies ist eine einfache Möglichkeit, um die Auswirkungen des Hinzufügens des Einschränkungs-Keywords zu überprüfen.

0
janneb