Ours & Hippy [ abridged edition]

Le C et ses raisons : les pointeurs restreints

restrict, où, comment ?

Hop, dans le vif du sujet ! restrict est un qualificateur de type (comme const ou volatile) ajouté en C99. Il ne s’applique qu’aux types pointeurs. Syntaxiquement, pas de problème donc… il suffit de se rappeler que les qualificateurs se placent à droite du signe * qui déclare le pointeur :

int * restrict        // pointeur restreint sur int
int * restrict *      // pointeur sur pointeur restreint sur int
int restrict *        // ILLÉGAL
int ** restrict       // pointeur restreint sur pointeur sur int

Un peu comme pour pointeur sur const, un pointeur normal peut être affecté à un pointeur déclaré restrict. Mais l’inverse est également vrai. En fait, restrict n’a pas beaucoup d’influence sur le typage à la compilation ; ses effets sont d’ordre dynamique.

Une définition intuitive

Si vous lisez la description de la norme à propos de restrict (toute une section lui est dédiée), vous vous rendrez vite compte que c’est assez indigeste. Même avec l’habitude de lire des spécifications, des références et des normes, la définition n’en demeure pas moins relativement obscure…

Mais, en essence, quelle est l’intention derrière restrict ? Il faut savoir que restrict n’est utile que dans le contexte d’optimisations du compilateur. Vous ne gagnez rien en ce qui concerne l’expressivité ; au contraire, en utilisant restrict, vous vous imposez des contraintes supplémentaires. Déclarer un pointeur comme restreint, c’est assurer au compilateur que vous avez pris soin de vérifier certaines hypothèses pour lui, qu’il pourra utiliser pour mieux optimiser votre code. Mais quelles hypothèses au juste ?

L’idée est d’avoir un unique pointeur (le pointeur restreint) vers une zone mémoire qui lui est attitrée. Tant qu’il existe (tant que l’on se trouve dans la durée de vie de la variable correspondante), aucun autre pointeur ne peut être utilisé pour accéder au même objet en mémoire… à moins d’en avoir hérité le titre. En effet, affecter un pointeur (ou le résultat d’une opération sur celui-ci) à un autre lui transfère non seulement la valeur, mais également les droits d’accès du premier.

La règle du pouce

En fait, il est très courant de supposer cette propriété sans s’en apercevoir : la plupart du temps, dans un contexte donné, on accède à chaque objet séparément, via son propre pointeur. On peut éventuellement en faire une copie, ou prendre l’adresse d’un de ses sous-éléments (p.ex. un membre d’une structure ou un élément d’un tableau), mais tout va bien, car ce faisant, on se donne le droit d’utiliser ces nouveaux pointeurs pour accéder à la même zone mémoire.

Votre compilateur est suffisamment intelligent pour comprendre que si un pointeur q prend pour valeur le résultat d’un calcul basé sur un autre pointeur p, alors q doit aussi pouvoir avoir accès aux mêmes éléments. (Et c’est garanti par la norme.)

En pratique, restrict se comporte quasiment comme nous l’avons décrit jusqu’ici, à l’exception que la norme spécifie quelques subtilités concernant l’écriture. On peut résumer son fonctionnement en deux règles pas trop compliquées. Soit p un pointeur restreint (déclaré T * restrict p), alors :

• Soit la valeur pointée par p n’est jamais modifiée durant toute la durée de vie de p, et restrict ne garantit rien de spécial dans ce cas.

• Soit la valeur pointée par p change à un moment ou un autre durant la vie de p (directement dans la fonction qui a déclaré p, ou indirectement dans une des fonctions appelée par celle-ci), et dans ce cas seulement restrict postule que tout accès à cette valeur (en lecture ou en écriture) durant la durée de vie de p doit passer par p (directement, ou indirectement via un pointeur résultant d’une opération sur p).

Dans la pratique

Des règles ci-dessus, nous pouvons déduire deux cas de figure pratiques :

• Un pointeur restreint sur un objet constant (T const * restrict) garantit que durant toute sa durée de vie, l’objet pointé n’est jamais modifié du tout. C’est une conséquence directe : si la valeur devait changer, l’écriture devrait obligatoirement se faire en passant par notre pointeur restreint ; or, celui-ci pointe sur un objet constant : impossible, donc.

