Was ist die Semantik von C99s „restrict“ in Bezug auf Zeiger auf Zeiger?

Question

Ich beschäftige mich viel mit Matrixarithmetik und möchte die Vorteile von C99 nutzen restrict Zeiger-Qualifizierer.

Ich möchte meine Matrizen als Zeiger auf Zeiger einrichten, um eine einfache Subskription zu ermöglichen, etwa so:

int **A = malloc (ncols * sizeof(int *));
A[0] = malloc (nrows * ncols * sizof(int));
for (int i=1; i < ncols; i++) {
    A[i] = A[0] + i*nrows;
}

Nun zu einer Matrixmultiplikationsfunktion

void mmultiply ( int nrows, int ncols, int **Out, int **A, int **B);

Muss ich beide Zeiger der Argumente als eingeschränkt qualifizieren?Es ist eine gültige Syntax, aber es fällt mir schwer, festzustellen, ob int *restrict *restrict verhält sich anders als int **restrict.

Wenn die Zeiger dann ordnungsgemäß eingeschränkt sind, erfolgt der Zugriff auf Elemente über A[0][col*nrows + row] nicht definiert?(d. h. geht der Compiler davon aus, dass ich nur Zugriff auf die Matrix über A[col][row] für Werte von row so dass row < nrow)?Oder muss ich einfach konsequent bleiben?

Answer 1

Für die erste Frage mit „ja“, wird es etwas anderes bedeuten, wenn Sie beide restrict Qualifikations verwenden, speziell, dass die Zeiger auch nicht aliased werden. Zur Frage, ob es einen Unterschied macht: theoretisch ja, in der Praxis hängt es von den Optimierer

.

Für die zweite Frage mit „ja“, wird es, dass alles durch einen Zeilenzeiger zugegriffen übernimmt nur durch den Zeilenzeiger zugegriffen wird.

Sie könnten werfen const dort auch.

Schließlich, wenn dies gcc bei -O2, O3 oder -Os wird der Compiler bereits eine Alias-Analyse auf Typen auf Basis tun. Ich bin sicher, dass andere Compiler dies auch tun. Dies bedeutet, dass die Zeiger gegen den Ints Einschränkung bereits verstanden wird, werden nur die Felder verlassen, die möglicherweise miteinander speichern könnte.

Insgesamt wird davon ausgehen, der Optimierer, dass die Zeiger nicht in als ints gespeichert werden, und sie weiß es nicht Zeiger tut während der Schleife schreibt.

So werden Sie wahrscheinlich den gleichen Code mit bekommen nur derjenige beschränken.

Answer 2

Die äußere (zweite) beschränken weist den Compiler an, dass keine der Anordnungen von Zeigern (A, B, und out) alias. Die innere (erste) beschränken weist den Compiler an, dass keiner der Anordnungen von ints (auf die durch Elemente der Arrays von Zeigern) alias.

Wenn Sie sowohl ein Zugriff auf [0] [col * nrows + row] und A [col] [Zeile] dann sind Sie verletzen die innere beschränken, so Dinge brechen könnte.

Answer 3

int **restrict Stellt nur sicher, dass sich der von Out, A und B adressierte Speicher nicht überlappt (außer dass A und B überlappen können, vorausgesetzt, Ihre Funktion ändert keinen von beiden).Damit sind die Arrays von Zeigern gemeint.Es sagt nichts über den Inhalt des Speichers aus, auf den Out, A und B zeigen.In Fußnote 117 in n1124 heißt es:

Wenn der Identifikator P Typ (int ** eingeschränkt) hat, basieren die Zeigerausdrücke P und P+1 auf dem von P bezeichneten eingeschränkten Zeigerobjekt, aber die Zeigerausdrücke *P und P [1] sind es nicht.

In Analogie zu const, ich vermute, dass das Qualifizieren mit restrict zweimal wird behaupten, was Sie wollen, nämlich dass keiner der Werte im Array auf überlappenden Speicher verweist.Aber wenn ich den Standard lese, kann ich mir nicht selbst beweisen, dass dies tatsächlich der Fall ist.Ich gehe davon aus, dass „D sei eine Deklaration eines gewöhnlichen Bezeichners, der die Möglichkeit bietet, ein Objekt P als eingeschränkt qualifizierten Zeiger auf den Typ T zu kennzeichnen“ dies in der Tat bedeutet int *restrict *restrict A, dann sind A[0] und A[1] Objekte, die als eingeschränkt qualifizierte Zeiger auf int bezeichnet sind.Aber es ist ziemlich schweres juristisches Fachwissen.

Ich habe allerdings keine Ahnung, ob Ihr Compiler mit diesem Wissen tatsächlich etwas anfangen wird.Es ist klar, dass dies der Fall sein könnte. Es kommt darauf an, ob es umgesetzt wird.

Ich weiß also nicht wirklich, was Sie gegenüber einem herkömmlichen C-2-D-Array gewonnen haben, bei dem Sie nur zuordnen rows * cols * sizeof(int), und Index mit A[cols*row + col].Dann benötigen Sie eindeutig nur eine Verwendung von „restrict“ und einen beliebigen Compiler, der damit irgendetwas macht restrict wird in der Lage sein, Lesevorgänge von A und B über Schreibvorgänge nach Out neu zu ordnen.Ohne restrict, Natürlich ist das nicht möglich. Wenn Sie also tun, was Sie tun, überlassen Sie sich der Gnade Ihres Compilers.Wenn es die doppelte Beschränkung nicht bewältigen kann, sondern nur den Fall der einfachen Beschränkung, dann hat Sie Ihre doppelte Indirektion die Optimierung gekostet.

Auf den ersten Blick dürfte die Multiplikation ohnehin schneller sein als eine zusätzliche Zeigerindirektion.Offensichtlich ist Ihnen die Leistung wichtig, sonst würden Sie „restrict“ überhaupt nicht verwenden, daher würde ich die Leistung ziemlich sorgfältig testen (auf allen Compilern, die Ihnen wichtig sind), bevor ich diese Änderung vornehme, um eine etwas bessere Syntax zu erzielen und mir nicht merken zu müssen, wie viele Jedes Mal, wenn Sie darauf zugreifen, werden die Spalten in Ihrem Array aktualisiert.

Ist der Zugriff auf Elemente über A[0][col*nrows + row] undefiniert?

Ja, wenn das Element durch einen der Zugriffe verändert wird, denn dadurch ist A[0] ein Alias ​​für Speicher, auf den auch über A[col] zugegriffen wird.Das wäre in Ordnung, wenn nur A und B eingeschränkt qualifizierte Zeiger wären, nicht aber, wenn A[0] und A[col] es sind.

Ich gehe davon aus, dass Sie A in dieser Funktion nicht ändern, daher ist dieser Alias ​​eigentlich in Ordnung.Wenn Sie dasselbe jedoch mit Out tun würden, wäre das Verhalten undefiniert.