# Les indices au compilateur

Les compilateurs de C++ sont généralement très forts pour optimiser le code. Cependant, ils peuvent manquer des optimisations si ils ne disposent pas assez d'informations. On va donc s'intéresser aux différentes façons de donner ces informations à notre compilateur.

Les indications utilisées en exemple proviennent de GCC, elles leurs équivalents existent pour Clang et (parfois) pour MSVC. Etant de simples indications, elles peuvent souvent être ignorées pour les compilateurs qui ne les implémentent pas. Lorsqu'on écrit du code pour plusieurs compilateurs, on regroupe généralement ces indications avec une macro commune :

```cpp
// Définition de unreachable() selon le compilateur utilisé.
// On verra plus tard ce que signifie cette macro, et à quoi elle peut servir.

// Détection de MSVC.
#if defined(_MSC_VER)
    #define unreachable() __assume(false)
    
// Détection de GCC ou Clang.
#elif defined(__GNUG__) || defined(__clang__)
    #define unreachable() __builtin_unreachable()
    
// Traitement par défaut pour les autres compilateurs.
#else
    #define unreachable() std::abort()
#endif

void do_not_call_me() {
    unreachable();
}
```

### Les attributs standards

[Le C++ permet l'utilisation d'attributs](https://www.bfilipek.com/2017/07/cpp17-in-details-attributes.html) avec la notation `[[namespace::attribut(arguments ...)]]`, où plusieurs attributs peuvent être spécifiés en une fois. Les attributs standards actuellement disponibles ne visent pour la plupart pas l'optimisation du code :

* `[[noreturn]]` indique qu'une fonction n'est jamais quitté normalement : soit parce qu'elle arrête le programme, ou lance un exception à chaque fois par exemple.
* `[[carries_dependency]]` permet d'optimiser des manipulations de variables atomiques en retirant quelques contraintes sur le compilateur, lorsque `std::memory_order_consume` est utilisé.
* `[[deprecated("message")]]` émet un warning lorsque la fonction marquée est utilisée. Le message est optionnel.
* `[[maybe_unusued]]` empêche au compilateur d'émettre un warning lorsque la fonction n'est pas utilisée.
* `[[fallthrough]]` indique que le `case` d'un `switch` laisse intentionnellement continuer l'exécution dans le prochain `case`.
* `[[nodiscrad]]` émet un warning lorsque la valeur de retour d'une fonction est ignorée.

`[[noreturn]]` permet d'optimiser le code en évitant de gérer le retour de la fonction marquée. Hormis `[[carries_dependency]]`, les autres attributs n'optimisent pas le code généré.

### Les prédictions de branches

Lors de l'exécution de code, le processeur dispose de moyens de prédire quelle branche le programme exécutera, c'est-à-dire les instructions suivant une condition (un `if`/`else`, un `while`, un `switch` ou un `for`). Cela permet au programme de ne pas attendre le résultat du test, ce qui permet au pipeline du processus de continuer à se remplir. En cas d'erreur, il doit alors rebrousser chemin.

Ces prédictions peuvent être très assez précises (notamment pour les boucles `for`), mais elles ne peuvent pas être connues à la compilation (car elles dépendent de l'exécution du programme) et ne changent donc pas le code généré.

On peut donc indiquer à GCC (qui est pris en exemple) quelle est la valeur la plus probable d'un test avec `__builtin_expect(variable, value)`, généralement placé à l'intérieur du test. Voici par exemple les macros `likely(val)` et `unlikely(val)`, qui sont définies de cette façon pour le noyau linux :

```cpp
// "!!(x)" sert à cast x en bool, ce que fait l'instruction if.
// C'est équivalent à static_cast<bool>(x).
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

// Exemple d'utilisation : pour le test d'une erreur.
User& get_user(UserId id) {
    if (unlikely(id < UserId::min || id > UserId::max))
        throw std::logic_error{"invalid user id passed"};
    
    return users[id];
}
```

{% hint style="info" %}
Les attributs `[[likely]]` et `[[unlikely]]` vont être disponibles pour C++20.       &#x20;
{% endhint %}

En connaissant la branche la plus probable à la compilation, le compilateur peut alors par exemple déplacer les instructions de la branche la plus probable devant celles des autres. Ainsi, lorsqu'on lit les instructions à exécuter, les plus courantes se suivent, ce qui va accélérer leur exécution.

### L'aliasing

Le standard indique que des références ou des pointeurs de types différents ne peuvent pas s'alias, c'est-à-dire désigner les mêmes données. Toutes les valeurs accédées depuis un pointeur ne doivent donc pas être accessibles depuis un pointeur de type différent.

Les types définis avec `using` et `typedef` ne sont pas différents du type d'origine : il s'agit juste d'un renommage. Des pointeurs ou références vers `T` et `const T` peuvent s'alias.

Les compilateurs qui implémentent ce principe (le *strict aliasing*) peuvent appliquer des optimisations supplémentaires, par exemple en évitant de lire les mêmes valeurs plusieurs fois en mémoire, ou pour appliquer plus efficacement la vectorisation. MSVC ne propose pas de *strict aliasing*.

{% hint style="danger" %}
Le *strict aliasing* demande une attention particulière au *type-punning* (qui réinterpréte des types) pour ne pas avoir de pointeurs de types différents qui s'aliasent, sous peine d'avoir un programme qui n'est pas garanti de fonctionner.

Les compilateurs qui utilisent le *strict aliasing* peuvent le désactiver, par exemple GCC avec `-fno-strict-aliasing`.
{% endhint %}

Le mot-clé `restrict` en C, disponible avec `__restrict` en C++ pour de nombreux compilateurs indique qu'un pointeur ou une référence n'alias pas les autres pointeurs ou références de même type. Par exemple, `memcpy` prend des pointeurs qui ne doivent pas s'alias, contrairement à `memmove`. En C++, `__restrict` peut également s'appliquer à `this`, pour indiquer que les données pointées par `this` n'alias pas les arguments de la fonction.

```cpp
struct Vec2 {
    int data[2];
    bool normalized;
    
    // this est implicitement un pointeur vers (entre autres) des ints.
    // Il peut donc alias l'int référencé par v :
    // Le processeur va donc devoir relire v après avoir modifié data[0], au cas où
    // v désignait justement data[0].
    void add1(int const& v) {
        data[0] += v;
        data[1] += v;
        // Pseudo-assembleur :
        // read v
        // data[0] = v
        // read v
        // data[1] = v
    };
    
    // En indiquant que this n'alias pas d'autres données du même type, v peut être
    // lu une seule fois. __restrict aurait aussi pu être placé sur la référence en
    // écrivant int const& __restrict v, ou sur les deux à la fois.
    void add2(int const& v) __restrict {
        data[0] += v;
        data[1] += v;
        // Pseudo-assembleur :
        // read v
        // data[0] = v
        // data[1] = v
    };
};
```

Pour l'exemple ci-dessus, le gain est important puisqu'on retire une instruction et on retire une dépendance : le pipeline du processeur peut assigner `data[0]` et `data[1]` en même temps dans le second cas, alors que les instructions du premier cas se font l'une après l'autre.

### Attributs et autres indications

Les compilateurs permettent d'ajouter des attributs à des symboles, avec par exemple `__attribute__((xxx))` pour GCC et Clang ou `__declspec(xxx)` pour MSVC. GCC et Clang supportent l'écriture des attributs avec la syntaxe `[[gnu::xxx]]`.

Les attributs `noinline` et `always_inline` indiquent au compilateur de ne pas inline une fonction (toujours possible) ou de toujours essayer d'inline une fonction (parfois impossible, si on souhaite désactiver les inlines de fonction pour débug ou pour certaines fonctions récursives).

Les attributs `hot` et `cold` vont ranger ensemble les fonctions marquées. Cela permet d'optimiser les accès mémoire lors de la lecture des instructions utilisées souvent (marquées hot).

Pour GCC, des attributs peuvent également permettre d'activer ou de désactiver manuellement des optimisations. Bien d'autres attributs existent, ne serait-ce que pour les fonctions ([ici pour GCC](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html)).

Il existe d'autres indications communes, qui ne sont pas implémentées par le standard C++ :

La macro `unreachable()` créé au début de ce chapitre indique que le processeur n'atteindra jamais cet endroit. Cela peut optimiser le code de manière semblable à `[[noreturn]]` et clarifier le programme pour ses lecteurs, en évitant de renvoyer une valeur inutile pour éviter un warning ou une erreur :

```cpp
float get_ratio(int type) {
    switch (type) {
        case 0:  return 1.f;
        case 1:  return 0.72f;
        case 2:  return 1.76f;
        // On évite de renvoyer une valeur comme '-1.f' et le branchement est éliminé.
        // Cela peut permettre de supprimer un test (if type > 1 return 1.76f).
        default: unreachable();
    }
}
```

La fonction `__assume(x)` sur MSVC indique au compilateur que l'expression `x` sera toujours évaluée à vraie (tant que ses dépendances ne sont pas modifiées). Cela permet de passer des informations au compilateur pour obtenir plus d'optimisations. Récemment, Clang a implémenté `__builtin_assume(x)`. Pour GCC, l'information peut être donné indirectement avec `if (!x) unreachable();`.

Bien d'autres instructions existent. Les extensions peuvent être aussi intéressantes : pour GCC, on a par exemple [les concepts](https://gcc.gnu.org/onlinedocs/gcc/C_002b_002b-Concepts.html#C_002b_002b-Concepts) ou le type [\_\_int128](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html).

Ces indications ne vont pas apporter de gros gains de performances (à part parfois `__restrict`), mais peuvent aider à optimiser une partie critique. De plus, elles peuvent souvent aider lors de la lecture du code (comme pour `unreachable()`).

Pour ce genre d'optimisations, il peut être intéressant de voir ce qui se passe au niveau de l'assembleur, ce qui peut se faire facilement avec des outils comme [Compiler Explorer](https://godbolt.org/). Cela permet de mieux comprendre ce que fait le processeur, et de s'assurer qu'on ne manque pas une optimisation qu'on pense avoir fait.

### Pour aller plus loin

[Les prédictions de branches se sont beaucoup développées](https://danluu.com/branch-prediction/) afin de d'augmenter les performances des processeurs : l'article linké explique leur fonctionnement.

Lors du préprocesseur, [des noms d'include ou des macros peuvent être testés](http://en.cppreference.com/w/cpp/experimental/feature_test) pour savoir quelles fonctionnalités sont disponibles. Cela peut permettre d'optimiser le code selon celles disponibles et de fournir des alternatives pour celles manquantes.

`[[no_unique_address]]` en C++20 permet d'avoir des objets qui ne prennent aucune place en mémoire : actuellement, même un objet vide doit au moins prendre un octet (notamment pour qu'il dispose de sa propre adresse).
