khalil Drissi Cms

Étiquette : mémoire

  • Conception orientée données et caches du processeur

    Conception orientée données et caches du processeur

    La plus grande leçon de performance que j’aie apprise, c’est que les processeurs modernes ne sont pas lents à calculer, ils sont lents à attendre la mémoire. Un défaut de cache vers la mémoire principale peut coûter quelques centaines de cycles. Pendant ce temps, le processeur aurait pu faire des centaines d’additions. Une fois cet écart intériorisé, on commence à concevoir les programmes autour de la façon dont les données circulent, pas seulement des opérations qu’on exécute dessus. C’est le cœur de la conception orientée données.

    La hiérarchie mémoire est la vraie machine

    Entre le processeur et la mémoire principale s’intercalent plusieurs niveaux de cache : L1 est minuscule et presque aussi rapide que les registres, L2 est plus grand et plus lent, L3 plus grand et plus lent encore. Quand le processeur a besoin d’un octet, il n’en cherche pas un seul. Il récupère une ligne de cache entière, typiquement 64 octets, et la range en cache. Si votre accès suivant est dans cette ligne, il est quasi gratuit. S’il est ailleurs au loin, vous payez la pénalité complète du défaut.

    Cela veut dire que la disposition de vos données en mémoire contrôle directement votre performance. Deux programmes faisant l’arithmétique identique peuvent différer d’un ordre de grandeur uniquement à cause des schémas d’accès.

    Tableau de structures contre structure de tableaux

    L’exemple classique est la façon de stocker une collection d’enregistrements. La disposition intuitive, orientée objet, est un tableau de structures :

    struct Particle {
    float x, y, z;     // position
    float vx, vy, vz;  // vitesse
    float mass;
    char name[32];
};
struct Particle particles[100000];

// mise à jour des positions
for (int i = 0; i < 100000; i++) {
    particles[i].x += particles[i].vx;
}

    Cette boucle ne touche que x et vx, mais chaque ligne de cache chargée est pleine de mass, name et des autres champs dont vous n'avez pas besoin. Vous traînez des données froides à travers le cache pour rien. La disposition orientée données scinde les champs en tableaux parallèles, une structure de tableaux :

    struct Particles {
    float x[100000], y[100000], z[100000];
    float vx[100000], vy[100000], vz[100000];
    float mass[100000];
};

