Mémoire contigus

Buffer linéaire simple

Un buffer linéaire (ou tableau dynamique) est la structure de données la plus élémentaire : un bloc contigu de mémoire stockant une séquence d’éléments de même type. Chaque élément occupe une position fixe, calculable directement : $\text{adresse}(i) = \text{base} + i \times \text{sizeof}(T)$. Cet adressage direct permet un accès en $O(1)$ à n’importe quel élément, propriété fondamentale des tableaux.

Adresse :  0x1000   0x1004   0x1008   0x100C   0x1010
Contenu :  [  42  ] [  17  ] [  89  ] [  31  ] [  56  ]

Avantages:

1. Accès aléatoire en $O(1)$ : pas de traversée nécessaire.
2. Localité spatiale parfaite : les éléments consécutifs sont physiquement adjacents en mémoire, maximisant l’efficacité du cache (pré-chargement de 64 bytes (octets).
3. Overhead mémoire minimal : aucune métadonnée par élément (contrairement aux listes chaînées).

Inconvénients:

1. Insertions/suppressions coûteuses : insérer en position $i$ nécessite de décaler $n - i$ éléments, soit $O(n)$ en pire cas.
2. Réallocations lors de la croissance : lorsque le buffer est plein :
   - allocation d’un nouveau buffer (typiquement 1.5-2x la taille courante),
   - copie de tous les éléments ($O(n)$),
   - libération de l’ancien buffer.

Malgré le coût ponctuel en $O(n)$ d’une réallocation, l’analyse amortie montre que le coût moyen d’une insertion en fin de tableau est $O(1)$. Donc si un tableau qui double sa capacité à chaque réallocation. Ainsi, pour atteindre $n$ éléments :

• Réallocations aux tailles : $1, 2, 4, 8, \dots, n$
• Coût total des copies : $1 + 2 + 4 + \cdots + n = 2n - 1 = O(n)$
• Coût amorti par insertion : $\frac{O(n)}{n} = O(1)$

Typiquement pour utiliser cette structure :

int capacity = 50; // la quantité de mémoire alloué
int size = 0; // la quantité de mémoire utilisé
int *buffer = (int*)malloc(sizeof(int) * capacity);
// vérifier si buffer != NULL
buffer[size++] = 5; // ajout d'un élément
free(buffer); // ne pas oublié de libéré la mémoire

Buffer circulaire (ring buffer)

Un buffer circulaire (ring buffer) résout l’impossibilité d’insérer efficacement en tête de séquence dans un buffer linéaire classique. Ce dernier nécéssitant de possibles réallocations. On considère le buffer comme un anneau : lorsque l’indice dépasse la fin, il revient au début. L’inconvenient est que cette structure est limité en taille. Nous avons utilisé ce principe dans le cours de C/Unix notament avec les MPMCs.

Deux indices sont maintenus :

• read (head) : position du prochain élément à lire
• write (tail) : position du prochain élément à écrire

Buffer physique : [  A  ] [  B  ] [  C  ] [  -  ] [  -  ]
Indices :         read=0          write=3

Après insertion de D et E :

Buffer physique : [  A  ] [  B  ] [  C  ] [  D  ] [  E  ]
Indices :         read=0                          write=0

L’accès circulaire repose sur le modulo :

write_idx = (write_idx + 1) % capacity;
read_idx  = (read_idx  + 1) % capacity;

Pour éviter le coût du modulo, on choisit une capacité : $C = 2^k$
On peut alors utiliser un masque binaire :

write_idx = (write_idx + 1) & (capacity - 1);

Opération en un cycle, sans division.

Double buffering

Bien que le principe sous-jacent ne soit pas strictement une structure de données mais plutôt une technique d’optimisation, sa connaissance doit faire partie du cursus. L’idée du double buffering consiste à maintenir deux buffers :

• front : lu par le consommateur
• back : écrit par le producteur
• En fin de cycle, on échange les pointeurs (coût en $O(1)$).

Implémentation minimale :

struct double_buffer {
  char *front;
  char *back;
  size_t size;
};

void swap_buffers(struct double_buffer *db) {
  char *tmp = db->front;
  db->front = db->back;
  db->back  = tmp;
}

Il n’y a aucune copie de données, seulement une permutation de pointeurs. Ce mécanisme est largement utilisé dans les domaines de l’audiovisuel et de l’embarqué. Un rapprochement peut également être établi avec certains concepts en deep learning (analogie simplifiée avec des mécanismes de mémoire récurrente de type LSTM).

Il permet d’exploiter efficacement le multithreading : pendant qu’un ou plusieurs threads écrivent dans un buffer (avec la synchronisation appropriée), d’autres threads peuvent lire ou traiter le second buffer.

Typiquement, les applications basées sur OpenGL, DirectX , … ou Metal utilisent ce principe. Pendant qu’une image est en cours de préparation, la précédente est affichée. De même en audio : pendant qu’un segment est en lecture, le suivant est généré. Ce principe contribue à réduire les latences et à stabiliser les flux de traitements.

Le tripple buffering est également possible : un buffer en écriture, un buffer en transaction (déplacemenet mémoire) et le buffer en lecture.

Mémoire fragmentée

Liste simplement chaînée

Une liste simplement chaînée est une structure dynamique composée d’une succession de nœuds, chacun contenant :

• une valeur,
• un pointeur vers le nœud suivant.

Implémentation typique :

struct node {
    int data;
    struct node *next;
};

struct node *begin = NULL; // une liste vide

Le champ next vaut NULL lorsqu’il n’existe pas de successeur. Une liste est toujours représentée par un pointeur vers son premier élément (la tête). Cette contrainte est fondamentale : si la tête est perdue, l’ensemble des nœuds devient inaccessible, ce qui provoque une fuite mémoire.

Une représentation mémoire possible serait :

0x2340 : [ 42 | 0x1A20 ]
0x1A20 : [ 17 | 0x4F00 ]
0x4F00 : [ 89 | NULL ]

Les adresses montrent que les nœuds ne sont pas contigus en mémoire. Chaque élément est alloué indépendamment, généralement sur le tas (heap). Cette absence de contiguïté implique une faible localité spatiale, ce qui pénalise les performances lors des parcours intensifs en raison des défauts de cache.

// création d'un noeud
begin = (struct node*)malloc(sizeof(struct node));
// test malloc
begin->data = 42;
begin->next = NULL;

struct node *tmp = (struct node*)malloc(sizeof(struct node));
// test malloc
tmp->data = 16;
tmp->next = root;

// Ajout d'une donnée devant
begin = tmp;
// Comment insérer à la fin ou au millieu ?
// Comment bien géré la mémoire ?

Avantage:

• L’insertion en tête est particulièrement efficace, car elle ne nécessite qu’une mise à jour de pointeurs. C’est donc on $O(1)$.
• L’insertion en queue requiert un parcours complet sauf si l’on maintient explicitement un pointeur vers le dernier élément. C’est donc soit $O(1)$ soit $O(n)$.

Inconvénients:

• Le parcours s’effectue nécessairement de manière séquentielle : pour atteindre le $k$-ème élément, il faut suivre les $k$ pointeurs (indirection) intermédiaires. Contrairement à un tableau, aucun calcul d’offset ne permet un accès direct. C’est donc en $O(n)$ (ou $O(k)$)
• Surcoût mémoire dû au stockage du pointeur (8 octets en 64 bits). Typiquement pour stocké une list d’entier (int = 4 octet) il faut un pointeur de plus par donnée (int* = 8 octets). La complexité sptil est donc $O(3n)$ mais cela devrais être noté $O(n)$. Cette notation perd donc beaucoup d’intéret.
• Fragmentation mémoire total et cache misses systématique.
• Non adaptée aux traitements vectorisés ou aux optimisations basées sur la localité mémoire.

La liste simplement chaînée est donc adaptée aux scénarios où les insertions et suppressions en tête sont fréquentes, ou lorsque la taille varie fortement et que la réallocation d’un tableau serait coûteuse. En revanche, pour des parcours massifs ou des accès indexés répétés, un tableau dynamique reste généralement plus performant grâce à sa contiguïté mémoire et à une meilleure exploitation du cache processeur.

Liste doublement chaînée

On ajoute simplement un pointeur prev :

struct node {
    int data;
    struct node *next;
    struct node *prev;
};

• Suppression en $O(1)$ sans connaître le précédent.
• Overhead mémoire doublé, dans ce cas nous somme en $O(5n)$. Pire dans le cas ou l’on souhaiterais stoké des charactère, nous serions en $O(16n)$. Il faut 16x plus de méta donnée que de donnée réalement utilisé.

Skip lists

• Structure probabiliste offrant : $O(\log n)$ en moyenne pour recherche, insertion, suppression.
• Niveau $k$ contient environ : $\frac{n}{2^k}$
• Hauteur déterminée aléatoirement avec probabilité : $P(\text{niveau } k) = p^k$
• Complexité moyenne : $O(\log n)$

Limite pratique:

• Cache misses élevés.
• Sur ensembles hors-cache, le coût mémoire domine, réduisant l’avantage théorique.

Unrolled linked lists

Une unrolled linked list est une variante de la liste simplement chaînée dans laquelle chaque nœud ne contient pas un seul élément, mais un petit tableau de $k$ éléments contigus. On réduit ainsi le nombre total de pointeurs et on améliore la localité mémoire.

struct unrolled_node {
    struct unrolled_node *next;
    int num_elements;
    int elements[MAX_ELEMENTS]; // k
};

Chaque nœud contient :

• un pointeur vers le nœud suivant,
• un compteur d’éléments effectivement stockés,
• un bloc contigu de $k$ valeurs.

En regroupant plusieurs éléments dans chaque nœud, cette organisation réduit la fragmentation mémoire et améliore la localité spatiale, car plusieurs valeurs consécutives sont chargées en une seule ligne de cache. De plus, un facteur $k$ plus élevé diminue le nombre de nœuds à parcourir, réduisant ainsi les déréférencements de pointeurs et le nombre de cache misses.

Insertion :

• Recherche du nœud : $O(n/k)$
• Insertion locale : $O(k)$

Choix de $k$

Le paramètre critique est la taille du nœud. L’objectif est généralement d’aligner la taille d’un nœud sur une ligne de cache, typiquement 64 octets sur les architectures modernes, afin de maximiser les cache hits. On prendra comme hypothese que les pointeurs occupent 8 octets (architecture 64 bits) et les entiers 4 octets. On souhaite donc $\text{sizeof(node)} \approx 64 \text{ octets}$ (maximiser les caches hits).

Alors :

• $8 + 4k \approx 64$
• $k \approx 14$

Cette valeur est proche de l’optimum théorique pour tenir dans une seule ligne de cache (un seul cache miss pour charger le nœud complet). Cependant, l’analyse doit considérer :

1. Les multiples de 64 octets : Il est parfois pertinent de viser des tailles plus importantes.
   * 64 octets → 1 cache miss
   * 128 octets → 2 cache misses
   * 256 octets → 4 cache misses
   * 512 octets → 8 cache misses

Un nœud de 128 octets peut rester acceptable si l’on privilégie la réduction du nombre total de nœuds au détriment d’un second cache miss. MAIS aussi pour la vectorisation des calcules : les instructions SIMD peuvent traité jusqu’a 512 octets simultanement sur les derniers processeur intel (AVX-512).

2. Le padding de la structure
   Le compilateur peut ajouter du padding pour respecter les contraintes d’alignement. Par exemple, num_elements (4 octets) peut entraîner un réalignement avant le tableau selon l’ABI. La formule réelle est donc : $\text{sizeof(node)} = \text{sizeof(pointer)} + \text{sizeof(int)} + 4k + \text{padding}$

Il est recommandé de vérifier avec :

static_assert(sizeof(unrolled_node) == 64); // Ou multiples visé

ou d’utiliser alignas(64) ou tout autre technique (union __attribut__ …) si l’on souhaite forcer l’alignement sur une ligne de cache (c++).

Donc le choix exact dépend :

• de la taille des données stockées,
• de l’architecture cible (taille des lignes de cache),
• du profil d’accès (lecture majoritaire vs insertions fréquentes).

Cette structure constitue ainsi un compromis efficace entre la liste chaînée (flexible mais peu locale) et le tableau dynamique (très local mais coûteux en réallocation).

Localité cache

La hiérarchie mémoire moderne est profondément non uniforme : chaque niveau agit comme un cache du niveau inférieur, avec une latence croissante et une capacité plus importante. Le facteur déterminant des performances n’est donc pas seulement la complexité algorithmique, mais la localité des accès mémoire.

Hiérarchie mémoire typique :

Un accès DRAM coûte environ 50× plus cher qu’un accès L1. En pratique, quelques dizaines de cache misses suffisent à dominer le temps d’exécution d’un algorithme pourtant théoriquement optimal.

Pour un tableau : $\text{cache misses} \approx \frac{n}{B}$ où $B$ est la taille d’une cache line (typiquement bytes). Cela signifie qu’un seul cache miss permet de charger plusieurs éléments utiles. Le coût mémoire est donc amorti sur plusieurs accès consécutifs.

Pour une liste chaînée (nous reviendrons dessus) : $\text{cache misses} \approx n$. Chaque nœud pouvant résider à une adresse arbitraire, le processeur ne peut ni précharger efficacement les données, ni exploiter la localité spatiale. On obtient alors un défaut de cache presque à chaque itération.

Les buffers contigus maximisent :

• Localité spatiale : les données adjacentes sont stockées physiquement côte à côte.
• Localité temporelle : les éléments récemment accédés ont une forte probabilité d’être réutilisés rapidement.
• Prefetching matériel : les processeurs modernes détectent les motifs d’accès séquentiels et chargent automatiquement les cache lines suivantes.
• Bande passante effective : les accès séquentiels exploitent pleinement les mécanismes de burst de la DRAM.

En conséquence, deux structures ayant la même complexité asymptotique peuvent présenter des performances radicalement différentes dès que le working set dépasse la capacité du cache L3. La compréhension de la localité mémoire est donc centrale dans l’ingénierie des structures de données performantes.

Conclusion

Généralement, les structures hybrides offrent un compromis intéressant entre localité mémoire et flexibilité structurelle. Les unrolled linked lists sont configurables via leur facteur $k$ (nombre d’éléments par bloc). Ce paramètre permet d’ajuster l’équilibre entre localité, donc de performance de lecture/écriture grâce à une meilleure exploitation du cache et coût d’insertion ou de modification.

Le programmeur dispose ainsi d’un levier d’optimisation dépendant du contexte d’exécution : volumétrie des données, fréquence des insertions, contraintes de latence ou comportement du cache.

Il convient toutefois de rappeler que le choix de la structure adéquate relève de la responsabilité de l’ingénieur. Cette décision doit être cohérente avec les contraintes matérielles (architecture CPU, hiérarchie mémoire) et logicielles (modèle de concurrence, profil de charge, exigences de performance).

• Les buffers contigus dominent grâce à la localité cache et aux accès en $O(1)$.
• Les listes chaînées offrent une grande flexibilité mais souffrent de cache misses systématiques.
• Les skip lists fournissent $O(\log n)$ en moyenne, au prix d’un comportement mémoire irrégulier.
• Les unrolled linked lists constituent un compromis performant, combinant localité et insertion flexible.