Ik probeer te begrijpen wanneer en wanneer ik het sleutelwoord restrictin C niet moet gebruiken en in welke situaties dit een tastbaar voordeel oplevert.
Na het lezen, “Demystifying the Restrict Keyword“, ( die enkele vuistregels biedt voor gebruik), krijg ik de indruk dat wanneer een functie wordt doorgegeven aanwijzers, deze rekening moet houden met de mogelijkheid dat de gegevens waarnaar wordt verwezen overlappen (alias) met andere argumenten die overgegaan in de functie. Gegeven een functie:
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];
}
}
de compiler moet copnieuw laden in de tweede expressie, omdat ben cmisschien naar dezelfde locatie verwijzen. Om dezelfde reden moet het ook wachten tot bis opgeslagen voordat het akan laden. Het moet dan wachten tot ais opgeslagen en moet ben copnieuw laden aan het begin van de volgende lus. Als je de functie als volgt aanroept:
int a[N];
foo(a, a, a, N);
dan kun je zien waarom de compiler dit moet doen. Het gebruik van restrictvertelt de compiler effectief dat je dit nooit zult doen, zodat het de redundante belasting van ckan laten vallen en avóór bwordt opgeslagen.
Tot nu toe heb ik begrepen dat het een goed idee is om restrictte gebruiken voor pointers die je doorgeeft aan functies die niet inline zijn. Als de code inline is, kan de compiler er blijkbaar achter komen dat de pointers elkaar niet overlappen.
Hier begint het voor mij wazig te worden.
In het artikel van Ulrich Drepper, “Wat elke programmeur zou moeten weten over geheugen“, legt hij de verklaring af dat, “tenzij restrict wordt gebruikt, alle aanwijzertoegangen potentiële bronnen van aliasing zijn”, en hij geeft een specifiek codevoorbeeld van een submatrixmatrix vermenigvuldiging waarbij hij restrictgebruikt.
Als ik zijn voorbeeldcode echter compileer, met of zonder restrict, krijg ik in beide gevallen identieke binaire bestanden. Ik gebruik gcc version 4.2.4 (Ubuntu 4.2.4-1ubuntu4)
Wat ik in de volgende code niet kan achterhalen, is of deze moet worden herschreven om uitgebreider gebruik te maken van restrict, of dat de alias-analyse in GCC zo goed is dat het in staat om erachter te komen dat geen van de argumenten elkaar aliassen. Hoe kan ik voor puur educatieve doeleinden het gebruik van restrictbelangrijk maken in deze code – en waarom?
Voor restrictgecompileerd met:
gcc -DCLS=$(getconf LEVEL1_DCACHE_LINESIZE) -DUSE_RESTRICT -Wextra -std=c99 -O3 matrixMul.c -o matrixMul
Verwijder gewoon -DUSE_RESTRICTom restrictniet te gebruiken.
#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;
}
Antwoord 1, autoriteit 100%
Het is een hint voor de code-optimizer. Het gebruik van restrict zorgt ervoor dat het een pointervariabele in een CPU-register kan opslaan en niet een update van de pointerwaarde naar het geheugen hoeft te spoelen, zodat ook een alias wordt bijgewerkt.
Of het er wel of niet gebruik van maakt, hangt sterk af van de implementatiedetails van de optimizer en de CPU. Code-optimizers zijn al zwaar geïnvesteerd in het detecteren van niet-aliasing, omdat het zo’n belangrijke optimalisatie is. Het zou geen problemen moeten hebben om dat in je code te detecteren.
Antwoord 2, autoriteit 100%
Bovendien bevat GCC 4.0.0-4.4 een regressiebug die ervoor zorgt dat het trefwoord restrict wordt genegeerd. Deze bug werd gemeld als opgelost in 4.5 (ik ben het bugnummer echter kwijt).
Antwoord 3, autoriteit 20%
(Ik weet niet of het gebruik van dit trefwoord u een aanzienlijk voordeel geeft. Het is heel gemakkelijk voor programmeurs om fouten te maken met deze kwalificatie omdat er geen handhaving is, dus een optimizer kan er niet zeker van zijn dat de programmeur dat niet doet ” liegen”.)
Als je weet dat een aanwijzer A de enige aanwijzer is naar een bepaald geheugengebied, dat wil zeggen dat deze geen aliassen heeft (dat wil zeggen, elke andere aanwijzer B zal noodzakelijkerwijs ongelijk zijn aan A, B!= A), u kunt dit feit aan de optimizer vertellen door het type A te kwalificeren met het trefwoord “restrict”.
Ik heb hier over geschreven: http://mathdev.org/node/23en geprobeerd om aan te tonen dat sommige beperkte verwijzingen in feite “lineair” zijn (zoals vermeld in dat bericht).
Antwoord 4, autoriteit 20%
Het is vermeldenswaard dat recente versies van clangin staat zijn om code te genereren met een runtime-controle voor aliasing en twee codepaden: één voor gevallen waarin er mogelijke aliasing is en de andere voor geval waar het duidelijk is, is er geen kans op.
Dit hangt duidelijk af van de omvang van de gegevens waarvan wordt aangegeven dat ze opvallen voor de compiler – zoals in het bovenstaande voorbeeld.
Ik geloof dat de voornaamste rechtvaardiging is voor programma’s die intensief gebruik maken van STL – en in het bijzonder <algorithm>, waar het moeilijk of onmogelijk is om de kwalificatie __restrictin te voeren.
Natuurlijk gaat dit allemaal ten koste van de codegrootte, maar het verwijdert een groot deel van het potentieel voor obscure bugs die ertoe kunnen leiden dat pointers die zijn gedeclareerd als __restrictniet zo niet-overlappend zijn als dacht de ontwikkelaar.
Het zou me verbazen als GCC deze optimalisatie niet ook had gekregen.
Antwoord 5, autoriteit 7%
Misschien is de optimalisatie die hier wordt gedaan, niet afhankelijk van verwijzingen die geen alias hebben? Tenzij u meerdere mul2-elementen vooraf laadt voordat u het resultaat in res2 schrijft, zie ik geen probleem met aliasing.
In het eerste stuk code dat je laat zien, is het vrij duidelijk wat voor soort aliassenprobleem kan optreden.
Hier is het niet zo duidelijk.
Als hij het artikel van Dreppers herleest, zegt hij niet specifiek dat restrict iets zou kunnen oplossen. Er is zelfs deze zin:
{In theorie het restrict-zoekwoord
geïntroduceerd in de C-taal in de
De herziening van 1999 zou het probleem moeten oplossen
probleem. Compilers hebben het niet ingehaald
toch maar toch. De reden is vooral dat
er is te veel onjuiste code die
zou de compiler misleiden en veroorzaken
het om onjuiste objectcode te genereren.}
In deze code is optimalisaties van geheugentoegang al uitgevoerd in het algoritme. De resterende optimalisatie lijkt te zijn gedaan in de vector die in aanhangsel wordt gepresenteerd. Dus voor de hier gepresenteerde code denk ik dat er geen verschil is, omdat er geen optimalisatie afhankelijk is van beperken. Elke wijzertoegang is een bron van aliasing, maar niet elke optimalisatie is afhankelijk van aliassing.
Voortijdige optimalisatie is de wortel van alle kwaad, het gebruik van het beperkende sleutelwoord moet worden beperkt tot het geval dat uw actief studeren en optimaliseren, niet gebruikt waar het maar kan worden gebruikt.
6
Het probleem met uw voorbeeldcode is dat de compiler gewoon de oproep zal inlijnen en zien dat er in uw voorbeeld geen aliasing is. Ik stel voor dat u de MAIN () -functie verwijdert en het compileert met -C.