Простой линейный распределитель
Выделяйте память последовательно.
«Простой линейный распределитель» — бесплатный урок C Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.
Идея распределителя bump_alloc
Распределитель bump_alloc (или аренный распределитель) — это простейшая конструкция. Вы храните один большой буфер и одно смещение. Каждое выделение просто возвращает текущее смещение, а затем «сдвигает» его вперёд на запрошенный размер.
Метаданных для отдельных блоков и поиска нет. Выделение сводится практически к одному сложению указателей, поэтому работает чрезвычайно быстро.
Статический буфер-основа
В самостоятельном примере мы обеспечиваем распределитель статическим массивом вместо кучи OS. Программа компилируется и работает где угодно, без sbrk и mmap.
Массив даёт нам фиксированный пул байтов, который можно разделять на части.
#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;Основная функция bump_alloc
Выделение проверяет, осталось ли достаточно места, сохраняет начало, сдвигает смещение и возвращает указатель на начало. Если запрос превысит размер пула, функция возвращает NULL.
Эта проверка переполнения — единственная мера безопасности, которую предоставляет распределитель bump_alloc.
void *bump_alloc(size_t size) {
if (offset + size > POOL_SIZE)
return NULL; /* out of pool */
void *p = &pool[offset];
offset += size;
return p;
}Полностью рабочий распределитель bump_alloc
Перед вами полноценная программа. Она выделяет из пула два целых числа и короткую строку, а затем выводит их, подтверждая работу распределителя.
Обратите внимание, насколько мало кода требуется по сравнению с настоящим 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;
}Нельзя освобождать отдельные блоки
Но есть ограничение: распределитель bump_alloc не может освободить отдельное выделение. Поскольку метаданных нет, он не знает, где заканчивается один блок и начинается следующий, чтобы повторно использовать память.
Можно только сбросить всю арену сразу, установив смещение обратно в ноль.
void bump_reset(void) {
offset = 0; /* frees everything at once */
}Почему сброс полезен
Такая модель «всё или ничего» идеально подходит для работы по фазам: выделяйте множество объектов во время запроса или кадра, а затем сбрасывайте арену по завершении фазы.
Игровые движки и компиляторы активно используют арены, потому что сброс выполняется за O(1) и избавляет от необходимости отслеживать тысячи отдельных освобождений.
/* Per-frame pattern */
for (int frame = 0; frame < 3; frame++) {
void *tmp = bump_alloc(128);
/* ... use tmp this frame ... */
bump_reset(); /* reclaim instantly */
}Отслеживание оставшегося пространства
Полезно показывать, сколько места осталось. Это просто размер пула минус текущее смещение.
Вызывающий код может использовать это, чтобы решить, нужно ли выполнить сброс или увеличить пул перед запросом дополнительного места.
size_t bump_remaining(void) {
return POOL_SIZE - offset;
}Рабочая демонстрация сброса
Эта программа заполняет часть пула, выводит информацию об использовании, выполняет сброс и показывает, что смещение возвращается к нулю, поэтому пространство можно использовать снова.
#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;
}Выравнивание в bump-распределителе
Побайтовое продвижение может возвращать невыравненные указатели. Для безопасности перед возвратом указателя округляйте смещение вверх до границы выравнивания.
Математику мы подробно разберём позже, но именно в bump-распределителе выравнивание особенно важно, поскольку иначе дополнения нет.
static size_t align_up(size_t n, size_t a) {
return (n + a - 1) & ~(a - 1); /* a must be power of 2 */
}Выровненный bump-распределитель
Объединив эти части, мы выравниваем смещение перед каждым выделением. Это гарантирует, что каждый возвращённый указатель подходит для любого распространённого типа.
Цена этого решения — небольшая внутренняя фрагментация из-за байтов дополнения.
#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;
}Преимущества и ограничения
Bump-распределители исключительно быстры и предельно просты, а накладные расходы на каждый объект равны нулю. Они идеально подходят, когда объекты имеют одинаковое время жизни.
Их недостаток — отсутствие освобождения отдельных объектов. Если времена жизни различаются, потребуется реализация со списком свободных блоков, которую мы рассмотрим на следующем уроке.
Быстрая проверка
Подумайте, как bump-распределитель возвращает память.
Итоги
Bump-распределитель выдаёт память, продвигая одно смещение по буферу, поэтому выделение обходится так же дёшево, как сложение с указателем.
Он отказывается от индивидуального освобождения ради скорости и простоты и возвращает память только посредством полного сброса. Выравнивайте смещение, чтобы возвращённые указатели оставались допустимыми для всех типов.
Часто задаваемые вопросы
Урок «Простой линейный распределитель» бесплатный?
Да — полный текст урока «Простой линейный распределитель» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.
Чему я научусь в уроке «Простой линейный распределитель»?
Выделяйте память последовательно. Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать C Academy?
Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Простой линейный распределитель»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке C Academy?
Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Как работает malloc
- Простой линейный распределитель
- Списки свободной памяти и повторное использование
- Выравнивание и разделение