Les accès mémoire

De nos jours, les accès mémoire sont très lents par rapport à la vitesse d'exécution des processeurs. Les accès mémoire peuvent donc être une cause majeure de ralentissement.

Lorsque de la mémoire est accédée, elle est chargée en cache par blocs de 64 octets (sur la plupart des architectures) : il s'agit des cache lines. Cela permet d'éviter de devoir souvent lire la RAM car on a tendance à accéder aux valeurs proches en même temps. Cependant, cela signifie également que si le reste de la cache line n'est pas utilisé, on gâche de la place dans le cache.

On souhaitons donc stocker les objets utilisés en même temps côte-à-côte afin de maximiser l'utilisation des cache lines obtenues : on parle de cache locality.

De plus, le matériel peut prévoir quelles données peuvent être chargées à l'avance : on parle de prefetch. Cela arrive lorsqu'on parcours des données dans l'ordre en mémoire (par ordre montant ou descendant). Itérer sur des tableaux procure donc les accès mémoire les plus rapides possibles, alors qu'itérer sur une liste chaînée peut coûter très cher.

Les variables statiques, et les instructions du code sont allouées statiquement (à la compilation du programme). En C++, nous pouvons choisir où allouer dynamiquement la mémoire (c'est-à-dire pendant l'exécution du programme). Nous avons deux espaces disponibles : la pile (stack) et le tas (heap).

La pile

Il s'agit de l'espace mémoire où sont allouées les variables locales, et où sont passés les paramètres des fonctions. La déallocation des objets est automatique et doit s'effectuer dans le sens inverse de l'allocation des objets (Last-In First-Out, LIFO).

La pile a une taille fixée à l'exécution du programme (de l'ordre de quelques méga-octets), qui peut être spécifiée selon le compilateur et le système d'exploitation utilisé. Chaque thread dispose de sa propre pile.

Comme les variables locales sont souvent utilisées et que les données sont continues en mémoire, la mémoire de la pile est très rapide d'accès : en effet, il s'agit de mémoire souvent réutilisée donc souvent en cache, et les données continues remplissent les cache lines.

De plus, l'allocation est très rapide sur la pile, puisqu'il suffit d'incrémenter le pointeur de pile. Cela peut être fait explicitement avec alloca(nbOctets) :

struct Vec3 { float x, y, z; };

int main() {
    // Variable sur la pile 'classique'
    {
        // Allocation automatique
        // Constructeur
        Vec3 vec{};
        // Destructeur automatique
        // Deallocation automatique
    }
    // Variable sur la pile, avec alloca :
    {
        // Allocation
        auto pVec = static_cast<Vec3*>(alloca(sizeof(Vec3)));
        // Constructeur (sans allouer de mémoire avec un 'placement new')
        new (pVec) Vec3();
        // Destructeur
        pVec->~Vec3();
        // Deallocation automatique
    }
}

On cherche donc à utiliser au maximum la pile, pour profiter des destructeurs et déallocations automatiques, pour avoir des allocations quasi-instantannées et accéder à des données continues en mémoire. Les grosses allocations font office d'exception à cause de la taille limitée de la pile.

Le tas

Il s'agit d'un espace de mémoire partagé par les threads, plus grand que la pile. Il ne donne pas d'ordre pour allouer ou libérer de la mémoire : on n'est pas contraint par l'ordre LIFO comme sur la pile.

Ces allocations sont effectuées par exemple avec malloc ou new. Elles sont relativement lentes, allouent de la mémoire qui a peu de chances d'être déjà en cache et fragmentent le tas (ce qui nous empêche d'utiliser toute la mémoire disponible).

On cherche donc à limiter le nombre de ces allocations.

Exemple d'allocations sur le tas : le second exemple montre l'interface utilisée pour manipuler les allocateurs implémentant le concept d'allocateur de la librairie standard.

 // Variable sur le tas, avec new :
 {
     // Allocation + constructeur
     auto pVec = new Vec3();
     // Destructeur + deallocation
     delete pVec;
 }
 // Variable sur le tas, avec std::allocator :
 // Les autres allocateurs sont utilisés de la même façon.
 {
     // Le type de l'allocateur, et son interface d'utilisation.
     // using ne fait que créer des alias.
     using alloc_t = std::allocator<Vec3>;
     using traits_t = std::allocator_traits<alloc_t>;
     
     // L'allocateur (vide pour std::allocator, car il ne fait qu'appeler malloc).
     auto allocator = alloc_t{};
     // Allocation
     auto pVec = traits_t::allocate(allocator, 1);
     // Constructeur
     traits_t::construct(allocator, pVec);
     // Destructeur
     traits_t::destroy(allocator, pVec);
     // Deallocation
     traits_t::deallocate(allocator, pVec, 1);
 }

Les allocateurs

Les allocations générales comme new ou malloc sont très polyvalentes : elles peuvent être appelées depuis plusieurs threads à la fois, pour n'importe quel taille (tant qu'elle est disponible en mémoire) et ne posent pas de contraintes quant à l'ordre d'allocation et de libération (contrairement à la pile par exemple).

