Le code et ses raisons
  1. Conventions : le retour
  2. Le code et ses raisons : goto en C
  3. Le code et ses raisons : typedef en C
  4. Pourquoi le C est moins puissant que votre langage favori
  5. Préprocesseur C : récursivité ou imbrication ?
  6. Le C et ses raisons : les pointeurs restreints
  7. Le C et ses raisons : assertions ou programmation défensive ?

Le C et ses raisons : les pointeurs restreints

(Nhat Minh Lê (rz0) @ 2012-05-29 17:21:51)

Après un an et demi de pause, le Code et ses raisons revient ! Dans ce nouvel épisode, je vais vous parler des pointeurs restreints, introduits en C99 avec le mot-clef restrict. C’est une question qui revient souvent parmi les enthousiastes qui découvrent le C99… Les explications sur Internet (merci Google) ne manquent pas, mais comme on m’a posé la question plusieurs fois, je me suis dit que j’allais rédiger ma propre réponse une bonne fois pour toute dans un petit billet !

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 :

Dans la pratique

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

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

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 :

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 :

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 !

Je ne vais pas le détailler, mais si on ajoute l’arithmétique des pointeurs, on se retrouve avec trois options :

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 :

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 ! ;)