• Un pointeur restreint sur un objet non constant garantit que seules les fonctions auxquelles on passe une copie ou un dérivé de ce pointeur peuvent modifier la valeur pointée. Ou de manière équivalente, que toute action qui ne touche pas à ce pointeur directement ou indirectement ne peut pas changer la valeur pointée.

Mais plus concrètement encore, qu’est-ce que cela nous interdit ? Les possibilités sont multiples, mais voici quelques pistes de réflexion :

• Dans une fonction qui prend des pointeurs restreints en arguments, écrire dans l’un ne doit pas changer la valeur lue dans l’autre.

• Appeler une fonction sans lui passer un certain pointeur restreint implique qu’elle n’a pas accès à cette adresse par d’autres moyens (p.ex. une variable globale).

Typiquement, l’usage de restrict se limite aux paramètres de fonctions ; il est possible d’utiliser le mot-clef dans d’autres contextes (p.ex. sur un membre de structure), mais la sémantique est plus complexe, et moins utile.

Une histoire d’optimisation

Plus haut, j’ai mentionné le fait que restrict trouve son utilité dans l’optimisation avant tout. Cependant, contrairement à inline, un autre ajout de C99, il n’est pas aisé pour quelqu’un qui ne fait pas de compilation ou de programmation bas niveau de comprendre l’impact que peut avoir restrict sur l’efficacité de son programme. Après tout, à quoi cela sert-il de garantir que l’on n’accède pas au même emplacement mémoire par deux pointeurs différents ?

Compilation des variables et des pointeurs, introduction accélérée

Pour comprendre pourquoi c’est utile, il faut regarder comment un compilateur typique gère les opérations sur les pointeurs. Naïvement, on pourrait penser que chaque opération comportant un accès à la mémoire via un pointeur induit une instruction pour lire la valeur à l’adresse concernée une fois traduit en langage machine. En vérité, ce n’est pas forcément le cas. Il serait plus précis de dire qu’un compilateur (typique) travaille tout d’abord avec des variables abstraites (vous pouvez voir cela comme une mémoire séparée, qui n’existe pas réellement, et qui sert au compilateur pour raisonner sur les calculs qu’on lui demande d’effectuer), qu’il est obligé de synchroniser de temps à autre avec la vraie mémoire de l’ordinateur. Un exemple :

int x;
f(&x);
/*
 * La valeur de x peut avoir changé ; il faut la relire depuis la
 * mémoire.
 */

Comme la mémoire abstraite avec laquelle travaille le compilateur n’existe que dans sa tête au moment où il compile un bout de code précis, dès lors qu’il interagit avec d’autres composants, il est obligé de matérialiser ses pensées dans la vraie mémoire, afin d’être cohérent avec ceux-ci. Il existe deux types de synchronisation, correspondant à la lecture et l’écriture :

• Si le compilateur veut que la valeur d’une variable soit lisible par un autre bout de code, il faut qu’il l’inscrive dans la mémoire.

• Inversement, s’il veut lire la valeur d’une variable qui a été écrite par un autre bout de code, il faut qu’il la charge depuis la mémoire.

Interagir avec la mémoire réelle peut être coûteux en soi, mais un problème plus important encore est que de telles opérations sont autant de contraintes supplémentaires pour le compilateur, qui l’empêchent de transformer et réarranger librement les opérations…

Mémoire abstraite et problèmes d’alias

C’est là qu’intervient la notion d’alias, directement liée à nos pointeurs restreints. Un pointeur est un alias d’un autre, à un moment donné de l’exécution, s’il pointe au même endroit.

Avoir des alias, c’est mal, du moins, ça mène la vie dure à votre compilateur. Prenons un exemple :

void
foo(int *p, int *q)
{
    /* ... */
}

Dans cette fonction foo, si nous mettons de côté l’arithmétique des pointeurs, nous nous retrouvons avec deux cas :

• p et q sont égaux ;
• ou p et q sont différents.

On a un problème d’alias. Ici, le compilateur n’est pas capable de représenter correctement dans son espace de variables abstraites les « variables » *p et *q (les objets pointés par p et q). En effet, il pourrait s’agir d’une seule variable si p et q sont égaux, ou de deux variables si les adresses sont distinctes. Il faudrait explorer les deux possibilités séparément, ce qui n’est pas faisable (si on avait n pointeurs…).

