Zasady korzystania z słowa kluczowego restrict w języku C?

Question

Próbuję zrozumieć, kiedy i kiedy nie używać słowa kluczowego restrict w C i w jakich sytuacjach zapewnia on wymierną korzyść.

Po przeczytaniu "Demystifying The Restrict Keyword" (co zapewnia pewne zasady dotyczące użycia), mam wrażenie, że gdy funkcja jest przekazywana wskaźniki, musi uwzględnić możliwość, że wskazane dane mogą się nakładać (alias) z dowolnymi innymi argumentami przekazywanymi do funkcji. Biorąc pod uwagę funkcję:

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]; 
    } 
} 

kompilator musi przeładować c w drugiej wypowiedzi, bo może b i c punktu do tej samej lokalizacji. Musi również czekać, aż b zostanie zapisany, zanim będzie mógł załadować a z tego samego powodu. Musi wówczas czekać na zapisanie a i musi ponownie załadować b i c na początku następnej pętli. Jeśli wywołasz funkcję podobną do tej:

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

to możesz zobaczyć, dlaczego kompilator musi to zrobić. Korzystanie z restrict skutecznie informuje kompilator, że nigdy tego nie zrobisz, dzięki czemu może zrzucić zbędne obciążenie z c i załadować a, zanim zostanie zapisane .

In a different SO post, Nils Pipenbrinck, provides a working example of this scenario demonstrating the performance benefit.

Tak dalece zostały zebrane, że jest to dobry pomysł, aby użyć restrict na wskaźniki przekazać do funkcji, które nie zostanie włączonych. Wygląda na to, że jeśli kod jest wstawiony, kompilator może zorientować się, że wskaźniki się nie pokrywają.

Teraz zaczynają się robić dla mnie niewyraźne rzeczy.

W artykule Ulricha Drepper za „What every programmer should know about memory” On sprawia, że ​​stwierdzenie, że „o ile nie ograniczają stosuje się wszystkie dostępy wskaźnika są potencjalnymi źródłami aliasing”, a on daje konkretny przykład kodu matrycy podmatrycy pomnożyć gdzie używa restrict.

Jednak, gdy skompiluję jego przykładowy kod z lub bez restrict, otrzymuję identyczne binarki w obu przypadkach. Używam gcc version 4.2.4 (Ubuntu 4.2.4-1ubuntu4)

Rzecz nie mogę dowiedzieć się, w poniższym kodzie jest, czy to musi być zapisane do szerszego stosowania restrict, lub jeśli analiza alias w GCC jest tak dobre, że jest w stanie aby dowiedzieć się, że żaden z argumentów nie jest aliasami nawzajem. Dla celów czysto edukacyjnych, w jaki sposób mogę dokonać użycia lub nie używając sprawy restrict w tym kodzie - i dlaczego?

Dla restrict skompilowany z:

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

Wystarczy usunąć -DUSE_RESTRICT nie używać 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; 
} 

Answer 1

Może być dokonana optymalizacja tutaj nie polegać na wskaźnikach nie są wygaszane? Jeśli nie wczytasz wielu elementów mul2 przed zapisaniem wyniku w res2, nie widzę problemu z aliasingiem.

W pierwszym przedstawionym kodzie jest całkiem jasne, jaki rodzaj problemu może wystąpić. Tutaj nie jest to takie jasne.

Dereperujący artykuł w Dreppers, nie mówi konkretnie, że ograniczenie może rozwiązać cokolwiek. Istnieje nawet ta fraza:

{Teoretycznie ograniczać słowa kluczowego wprowadzony do języka C w rewizji 1999 powinno rozwiązać problem . Jednak kompilatory jeszcze nie złapały się na . Powodem jest przede wszystkim, że zbytnio niepoprawny kod istnieje których by wprowadzić w błąd kompilatora i spowodować to generować nieprawidłowy kod wynikowy.}

W tym kodzie, optymalizacja dostępu pamięci zostało już zrobione w algorytmie. Optymalizacja rezydualna wydaje się być wykonana w wektoryzowanym kodzie przedstawionym w appendice. Tak więc dla kodu przedstawionego tutaj, myślę, że nie ma różnicy, ponieważ nie jest dokonywana optymalizacja polegająca na ograniczeniu. Każdy dostęp do wskaźnika jest źródłem aliasingu, ale nie każda optymalizacja polega na aliasingu.