for (int i = 0; i < 100000; i++) {
    p.x[i] += p.vx[i];
}

    Maintenant le tableau x et le tableau vx sont chacun densément empaquetés. Chaque octet tiré en cache est un octet utilisé. Sur du vrai matériel, ce genre de changement donne couramment des accélérations de 3x à 10x sur les boucles chaudes, sans aucun changement d'algorithme.

    Pourquoi la poursuite de pointeurs fait mal

    Les listes chaînées et les arbres à nœuds sont l'opposé d'amicaux pour le cache. Chaque nœud est une allocation de tas séparée qui peut vivre n'importe où, donc parcourir la liste saute partout en mémoire et rate le cache à presque chaque étape. Si vous comprenez pile contre tas et comment les allocations de tas s'éparpillent, cela découle naturellement. Un tableau plat parcouru linéairement est nettement plus rapide qu'une liste chaînée du même nombre d'éléments, même si les deux sont en O(n), car le préchargeur matériel peut prédire et précharger un accès séquentiel.

    • Préférez les tableaux contigus aux structures à nœuds quand vous itérez souvent.
    • Regroupez les champs auxquels vous accédez ensemble, et séparez ceux que vous n'utilisez pas.
    • Traitez les données dans l'ordre où elles sont en mémoire dès que possible.
    • Gardez les données chaudes petites pour qu'il en tienne plus en cache à la fois.

    C'est la même idée qu'un bon allocateur

    Voilà pourquoi la stratégie d'allocation compte autant. Si vous allouez dix mille objets un par un, ils finissent éparpillés. Si vous les allouez en un seul bloc, ils sont voisins et itèrent vite. L'allocateur sur mesure de écrire un allocateur mémoire simple vous donne exactement ce contrôle : vous décidez la disposition au lieu de la laisser au hasard.

    Quand y recourir

    Je ne restructure pas tout autour du cache. Pour du code qui tourne une fois ou rarement, la clarté l'emporte. Mais pour les boucles chaudes, les noyaux internes qui tournent des millions de fois, la disposition des données est généralement la première chose que je règle et souvent le meilleur retour. Profilez d'abord, trouvez où sont les défauts de cache, puis disposez les données comme le matériel veut les lire. La machine est ravie d'être rapide si vous cessez de la faire attendre.

  • Comment fonctionnent vraiment les pointeurs

    Comment fonctionnent vraiment les pointeurs

    Les pointeurs m’ont fait peur pendant un temps embarrassant. La syntaxe n’aidait pas : des astérisques avec deux sens différents, des esperluettes, des flèches. Mais le concept est simple une fois la syntaxe écartée. Un pointeur est une variable dont la valeur est une adresse mémoire. C’est tout. C’est un nombre qui indique où vit quelque chose.

    La mémoire est un seul gigantesque tableau

    Imaginez l’espace d’adressage de votre processus comme un énorme tableau d’octets, indexé de zéro jusqu’à un nombre colossal. Chaque variable que vous déclarez vit à un certain indice de ce tableau. Un pointeur stocke simplement l’un de ces indices. Quand vous « déréférencez » un pointeur, vous dites « va à cet indice et lis ce qui s’y trouve ».

    int x = 42;
int *p = &x;      // p contient l'adresse de x
printf("%d\n", *p);   // déréférencement : affiche 42
*p = 7;           // écriture à travers le pointeur
printf("%d\n", x);    // affiche 7

    L’esperluette signifie « adresse de » et l’astérisque dans une expression signifie « la chose à cette adresse ». Le même astérisque dans une déclaration signifie « cette variable est un pointeur ». Deux rôles pour un seul symbole, ce qui est la principale raison pour laquelle les pointeurs semblent déroutants au début.

    Le type compte plus que vous ne le pensez

    Un pointeur n’est pas qu’une adresse, c’est une adresse plus un type. Le type indique au compilateur deux choses : combien d’octets lire au déréférencement, et de combien sauter lors d’une arithmétique. Un pointeur sur int et un pointeur sur char peuvent contenir exactement la même adresse numérique et se comporter tout à fait différemment.

    int arr[4] = {10, 20, 30, 40};
int *p = arr;     // pointe sur arr[0]
p++;              // pointe maintenant sur arr[1], déplacé de 4 octets, pas de 1
printf("%d\n", *p);   // affiche 20

    Voilà l’idée clé de l’arithmétique des pointeurs. Ajouter un à un pointeur sur int le déplace de sizeof(int) octets, pas d’un octet. Le compilateur met à l’échelle pour vous selon le type. C’est aussi pourquoi tableaux et pointeurs semblent si interchangeables en C : indexer arr[i] est défini comme prendre l’adresse de arr, ajouter i fois la taille d’un élément, puis déréférencer.

    Où pointent les pointeurs

    Un pointeur peut contenir l’adresse d’une variable de pile, d’une allocation sur le tas, d’une fonction, ou de rien du tout. Le « où » compte parce qu’il décide si le déréférencement est sûr. Si les durées de vie pile contre tas restent floues pour vous, c’est la base ici, et je l’ai couverte dans pile contre tas : comment la mémoire fonctionne vraiment. Un pointeur vers une variable de pile devient pendouillant dès que la trame retourne. Un pointeur vers de la mémoire du tas libérée est un use-after-free qui n’attend que de planter.

    • Pointeur NULL : contient l’adresse zéro, un « ne pointe vers rien » délibéré. Le déréférencer plante, ce qui est en fait le résultat le plus aimable.
    • Pointeur pendouillant : contient une adresse autrefois valide. Le déréférencer est un comportement indéfini et peut corrompre des données silencieusement.
    • Pointeur sauvage : jamais initialisé, contient n’importe quoi. Le pire, car il peut pointer partout.

    Pointeurs sur pointeurs

    Dès qu’un pointeur n’est qu’une variable, un pointeur sur pointeur cesse d’être mystérieux. C’est l’adresse d’une variable qui contient elle-même une adresse. Il en faut un chaque fois qu’une fonction doit changer où un pointeur pointe, pas seulement ce vers quoi il pointe.

    void allocate(int **out) {
    *out = malloc(sizeof(int));   // écrit une nouvelle adresse dans le pointeur de l'appelant
    **out = 99;                   // écrit une valeur dans cette mémoire
}