Une solution pragmatique, mais pas vraiment satisfaisante, est de considérer les accès à *p et *q comme des opérations externes, qui requièrent une synchronisation avec la vraie mémoire. En quelque sorte, on est obligé d’abandonner notre modèle dans lequel un pointeur désigne une variable pour une boîte noire capable de renvoyer ou stocker une valeur qu’on lui donne. Et tout cela parce que l’on est incapable d’identifier ladite variable pointée !

Maintenant, regardons ce qui se passe si nous déclarons nos deux pointeurs restrict :

void
foo(int * restrict p, int * restrict q)
{
    /* ... */
}

D’après les règles décrites plus haut, nous savons que selon que l’objet pointé soit modifié ou non, les propriétés changent. Néanmoins, nous pouvons toujours choisir de représenter *p et *q comme deux variables distinctes dans l’espace abstrait. En effet :

• Si durant l’exécution de foo, quelqu’un écrit dans l’emplacement associé à p ou à q, alors les règles qui gouvernent les pointeurs restreints nous garantissent que p et q pointent sur des objets différents.

• Sinon, la valeur des objets pointés ne change jamais, et nous nous retrouvons avec deux variables abstraites parfaitement égales, à tout moment ; sans conséquence pour la suite des opérations.

Un mot sur la vectorisation

Nous avons vu comment restrict permettait d’affiner notre représentation des variables pointées, ce qui permet d’être plus agressif au niveau des échanges avec la mémoire réelle.

Un autre effet positif, qui est souvent davantage médiatisé, mais qui découle essentiellement des mêmes principes, est une meilleure vectorisation du code. La vectorisation (ou auto-vectorisation) est l’optimisation par laquelle le compilateur traduit des boucles ou morceaux de boucles en instructions spécialisées qui opèrent sur des (petits) tableaux de plusieurs valeurs à la fois.

Typiquement, ces instructions se présentent comme des opérations classiques sur les scalaires, excepté qu’elles consomment et produisent des vecteurs. Une conséquence de cette description en apparence anodine est que le compilateur doit pouvoir réarranger les boucles afin de grouper plusieurs lectures et plusieurs écritures ensemble. Dans le cas où les pointeurs utilisés pour ces accès se comportent comme des boîtes noires, de telles permutations sont en général illégales, car une inscription dans la boîte noire pourrait influencer le prochain chargement depuis une autre boîte noire. Et nous retrouvons notre cher problème d’alias.

Pour illustrer cette question, regardons un dernier exemple, une fonction qui additionne deux vecteurs et place le résultat dans un troisième :

int *
vector_add(int *a, int *b, int *result, size_t n)
{
    for (size_t i = 0; i < n; ++i)
        result[i] = a[i] + b[i];
    return result;
}

Admettons que n soit un multiple de 4 et que par chance, nous disposions d’une instruction machine qui ajoute deux vecteurs de taille fixe 4 et place le résultat dans un troisième. Il faudrait modifier la boucle précédente pour traiter les données par paquets de 4, comme suit :

int *
vector_add_1(int *a, int *b, int *result, size_t n)
{
    for (size_t i = 0; i < n; i += 4) {
        int tmp[4];
        tmp[0] = a[i] + b[i];
        tmp[1] = a[i+1] + b[i+1];
        tmp[2] = a[i+2] + b[i+2];
        tmp[3] = a[i+3] + b[i+3];
        memcpy(result + i, tmp, 4 * sizeof *result);
    }
    return result;
}

La variable tmp illustre ici le fait que notre instruction vectorielle prend place entièrement avant l’écriture dans le tableau-résultat. Malheureusement, ces deux fonctions ne sont pas équivalentes dans le cas où a, ou b, et result pointent sur des parties du même vecteur !

Conclusion

Voilà qui conclut notre petit tour des pointeurs restreints. J’espère que cela aura été instructif pour certains, ou donné envie à d’autres d’essayer le mot-clef restrict ! Pour ma part, j’ai encore un peu de mal à me faire à son usage. La charge de réflexion supplémentaire pour savoir quand un pointeur doit être restreint ou non n’est pas exactement négligeable, et je ne pense pas non plus qu’il faille essayer de toute spécifier à l’aide de ce seul qualificateur, mais, comme pour const, il permet d’expliciter certaines hypothèses que je fais parfois sans m’en apercevoir, et en cela, je considère son ajout comme une bonne chose… les performances, c’est que du bonus ! ;)