A C99 restrict kulcsszó

Találós kérdés. Adott az alábbi függvény. Mi a visszatérési értéke?

int foo(int *a, int *b) {
    *a = 1;
    *b = 2;
    return *a;
}

int i;
printf("%d", foo(&i, &i));

Ha a programjainkban csak értékként definiált változók lennének, nem lehetne föltenni ezt a találós kérdést. Mert akkor minden egyes változó egy egyedi helyet jelölne a memóriában, és így mindegyik független lenne. Azonban abban a pillanatban, hogy pointereket vagy referenciákat kezdünk használni, előfordulhat az, hogy két különállónak látszó név ugyanazt a memóriaterületet, ugyanazt a változót hivatkozza. A probléma neve az angol nyelvű szakirodalomban: aliasing, és már találkoztunk vele C++-ból a másoló értékadó operátorok (copy assignment operator) megírása kapcsán. Ott is figyelnünk kellett az önértékadásra, amit arról ismertünk fel, hogy a this pointer és a paraméterként kapott referencia ugyanazt az objektumot hivatkozzák:

Vector& Vector::operator=(Vector const &rhs) {
    if (this != &rhs) {
        /* ... */
    }
    return *this;
}

Emiatt fenti találós kérdés függvényéről sem lehet teljes biztonsággal állítani, hogy 1-gyel térne vissza. A függvény lefordításakor a fordító nem ismeri az a és b pointerek értékét, ezért fel kell készülnie arra, hogy esetleg a két pointer megegyezik egymással.

Ez akkor fontos, ha sebességre optimalizálva próbáljuk lefordítani a kódot. Az aliasing lehetősége miatt rengeteg optimalizációs, gyorsítási lehetőség veszik el. Például az alábbi foo1() függvényben a *n indirekciót nem lehet kiemelni a ciklus elé (a jobb oldalon látható foo2() változat), mivel akár az is lehet, hogy az n pointer a vec[] tömb valamelyik elemére mutat, azaz *n a vec[] tömb valamelyik elemével egyezik meg. Pedig ez fontos lenne, mert iterációnként egy memóriaműveletet megspórolhatnánk:

void foo1(int vec[], int *n) {

    for (int i = 0; i != *n; ++i)
        vec[i] += 1;
}

void foo2(int vec[], int *n) {
    int t = *n;
    for (int i = 0; i != t; ++i)
        vec[i] += 1;
}

A következő programrész pedig nem gyorsítható úgy, hogy az egyes bájtokat nem egyesével, hanem négyesével vagy nyolcasával másoljuk (az erre való gépi utasítással), hiszen a két tömb átfedheti egymást:

void my_memcpy(char *dst, char const *src, size_t n) {
    for (size_t i = 0; i != n; ++i)
        dst[i] = src[i];
}

Pedig ezek mind olyan optimalizációk, amelyre a mai fordítók képesek lennének.

C++-ban még rosszabb a helyzet. Ott egy objektum tagváltozói mindig indirekt elérésűek, a this pointeren keresztül. Az alábbi tagfüggvényben a size nem lokális változó, ezért lehet, hogy a data pointeren keresztül hivatkozható. Emiatt minden egyes iterációban újra ki kell olvasni az értékét a memóriából:

class Vector {
  public:
    void clear() {
        for (int i = 0; i < size; i++)
            data[i] = 0;
    }

  private:
    int size;
    int *data;
};

Akármennyire is tűnik ez értelmetlennek nekünk, a fordító nem érti a kódot, és nem élhet azzal a feltételezéssel, hogy data!=&size teljesül!

TBAA: Type-based alias analysis

A szabvány és a fordítók írói megpróbáltak kicsit javítani ezen a helyzeten. Vannak olyan körülmények, amelyek fennállása esetén tudni lehet, hogy két pointer biztosan nem ugyanarra az objektumra mutat. Például egy int*-ról és egy double*-ról „ránézésre” is tudjuk, hogy nem kell feltételezni az egyezésüket. De a „ránézésre” nem elég, a szabályrendszert formalizálni kell, mert a fordítók csak a beléjük programozott szabályokat tudják követni.

Az előző példa azonban adhat egy ötletet. A nyelv típusait fel lehet használni arra, hogy felismerjük a különálló pointereket! Ebből kiindulva, a szabályok a következők:

1. Minden memóriaterület csak egy bizonyos típusú objektumot tárolhat, amíg annak az objektumnak az élettartama tart.
2. Két pointer akkor nevezünk kompatibilisnek, ha:
   1. Csak előjelben vagy minősítőkben (qualifier, pl. const) térnek el.
   2. Az egyikük void *, mert az bármilyen típussal kompatibilis (generikus pointer).
   3. Az egyikük char * vagy unsigned char *, mert ezt használjuk bájtonkénti memóriacímzésre.