Przedwczesna optymalizacja jest źródłem wszelkiego zła, użycie ograniczającego słowa kluczowego powinno być ograniczone do przypadku, w którym aktywnie się uczysz i optymalizujesz, a nie używasz go w dowolnym miejscu.

Answer 2

Jest to wskazówka dla optymalizatora kodu. Użycie polecenia restrict powoduje, że może on przechowywać zmienną wskaźnika w rejestrze procesora i nie musi przepłukiwać aktualizacji wartości wskaźnika do pamięci, aby również alias był aktualizowany.

To, czy korzysta z niego, czy nie, zależy w dużej mierze od szczegółów implementacji optymalizatora i procesora. Optymalizatory kodu już teraz są silnie inwestowane w wykrywanie nie-aliasingu, ponieważ jest to tak ważna optymalizacja. Nie powinno być problemu z wykryciem tego w twoim kodzie.

Answer 3

Czy używasz 32- lub 64-bitowego Ubuntu? Jeśli jest to 32-bit, to musisz dodać -march=core2 -mfpmath=sse (lub inną dowolną architekturę procesora), w przeciwnym razie nie będzie używać SSE. Po drugie, w celu umożliwienia wektoryzacji za pomocą GCC 4.2, należy dodać opcję -ftree-vectorize (zgodnie z 4.3 lub 4.4 jest to domyślnie włączone w -O3). Może być również konieczne dodanie -ffast-math (lub innej opcji zapewniającej swobodę semantyki zmiennoprzecinkowej), aby umożliwić kompilatorowi zmianę kolejności operacji zmiennoprzecinkowych.

Dodać również opcję -ftree-vectorizer-verbose=1, aby sprawdzić, czy jest w stanie wektoryzować pętlę, czy nie; to prosty sposób sprawdzenia efektu dodania słowa kluczowego restrict.

Answer 4

Ponadto w GCC 4.0.0-4.4 występuje błąd regresji, który powoduje ignorowanie słowa kluczowego restrict. Ten błąd został zgłoszony jako naprawiony w wersji 4.5 (mimo to straciłem numer błędu).

Answer 5

Jeśli jest jakakolwiek różnica, przeniesienie mm do oddzielnego DSO (tak, że gcc nie będzie już wiedział wszystkiego o kodzie wywołującym) będzie sposobem na zademonstrowanie tego.

Answer 6

(Nie wiem, czy użycie tego słowa kluczowego daje istotną korzyść, to jest naprawdę bardzo łatwe dla programisty, aby popełnić błąd z tym kwalifikatorem, ponieważ nie ma wymuszania, więc optymalizator nie może być pewien, że programista nie "kłamstwo".)

Gdy wiesz, że wskaźnik A jest jedynym wskaźnikiem do jakiegoś regionu pamięci, to znaczy, że nie ma aliasów (to znaczy, każdy inny wskaźnik B będzie koniecznie niejednoznaczny dla A, B! = A), możesz powiedzieć ten fakt optymalizatorowi, określając typ A słowem kluczowym "restrict".

Pisałem o tym tutaj: http://mathdev.org/node/23 i próbowałem pokazać, że niektóre ograniczone wskaźniki są w rzeczywistości "liniowe" (jak wspomniano w tym poście).

Answer 7

Warto zauważyć, że ostatnie wersje clang są w stanie generować kod z sprawdzaniem czasu wykonywania dla aliasingu oraz dwie ścieżki kodu: jedną dla przypadków, w których istnieje aliasing, a drugą dla przypadku, w którym jest oczywiste, że istnieje nie ma szansy.

To oczywiście zależy od zakresu danych wskazanych jako widoczne dla kompilatora - tak jak w powyższym przykładzie.

Uważam, że podstawowe uzasadnienie dotyczy programów intensywnie wykorzystujących STL - a szczególnie <algorithm>, gdzie jest trudne lub niemożliwe wprowadzenie kwalifikatora __restrict.

Oczywiście wszystko to odbywa się kosztem rozmiaru kodu, ale usuwa wiele potencjalnych błędów, które mogłyby spowodować, że wskaźniki zadeklarowane jako __restrict nie były tak niezupełnie zachodzące, jak myślał programista.

Byłbym zaskoczony, gdyby GCC również nie miało tej optymalizacji.

Answer 8

Problem z przykładowym kodem polega na tym, że kompilator po prostu wstawi połączenie i zobaczy, że w twoim przykładzie nie ma żadnego aliasingu. Proponuję usunąć funkcję main() i skompilować ją przy pomocy -c.