Un semplice allocatore bump
Distribuisca la memoria in modo lineare.
Un semplice allocatore bump è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.
L'idea del bump allocator
Un bump allocator (o allocatore ad arena) è il design più semplice. Si utilizza un unico buffer grande e un solo offset. Ogni allocazione restituisce semplicemente l'offset corrente, quindi lo fa avanzare della dimensione richiesta.
Non sono presenti metadati per blocco né operazioni di ricerca. L'allocazione consiste essenzialmente in una sola somma tra puntatori, il che la rende estremamente veloce.
Un buffer statico di supporto
Per un esempio autonomo utilizziamo un array statico come memoria di supporto dell'allocatore, invece dell'heap del sistema operativo. Il programma viene compilato ed eseguito ovunque, senza sbrk o mmap.
L'array ci fornisce un pool fisso di byte da suddividere.
#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;La funzione bump principale
L'allocazione verifica che rimanga spazio sufficiente, memorizza l'inizio, fa avanzare l'offset e restituisce il puntatore all'inizio. Se la richiesta supererebbe la capacità del pool, restituisce NULL.
Il controllo dell'overflow è l'unica misura di sicurezza fornita dal bump allocator.
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 bump allocator completo ed eseguibile
Ecco un programma completo. Alloca dal pool due interi e una stringa breve, quindi li stampa, dimostrando che l'allocatore funziona.
Notate quanto poco codice richieda rispetto a un vero 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;
}Nessuna free individuale
Il limite è il seguente: un bump allocator non può liberare una singola allocazione. Poiché non dispone di metadati, non sa dove termini un blocco e inizi quello successivo da riutilizzare.
È possibile reimpostare soltanto l'intera arena in una volta sola, riportando l'offset a zero.
void bump_reset(void) {
offset = 0; /* frees everything at once */
}Perché il reset è utile
Questo modello tutto-o-niente è perfetto per il lavoro suddiviso in fasi: si allocano molti oggetti durante una richiesta o un frame, poi si reimposta l'arena quando la fase termina.
I motori di gioco e i compilatori utilizzano ampiamente le arene perché il reset è O(1) ed evita di tenere traccia di migliaia di operazioni di free individuali.
/* Per-frame pattern */
for (int frame = 0; frame < 3; frame++) {
void *tmp = bump_alloc(128);
/* ... use tmp this frame ... */
bump_reset(); /* reclaim instantly */
}Monitoraggio dello spazio rimanente
È utile rendere visibile quanto spazio rimane. Si tratta semplicemente della dimensione del pool meno l'offset corrente.
I chiamanti possono usare questo valore per decidere se eseguire un flush o aumentare la capacità prima di richiedere altro spazio.
size_t bump_remaining(void) {
return POOL_SIZE - offset;
}Una dimostrazione eseguibile del reset
Questo programma riempie una parte del pool, stampa l'utilizzo, esegue il reset e mostra che l'offset torna a zero, rendendo nuovamente disponibile lo spazio.
#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;
}Allineamento in un bump allocator
Un incremento byte per byte può restituire puntatori non allineati. Per sicurezza, arrotondi l'offset verso l'alto fino a un limite di allineamento prima di restituire un puntatore.
Analizzeremo la matematica in dettaglio più avanti, ma è nel bump allocator che l'allineamento è più importante, perché altrimenti non ci sarebbe alcun padding.
static size_t align_up(size_t n, size_t a) {
return (n + a - 1) & ~(a - 1); /* a must be power of 2 */
}Un bump allocator allineato
Combinando i vari elementi, allineiamo l'offset prima di ogni allocazione. In questo modo garantiamo che ogni puntatore restituito sia adatto a qualsiasi tipo comune.
Il costo è una lieve frammentazione interna dovuta ai byte di padding.
#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;
}Vantaggi e limiti
I bump allocator sono imbattibili in termini di velocità e semplicissimi, senza alcun overhead per oggetto. Sono ideali quando gli oggetti condividono la stessa durata di vita.
Il loro punto debole è l'assenza di una liberazione a grana fine. Quando le durate di vita differiscono, è necessario il design con free list illustrato nella lezione successiva.
Verifica rapida
Consideri come un bump allocator recupera la memoria.
Riepilogo
Un bump allocator distribuisce la memoria facendo avanzare un unico offset attraverso un buffer, rendendo l'allocazione economica quanto un'addizione a un puntatore.
Rinuncia alla liberazione dei singoli blocchi in cambio di velocità e semplicità, recuperando la memoria solo tramite un reset completo. Allinei l'offset per mantenere validi per tutti i tipi i puntatori restituiti.
Domande Frequenti
La lezione «Un semplice allocatore bump» è gratuita?
Sì — il testo completo di «Un semplice allocatore bump» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.
Cosa imparerò in «Un semplice allocatore bump»?
Distribuisca la memoria in modo lineare. Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare C Academy?
Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Un semplice allocatore bump»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione C Academy?
Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Come funziona malloc
- Un semplice allocatore bump
- Free list e riutilizzo
- Allineamento e suddivisione