Un allocateur linéaire simple
Distribuez la mémoire linéairement.
Un allocateur linéaire simple est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.
Le principe de l’allocateur par déplacement
Un allocateur par déplacement (ou allocateur de zone) est la conception la plus simple. Vous conservez un grand tampon et un seul décalage. Chaque allocation renvoie simplement le décalage courant, puis le « déplace » de la taille demandée.
Il n’y a ni métadonnées par bloc ni recherche. L’allocation consiste essentiellement en une addition de pointeurs, ce qui la rend extrêmement rapide.
Un tampon statique de stockage
Pour cet exemple autonome, nous faisons reposer l’allocateur sur un tableau statique plutôt que sur le tas de l’OS. Le programme se compile et s’exécute partout, sans sbrk ni mmap.
Le tableau nous fournit une réserve fixe d’octets à découper.
#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;La fonction bump essentielle
L’allocation vérifie qu’il reste suffisamment de place, mémorise le début, avance le décalage et renvoie le pointeur de début. Si la demande devait dépasser la réserve, elle renvoie NULL.
Cette vérification de dépassement est la seule sécurité fournie par l’allocateur par déplacement.
void *bump_alloc(size_t size) {
if (offset + size > POOL_SIZE)
return NULL; /* out of pool */
void *p = &pool[offset];
offset += size;
return p;
}Un allocateur par déplacement complet et exécutable
Voici un programme complet. Il alloue deux entiers et une courte chaîne de caractères dans la réserve, puis les affiche, ce qui prouve que l’allocateur fonctionne.
Remarquez la faible quantité de code nécessaire par rapport à un véritable malloc.
#include <stdio.h>
#include <stddef.h>
#include <string.h>
#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;
void *bump_alloc(size_t size) {
if (offset + size > POOL_SIZE) return NULL;
void *p = &pool[offset];
offset += size;
return p;
}
int main(void) {
int *a = bump_alloc(sizeof(int));
int *b = bump_alloc(sizeof(int));
char *s = bump_alloc(6);
*a = 10; *b = 32;
strcpy(s, "hi");
printf("%d %d %s\n", *a, *b, s);
printf("used = %zu\n", offset);
return 0;
}Pas de libération individuelle
Le problème est le suivant : un allocateur par déplacement ne peut pas libérer une allocation isolée. Comme il ne possède pas de métadonnées, il ne sait pas où se termine un bloc et où commence le suivant pour le réutiliser.
Vous pouvez uniquement réinitialiser toute la zone en une seule fois, en remettant le décalage à zéro.
void bump_reset(void) {
offset = 0; /* frees everything at once */
}Pourquoi la réinitialisation est utile
Ce modèle tout ou rien est parfait pour les travaux organisés par phases : allouez de nombreux objets pendant une requête ou une image, puis réinitialisez la zone lorsque la phase se termine.
Les moteurs de jeu et les compilateurs utilisent largement les zones, car leur réinitialisation est en O(1) et évite de suivre des milliers de libérations individuelles.
/* Per-frame pattern */
for (int frame = 0; frame < 3; frame++) {
void *tmp = bump_alloc(128);
/* ... use tmp this frame ... */
bump_reset(); /* reclaim instantly */
}Suivi de l’espace restant
Il est pratique d’indiquer l’espace encore disponible. Il suffit de soustraire le décalage actuel de la taille de la zone mémoire.
Les appelants peuvent s’en servir pour décider de vider ou d’agrandir la zone avant de demander davantage d’espace.
size_t bump_remaining(void) {
return POOL_SIZE - offset;
}Une démonstration réinitialisable exécutable
Ce programme remplit une partie de la zone mémoire, affiche son utilisation, la réinitialise, puis montre que le décalage revient à zéro et que l’espace peut être réutilisé.
#include <stdio.h>
#include <stddef.h>
#define POOL_SIZE 256
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;
void *bump_alloc(size_t s){ if(offset+s>POOL_SIZE) return NULL; void *p=&pool[offset]; offset+=s; return p; }
void bump_reset(void){ offset = 0; }
int main(void) {
bump_alloc(100);
printf("after alloc: used=%zu\n", offset);
bump_reset();
printf("after reset: used=%zu\n", offset);
return 0;
}Alignement dans un allocateur par incrément
Un incrément octet par octet peut renvoyer des pointeurs mal alignés. Par sécurité, arrondissez le décalage vers le haut jusqu’à une frontière d’alignement avant de renvoyer un pointeur.
Nous détaillerons les calculs plus loin, mais c’est dans l’allocateur par incrément que l’alignement est le plus important, car il n’y a sinon aucun remplissage.
static size_t align_up(size_t n, size_t a) {
return (n + a - 1) & ~(a - 1); /* a must be power of 2 */
}Un allocateur par incrément aligné
En combinant ces éléments, nous alignons le décalage avant chaque allocation. Cela garantit que chaque pointeur renvoyé convient à tout type courant.
Le coût est une légère fragmentation interne due aux octets de remplissage.
#define ALIGN 16
void *bump_aligned(size_t size) {
offset = align_up(offset, ALIGN);
if (offset + size > POOL_SIZE) return NULL;
void *p = &pool[offset];
offset += size;
return p;
}Forces et limites
Les allocateurs par incrément sont imbattables en matière de rapidité et d’une simplicité élémentaire, sans surcharge par objet. Ils sont idéaux lorsque les objets ont la même durée de vie.
Leur faiblesse est l’absence de libération fine. Lorsque les durées de vie diffèrent, vous avez besoin de la conception avec liste de blocs libres présentée dans la leçon suivante.
Vérification rapide
Réfléchissez à la manière dont un allocateur par incrément récupère la mémoire.
Récapitulatif
Un allocateur par incrément fournit la mémoire en avançant un seul décalage dans un tampon, ce qui rend l’allocation aussi peu coûteuse qu’une addition de pointeur.
Il renonce à la libération individuelle au profit de la rapidité et de la simplicité, et ne récupère la mémoire qu’au moyen d’une réinitialisation complète. Alignez le décalage pour que les pointeurs renvoyés restent valides pour tous les types.
Apprends C avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 39
- Leçons
- 144
Questions Fréquemment Posées
La leçon « Un allocateur linéaire simple » est-elle gratuite ?
Oui — le texte complet de « Un allocateur linéaire simple » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Un allocateur linéaire simple » ?
Distribuez la mémoire linéairement. Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer C Academy ?
Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Un allocateur linéaire simple » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon C Academy ?
Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Comment fonctionne malloc
- Un allocateur linéaire simple
- Listes libres et réutilisation
- Alignement et découpage