int *p = NULL;
allocate(&p);     // passe l'adresse de p pour que la fonction puisse le modifier
printf("%d\n", *p);   // affiche 99

    Pourquoi ça vaut l’effort

    Les pointeurs sont le mécanisme derrière presque tout ce qui est intéressant en code système : structures chaînées, mémoire dynamique, passage de gros objets sans copie, dialogue avec le matériel à des adresses fixes. Ils sont aussi la source de la plupart des plantages en C. L’allocateur que je décris dans écrire un allocateur mémoire simple n’est rien d’autre qu’une manipulation soigneuse de pointeurs sur un bloc brut d’octets. Dès qu’on voit un pointeur comme un entier typé dans le grand tableau d’octets, la peur s’en va et la puissance apparaît.

  • Écrire un allocateur mémoire simple

    Écrire un allocateur mémoire simple

    La première fois que j’ai écrit mon propre malloc, le concept de mémoire dynamique a cessé de ressembler à une boîte noire. Un allocateur n’est qu’un programme qui gère un gros bloc de mémoire et en distribue des morceaux à la demande. Les parties difficiles sont la comptabilité et la fragmentation, rien de mystique. Voici une version minimale.

    D’où vient la mémoire

    Votre allocateur a besoin de mémoire brute à découper. Sur Unix, vous l’obtenez du noyau avec sbrk, qui déplace le sommet du tas, ou avec mmap pour de plus grandes régions. sbrk est le plus simple à raisonner : appelez-le avec un nombre positif et le tas grandit, en retournant un pointeur vers le nouvel espace.

    void *region = sbrk(4096);   // demande une page au noyau
if (region == (void *) -1) {
    // plus de mémoire
}

    Tout le jeu consiste maintenant à prendre cette région et à la distribuer, en se souvenant des parties utilisées et des parties libres.

    Les en-têtes de bloc : l’astuce centrale

    L’idée fondamentale est de stocker des métadonnées juste avant chaque bloc distribué. Quand l’appelant demande N octets, vous réservez en réalité N octets plus la taille d’un petit en-tête. Vous retournez un pointeur situé après l’en-tête, donc l’appelant ne le voit jamais. Quand il appelle free avec ce pointeur, vous reculez pour retrouver l’en-tête.

    typedef struct block {
    size_t size;          // taille utile en octets
    int free;             // 1 si disponible, 0 si utilisé
    struct block *next;   // bloc suivant dans la liste
} block_t;

#define HEADER_SIZE sizeof(block_t)

    Je tiens une liste chaînée de ces en-têtes. Pour allouer, je parcours la liste à la recherche d’un bloc libre assez grand. C’est la stratégie first-fit : prendre le premier bloc qui convient. Le best-fit (le plus petit bloc qui rentre) gaspille moins d’espace mais est plus lent à chercher. Les deux conviennent pour apprendre.

    Le chemin d’allocation

    static block_t *head = NULL;