3. Két pointerről csak akkor kell feltételezni, hogy ugyanarra az objektumra mutatnak, ha kompatibilis típusúak.

A szabályok alapján a fordítók már sok optimalizálást el tudnak végezni. Például az alábbi foo1() függvényt jogosan foo2()-ként értelmezhetik, mivel tudni lehet, hogy az int *n pointer nem mutat a float vec[] tömb semelyik elemére. Így nem kell a *n kifejezést minden iterációban kiértékelni:

/* vec[i] ugyanaz az int, mint *n? */
void foo1(float vec[], int *n) {

    for (int i = 0; i != *n; ++i)
        vec[i] += 1;
}

/* biztosan nem ugyanazok! */
void foo2(float vec[], int *n) {
    int t = *n;
    for (int i = 0; i != t; ++i)
        vec[i] += 1;
}

Azonban ez int vec[], int *n esetén még mindig nem lenne segítség.

A kompatibilis pointerekhez: restrict kulcsszó

Ha két kompatibilis pointerünk van, akkor is jelezhetjük a fordító számára, hogy biztosan nem ugyanarra az objektumra mutatnak. Ezt a restrict minősítővel tehetjük meg. A kulcsszót a pointert jelző * után kell írni, mivel a pointert minősíti, nem a mutatott objektumot:

int foo(int * restrict a, int * restrict b) {
    *a = 1;
    *b = 2;
    return *a;
}

Ha egy blokkban a restrict kulcsszóval megjelölünk egy pointert, azzal azt jelezzük a fordítónak, hogy abban a blokkban az általa mutatott objektumot csak az a pointer, vagy az abból létrehozott másolatok hivatkozzák. Így a fenti kódban például optimalizálhatja a visszatérési értéket, fixen 1-re. Ha megnézzük a generált assembly kódot, ez látszik is:

movl	$1, (%rdi)    ; *a = 1;
movl	$2, (%rsi)    ; *b = 2;
movl	(%rdi), %eax  ; (vissza) = *a;
ret                   ; visszatérés a fv-ből

movl	$1, (%rdi)    ; *a = 1;
movl	$1, %eax      ; (vissza) = 1;
movl	$2, (%rsi)    ; *b = 2;
ret                   ; visszatérés a fv-ből

Tömbök esetén nagyon sokat segíthet a restrict kulcsszó, mert lehetővé teheti a tömbelemek párhuzamos feldolgozását. A mai processzorok rengeteg ún. SIMD (single instruction, multiple data) utasítással rendelkeznek, amelyek sok adatot dolgoznak fel egyszerre, így az előny például a lenti függvényben jelentős lehet. (Itt a és b pointerek! A tömb szintaktikájú formális paraméternél így kell jelölni a restrict-et.)

/* vector a += b */
void vec_plus(int n, float a[restrict], float const b[restrict]) {
    for (int i = 0; i != n; ++i)
        a[i] += b[i];
}

Nagyon vigyázni kell arra, hogy a restrict használatával ígéretet teszünk a fordítónak a pointerek által mutatott objektumokat illetően. Ha mégis olyan értékeket adunk a pointereknek, amelyek megegyeznek, nem garantált, hogy a futtatott program helyes eredményt ad! Például:

$ cat restrict.c
#include <stdio.h>

int foo(int * restrict a, int * restrict b) {
    *a = 1;
    *b = 2;
    return *a;
}

int main() {
    int i;
    printf("%d\n", foo(&i, &i));
}

$ clang -O0 restrict.c -o restrict; ./restrict
2

$ clang -O2 restrict.c -o restrict; ./restrict
1

Látszik, hogy a -O2 optimalizálás mellett a fordító kihasználta az ígéretünket, és ezért más lett az amúgy helytelen (!) programkód futási eredménye, mint optimalizálás nélkül.

1. A C89-ben két függvénnyel lehetett adott méretű memóriaterületet másolni, ezek a memcpy() és a memmove(). Mindkettő paraméterei: cél pointer, forrás pointer, memóriaterület mérete. Mi a két függvény között a különbség? A C99-től kezdve a kettő közül vajon melyik paraméterei restrict minősítésű pointerek?

Megoldás

A memcpy()-nál elvárás volt a C89-ben is, hogy olyan tömböket adjunk paraméterként, amelyek nem fedik egymást. Így az új verzióban ennek restrict minősítésűek a paraméterei. A memmove()-nál nincs ilyen elvárás, az képes egymást átfedő memóriaterületeket is másolni.

Irodalom

1. Realistic usage of the C99 'restrict' keyword?
2. restrict – Wikipedia