Что такое фрагментация кучи?

Что такое фрагментация кучи

Фрагментация кучи (heap fragmentation) — это явление, когда память в куче становится разбита на множество мелких кусков, и хотя свободной памяти достаточно, её невозможно использовать, потому что нет одного большого непрерывного блока нужного размера.

Как это выглядит

Идеальное состояние (без фрагментации):

Куча: [Объект1][Объект2][Объект3][==========СВОБОДНАЯ ПАМЯТЬ========]
      Процесс может выделить любой размер

Фрагментированная куча:

Куча: [Obj1][свобода][Obj2][свобода][Obj3][свобода][Obj4][свобода]...
      4KB    2KB    4KB   1KB    4KB   3KB   4KB   2KB
      
      Всего свободно: 8KB
      Но нельзя выделить 5KB единовременно!

Типы фрагментации

1. Внешняя фрагментация (External Fragmentation):

Свободные блоки разбросаны, но суммарно памяти достаточно:

char* p1 = new char[100];   // 100 байт
char* p2 = new char[100];   // 100 байт
char* p3 = new char[100];   // 100 байт

delete[] p1;                // Оставляет 100 байт свободно
delete[] p3;                // Оставляет 100 байт свободно

char* p4 = new char[150];   // ОШИБКА! Нет непрерывного блока 150 байт
                            // Хотя свободно 200 байт

Визуально:

ДО:  [100][100][100]
ПОСЛЕ: [свобода][100][свобода]
       
       Хотим 150 байт → FAIL (нет одного куска)

2. Внутренняя фрагментация (Internal Fragmentation):

Аллокатор выделяет больше памяти, чем нужно:

char* p = new char[3];      // Просим 3 байта
                            // Но аллокатор выделяет 16 байт (по размеру блока)
                            // Потеряны 13 байт!

struct Data {
    char a;     // 1 байт
    // 3 байта padding для выравнивания
    int b;      // 4 байта
    char c;     // 1 байт  
    // 3 байта padding
};  // sizeof(Data) = 12, хотя нужно 6

Причины фрагментации

1. Различные размеры объектов:

new int[100];       // 400 байт
delete[] ...;       // Оставляет дырку 400 байт

new char[150];      // 150 байт
delete[] ...;       // Оставляет дырку 150 байт

new int[200];       // Хочет 800 байт
                    // Есть дырки 400+150, но они не смежны!

2. Долгоживущие объекты среди коротких:

void fragment_example() {
    // Выделяем долгоживущий объект
    LongLivedObject* long_obj = new LongLivedObject();  // 1000 байт
    
    while (true) {
        // Выделяем и удаляем короткие объекты
        char* temp = new char[100];
        delete[] temp;
        // Оставляет дырку 100 байт
        
        char* temp2 = new char[50];
        delete[] temp2;
        // Оставляет дырку 50 байт
    }
    
    // Со временем вокруг long_obj полно мелких дырок
    // Невозможно выделить блок > 100 байт
}

Влияние на производительность

1. Out of Memory (OOM) ошибки:

char* p = malloc(1000000);  // Просим 1MB
                            // Но heap фрагментирован
                            // Нет одного куска 1MB
                            // → malloc возвращает NULL
                            // → Crash или исключение

// Хотя свободно несколько GiB памяти!

2. TLB (Translation Lookaside Buffer) misses:

Если объекты разбросаны в памяти, CPU cache работает плохо:

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

// При фрагментации следующий узел может быть на совсем другой странице
Node* n1 = new Node();  // Страница 0x1000
Node* n2 = new Node();  // Страница 0x5000 ← далеко!
Node* n3 = new Node();  // Страница 0x2000

// Много TLB misses → медленно

3. Увеличение рабочего набора памяти (Working Set):

Линейный скан фрагментированного массива требует больше страничных переходов.

Виды аллокаторов и фрагментация

Простой аллокатор (malloc/free):

• Подвержен внешней фрагментации
• Может выглядеть примерно так:

struct Block {
    size_t size;
    bool is_free;
    Block* next;
};

void* malloc(size_t size) {
    for (Block* b = free_list; b; b = b->next) {
        if (b->size >= size) {
            // Нашли свободный блок
            if (b->size > size) {
                // Разбиваем блок
                Block* new_block = (Block*)((char*)b + size);
                new_block->size = b->size - size;
                new_block->is_free = true;
                new_block->next = b->next;
                b->next = new_block;
            }
            b->is_free = false;
            return (char*)b + sizeof(Block);
        }
    }
    return NULL;  // OOM
}

Pool-based аллокатор:

• Выделяет память предзаказанными блоками одинакового размера
• Минимизирует фрагментацию

class MemoryPool {
private:
    const size_t BLOCK_SIZE = 256;
    std::list<void*> free_blocks;
    
public:
    MemoryPool(size_t num_blocks) {
        for (size_t i = 0; i < num_blocks; i++) {
            free_blocks.push_back(malloc(BLOCK_SIZE));
        }
    }
    
    void* allocate() {
        if (free_blocks.empty()) return NULL;
        void* block = free_blocks.front();
        free_blocks.pop_front();
        return block;
    }
    
    void deallocate(void* ptr) {
        free_blocks.push_back(ptr);
    }
};

Как обнаружить фрагментацию

1. Инструменты профилирования:

# Valgrind показывает статистику памяти
valgrind --leak-check=full --show-leak-kinds=all ./program

# Linux: посмотрим /proc/self/maps
cat /proc/self/maps

# macOS: использовать Instruments
instruments -t Memory ./program

2. Запрограммированная проверка:

void check_memory_fragmentation() {
    size_t total_allocated = 0;
    size_t num_blocks = 0;
    size_t largest_free = 0;
    
    // Попытаемся выделить блоки увеличивающегося размера
    for (size_t size = 1024; size <= 10*1024*1024; size *= 2) {
        void* p = malloc(size);
        if (!p) {
            std::cout << "Не удалось выделить " << size << " байт" << std::endl;
            std::cout << "Фрагментация!
        } else {
            free(p);
            largest_free = size;
        }
    }
}

Стратегии борьбы с фрагментацией

1. Используй memory pools для однотипных объектов:

Pool<Node> node_pool(10000);
Node* n = node_pool.allocate();
node_pool.deallocate(n);

1. Выделяй блоки одинакового размера:

std::vector<std::vector<char>> chunks;
chunks.push_back(std::vector<char>(1024));  // 1KB блоки

1. Используй arena allocators для временных данных:

class Arena {
    char* buffer;
    size_t offset = 0;
    
public:
    void* allocate(size_t size) {
        void* ptr = buffer + offset;
        offset += size;
        return ptr;
    }
    
    void reset() { offset = 0; }  // Всё разом удалить
};

1. Рассмотри jemalloc или tcmalloc вместо стандартного malloc:

// tcmalloc от Google лучше справляется с фрагментацией
// Используется в высоконагруженных системах

1. Дефрагментируй память явно (сложно, но возможно):

// Переместить объекты в последовательные области памяти
// Как это делает Java GC

Практические рекомендации для backend разработчика

1. Мониторь потребление памяти — если оно растёт без причины, возможна фрагментация
2. Используй RAII — уменьшает шансы утечек и фрагментации
3. Профилируй на real данных — фрагментация проявляется при scale
4. Рассмотри jemalloc — существенно лучше для высоконагруженных систем
5. Избегай частого malloc/free в горячих путях — используй pools или arenas

Фрагментация кучи — это тихая проблема, которая может неожиданно упасть систему в production при масштабировании.