void *my_malloc(size_t size) {
    block_t *cur = head;
    while (cur) {
        if (cur->free && cur->size >= size) {
            cur->free = 0;
            return (void *)(cur + 1);   // mémoire juste après l'en-tête
        }
        cur = cur->next;
    }
    // rien de libre, agrandir le tas
    block_t *blk = sbrk(HEADER_SIZE + size);
    if (blk == (void *) -1) return NULL;
    blk->size = size;
    blk->free = 0;
    blk->next = head;
    head = blk;
    return (void *)(blk + 1);
}

    L’expression cur + 1 est de l’arithmétique de pointeurs sur un pointeur block_t, donc elle saute exactement après l’en-tête. Si cette ligne semble étrange, mon article sur comment fonctionnent vraiment les pointeurs explique pourquoi ajouter un déplace d’une structure entière, pas d’un octet.

    Libérer et le problème de la fragmentation

    Libérer est presque trop facile : trouver l’en-tête et basculer le drapeau free. La mémoire n’est pas rendue au noyau, elle est simplement marquée réutilisable par la prochaine allocation.

    void my_free(void *ptr) {
    if (!ptr) return;
    block_t *blk = (block_t *)ptr - 1;   // recule jusqu'à l'en-tête
    blk->free = 1;
}

    Cette version naïve a un vrai défaut : la fragmentation. Libérez un bloc de 100 octets et un autre de 100 octets côte à côte, puis demandez 150 octets, et mon allocateur échoue alors même que 200 octets contigus sont libres. La correction est le coalescing : à la libération, vérifier si les blocs voisins sont aussi libres et les fusionner en un bloc plus grand. Les vrais allocateurs scindent aussi les blocs surdimensionnés pour qu’une demande de 16 octets ne consomme pas un morceau de 4 Ko.

    L’alignement, le détail qui mord plus tard

    Il y a un problème de correction que ma version jouet escamote : l’alignement. Le processeur attend qu’une valeur de huit octets se trouve à une adresse divisible par huit, et sur certaines architectures un accès mal aligné provoque une faute pure et simple. Un vrai allocateur arrondit chaque demande vers le haut pour que la zone utile commence toujours sur une frontière correctement alignée, généralement 16 octets sur un système 64 bits. Ma version marche par hasard parce que l’en-tête est déjà un multiple de l’alignement, mais dès que vous commencez à scinder des blocs, il faut arrondir les tailles, sinon vous rendez des adresses qui plantent sur certaines lectures. C’est le genre de bug qui se cache des mois puis ne surgit que sur une seule plateforme.

    Pourquoi ça vaut la peine de le construire

    • Vous cessez de craindre malloc et le voyez comme un composant réglable.
    • Vous comprenez pourquoi les schémas d’allocation comptent pour la performance, ce qui rejoint directement conception orientée données et caches du processeur.
    • Vous voyez exactement pourquoi le double-free et le use-after-free corrompent la mémoire : ils gribouillent sur ces en-têtes.

    Les allocateurs de production comme jemalloc et tcmalloc ajoutent des classes de taille, des caches par thread et des structures astucieuses, mais le squelette est celui que je viens de décrire. Connaître le squelette, c’est la différence entre utiliser la mémoire et la comprendre.

  • Pile contre tas : comment la mémoire fonctionne vraiment

    Pile contre tas : comment la mémoire fonctionne vraiment

    Les gens parlent de « la pile » et du « tas » comme si c’étaient des objets physiques qu’on pourrait montrer du doigt. Ce n’en sont pas. Ce sont deux régions du même espace d’adressage virtuel, gérées de façons complètement différentes. J’ai écrit du C pendant des années avant d’intérioriser vraiment la différence, et une fois que ce fut fait, beaucoup de bugs déroutants ont soudain pris du sens.

    La pile est une région, pas une structure de données

    Quand votre programme démarre, le système d’exploitation donne à chaque thread un bloc de mémoire contiguë appelé la pile. Elle croît dans une direction, généralement vers le bas, vers les adresses basses sur x86 et ARM. Chaque fois que vous appelez une fonction, le processeur empile une trame : l’adresse de retour, les registres sauvegardés et la place pour les variables locales. Quand la fonction retourne, cette trame disparaît instantanément. Aucune comptabilité, aucune recherche, juste un ajustement de registre.

    C’est pourquoi l’allocation sur la pile est rapide. Il y a un registre, le pointeur de pile, et « allouer » 64 octets revient à lui soustraire 64. Libérer revient à les rajouter. Le coût est quasi nul.

    Le piège, c’est la durée de vie. Une variable de pile vit exactement le temps de l’appel de fonction qui l’a créée. Retournez un pointeur vers une locale et vous pointez vers une mémoire que le prochain appel va écraser.

    // Ceci est un bug. Le tampon meurt quand la fonction retourne.