Cependant, cette flexibilité vient avec les coûts décrits plus hauts (lent, dispersé en mémoire, fragmentation de mémoire, ...). On peut alors concevoir des allocateurs spécialisés : ils auront plus de contraintes mais seront plus efficaces. On préfère alors généralement avoir des données continues en mémoire plutôt que des allocations plus rapides.

Les allocateurs sont des objets permettant d'allouer et de libérer de la mémoire. Généralement, ils se basent sur des gros blocs de mémoire alloués sur le tas, qu'ils vont ensuite mettre à disposition de façon optimisée.

Les garbage collectors, souvent intégrés dans les langages de plus hauts niveaux, sont une forme d'allocateur et peuvent être implémentés en C++.

Deux allocateurs simples utilisés souvent sont le stack allocator et le block allocator.

Comme son nom l'indique, le stack allocator va recopier le comportement d'une pile pour en avoir les mêmes propriétés. Il permet d'être plus flexible et est pratique pour allouer de sobjets dont on connaît la durée de vie. Par exemple, les moteurs de jeu utilisent ces allocateurs pour allouer des objets qui ne vivront qu'une frame : on parle alors parfois de frame allocator.

Le block allocator va allouer un gros bloc de mémoire qu'il va séparer en blocs de même taille. Ces blocs vont former une liste chaînée : chaque bloc pointe sur le suivant, jusqu'à ce qu'il n'y en ait plus. Allouer et déallouer ces blocs revient alors à insérer ou supprimer un bloc à la tête de la liste, ce qui est très rapide. Ces allocateurs sont souvent utilisés pour créer de nombreux objets de même type, comme pour les noeuds de listes, d'arbres ou de graphes.

L'alignement

Les données allouées sont souvent alignées en mémoire : leur adresse est alors le multiple d'une puissance de 2.

Cela vient notamment du fait que certaines architectures ne peuvent pas lire certaines données si elles ne sont pas alignées : c'est pourquoi les types natifs (ints, floats, pointeurs, références, longs, ...) ont des alignements différents, égaux à leur taille. On peut obtenir l'alignement d'un type avec alignof(T).

malloc (et new) sont assurés de renvoyer de la mémoire alignée selon le type natif le plus strict (généralement 8, contraint par les types de 8 octets comme long long, et les pointeurs pour une architecture 64bits). Par contre, ils n'assurent pas d'alignement supérieur.

L'allocation sur la pile assure l'alignement du type.

L'alignement d'un type peut être augmenté avec alignas(n). Cela peut être pratique pour différents problèmes de performance, comme pour la vectorisation (qui aura un chapitre dédié) ou pour contrôler l'accès aux cache line, qui regroupent les données par plages de 64 octets (alignées en mémoire sur 64 octets).

Pour aller plus loin

Les cache lines ont d'autres effets notables, comme le false sharing (pouvant drastiquement baisser les performances en multithread) ou l'associativité des caches (pouvant empêcher de charger la mémoire de certaines adresses en cache).

D'autres allocateurs plus généraux existent (Slab, Buddy), notamment des alternatives à malloc.

Le Data-Oriented Design prend en compte les contraintes matérielles pour concevoir des programmes très performants, en se focalisant sur la compréhension et la transformation des données.

L'utilisation explicite de mémoire virtuelle peut permettre des fonctionnalités intéressantes.

Les règles d'alignement peuvent créer des 'trous' dans les classes et structures. On peut alors réorganiser ces classes pour qu'elles prennent moins de place en mémoire (cependant, elles peuvent devenir être plus lentes à accéder).

L'allocation statique (qui stocke les variables statiques) peut parfois être influencée, avec par exemple les attributs hot ou cold de GCC, qui vont stocker des instructions souvent utilisées au même endroit pour maximiser l'utilisation des caches.

Challenges

(*) Créer une macro alloca_aligned(nb, align) qui alloue nb octets sur la pile, avec l'alignement requis. Expliquer pourquoi une fonction ne peut pas être utilisée à la place. Exemple :

template <class T>
bool test(int nb) {
    // Alloue nb objets de type T sur la pile.
    auto ptr = alloca_aligned(nb * sizeof(T), alignof(T));
    // Renvoie 'true' si l'allocation est bien alignée.
    auto address = reinterpret_cast<uintptr_t>(ptr);
    return address % alignof(T) == 0;
}

(**) Créer un 'bock allocator' respectant le concept standard d'allocateur pour pouvoir l'utiliser avec un conteneur de la librairie standard. Exemple :

// Bonus : permettre à la ressource utilisée (contenant les blocs) d'allouer de
// nouveaux blocs si aucun n'est disponible.
std::list<int, block_allocator<int>>
make_list(block_ressource<MySize, MyAlign>& resource) {
    auto list = std::list<int, block_allocator<int>>(resource.make_allocator());
    list.push_back(2);
    list.push_back(3);
    list.push_front(1);
    return list;
}