char *make_greeting(void) {
    char buffer[32];
    snprintf(buffer, sizeof buffer, "bonjour");
    return buffer;   // pointeur pendouillant
}

    Le tas, pour ce qui survit à une trame

    Le tas est le reste de votre espace d’adressage utilisable, et il est géré par un allocateur (malloc et compagnie) plutôt que par le processeur. Quand vous demandez de la mémoire, vous obtenez un bloc qui reste valide jusqu’à ce que vous le libériez explicitement. Cette souplesse est tout l’intérêt, et c’est aussi là que le travail se cache. L’allocateur doit suivre quels blocs sont libres, en trouver un assez grand et le rendre. J’ai écrit un article entier sur écrire un allocateur mémoire simple parce que cette mécanique vaut la peine d’être comprise directement.

    char *make_greeting(void) {
    char *buffer = malloc(32);   // vit sur le tas
    if (!buffer) return NULL;
    snprintf(buffer, 32, "bonjour");
    return buffer;   // valide, mais l'appelant en est désormais propriétaire
}

    Les compromis que vous ressentez vraiment

    • Vitesse : l’allocation sur la pile est un simple décalage de pointeur. Sur le tas, elle parcourt des structures et peut appeler le noyau. L’écart est grand.
    • Durée de vie : la mémoire de pile est liée à la portée. La mémoire du tas vit jusqu’à ce que vous la libériez, ce qui veut dire qu’il faut y penser.
    • Taille : les piles sont petites, souvent de 1 à 8 Mo. Mettez un tableau de 10 Mo sur la pile et vous obtenez un débordement de pile. Les grosses données vont sur le tas.
    • Localité : la mémoire de pile est chaude. Elle vient d’être touchée, donc elle est presque toujours en cache. La mémoire du tas peut être éparpillée, ce qui compte plus qu’on ne le pense.

    Pourquoi ceci touche à la performance

    Le point sur la localité est celui qui mord dans les vrais systèmes. Un pointeur vers le tas est une valeur, et suivre ce pointeur en est une aussi. L’endroit physique où il atterrit décide si votre processeur cale. Je creuse cela dans conception orientée données et caches du processeur, mais en résumé, éparpiller vos données sur des allocations de tas peut être plus lent que l’algorithme ne le laisse croire, uniquement à cause des défauts de cache.

    Un modèle mental qui tient

    Voici comment je le vois maintenant. La pile est un brouillon que le processeur gère pour vous, parfait pour des valeurs courtes et de taille connue. Le tas est un entrepôt que vous gérez vous-même, pour tout ce dont la taille ou la durée de vie ne peut être fixée à la compilation. La plupart des bugs en C viennent de la confusion entre les deux : retourner des pointeurs de pile, libérer deux fois la mémoire du tas, ou oublier de la libérer.

    Si des langages comme Rust paraissent sûrs, c’est qu’ils encodent ces règles dans le système de types pour que le compilateur attrape les erreurs. Pour voir comment cela fonctionne sans ramasse-miettes, lisez sûreté mémoire avec l’ownership et l’emprunt de Rust. Mais on ne peut vraiment apprécier ce contre quoi Rust vous protège qu’après avoir senti soi-même les angles tranchants de la pile et du tas.