«Преждевременная оптимизация — корень всех зол, но преждевременная пессимизация является им не в меньшей степени». — Андрей Александреску
Проблема перераспределения
Динамические массивы (векторы C++, ArrayList в Java) — одна из самых полезных структур данных. Они сочетают в себе удобство для кэша, присущее массивам, с гибкостью динамического изменения размера.
Однако у них есть скрытые затраты, связанные с перераспределением.
Однажды я работал над агрегатором логов встраиваемой системы. Система накапливала сообщения логов в динамическом массиве и периодически скидывала их на флэш-накопитель. Кажется, всё просто, не так ли?
Но производительность была ужасной. Система тратила 60% времени на realloc().
Проблема заключалась в том, что массив разрастался по одному элементу за раз:
typedef struct { char **messages; int size; int capacity; } log_buffer_t; void add_message(log_buffer_t *buf, const char *msg) { if (buf->size >= buf->capacity) { buf->capacity++; // Увеличение на 1! buf->messages = realloc(buf->messages, buf->capacity * sizeof(char*)); } buf->messages[buf->size++] = strdup(msg); }
Для 1000 сообщений: 1000 перераспределений, каждое из которых копировало весь массив.
Общее количество копирований: 1 + 2 + 3 + ... + 1000 = всего копировалось 500500 элементов!
Решение проблемы было простым: выполнять увеличение экспоненциально, а не линейно.
void add_message(log_buffer_t *buf, const char *msg) { if (buf->size >= buf->capacity) { buf->capacity = buf->capacity ? buf->capacity * 2 : 16; buf->messages = realloc(buf->messages, buf->capacity * sizeof(char*)); } buf->messages[buf->size++] = strdup(msg); }
Для 1000 сообщений: 7 перераспределений (16, 32, 64, 128, 256, 512, 1024).
Общее количество копирований: ~2000 элементов (а не 500500).
Результат: в 250 меньше копий, в 60 раз быстрее.
Визуализация экспоненциального роста:
Исходное состояние: ┌────────────────────────┐ │ Размер: 0, Ёмкость: 0 │ └────────────────────────┘ Добавляем элемент 1 → Распределяем исходную ёмкость ┌────────────────────────┐ │ Размер: 1, Ёмкость: 16 │ ✅ Распределено └────────────────────────┘ Добавляем элементы 2-16 → Перераспределение не выполняется ┌─────────────────────────┐ │ Размер: 16, Ёмкость: 16 │ ⚠️ Заполнено └─────────────────────────┘ Добавляем элемент 17 → Перераспределение (16 → 32) ┌─────────────────────────┐ │ Размер: 17, Ёмкость: 32 │ ✅ Перераспределено (копирование 16 элементов) └─────────────────────────┘ Добавляем элементы 18-32 → Перераспределение не выполняется ┌─────────────────────────┐ │ Размер: 32, Ёмкость: 32 │ ⚠️ Заполнено └─────────────────────────┘ Добавляем элемент 33 → Перераспределение (32 → 64) ┌─────────────────────────┐ │ Размер: 33, Ёмкость: 64 │ ✅ Перераспределено (копирование 32 элементов) └─────────────────────────┘ Продолжение... ┌────────────────────────────┐ │ Размер: 64, Ёмкость: 64 │ → Перераспределено до 128 │ Размер: 128, Ёмкость: 128 │ → Перераспределено до 256 │ Размер: 256, Ёмкость: 256 │ → Перераспределено до 512 │ Размер: 512, Ёмкость: 512 │ → Перераспределено до 1024 └────────────────────────────┘ Окончательное состояние (1000 элементов): ┌──────────────────────────────┐ │ Размер: 1000, Ёмкость: 1024 │ ✅ Всего примерно 10 перераспределений └──────────────────────────────┘ Общее количество перераспределений: 10 (против 1000 при увеличении массива по 1 элементу) Общее количество копирований: около 2000 элементов (против 500500)
Применение этой стратегии в реальном мире:
Паттерн «распределение лишнего места, чтобы избежать частых затратных операций» встречается во многих системах:
Построители строк (Java
StringBuilder, C#StringBuilder): экспоненциальный рост, чтобы избежать конкатенации строк за O(n²).Сетевые буферы (буферы приёма TCP): предварительное распределение больших буферов для снижения количества системных вызовов.
Распределители памяти (реализации malloc): используют классы размеров (16, 32, 64, 128...) для снижения фрагментации.
Логи транзакций баз данных: выполняют предварительное распределение пространства логов блоками, чтобы избежать частого дискового ввода-вывода.
Разреженные матрицы (научные вычисления): распределяют дополнительную ёмкость в хранилище сжатых строк, чтобы обеспечить возможность эффективных вставок.
Файловые системы (ext4, XFS): выполняют предварительное распределение блоков увеличивающихся файлов с целью снижения фрагментации.
Главный вывод: увеличение пространства для снижения времени избыточным распределением снижает амортизированные затраты на рост с O(n) до O(1).
Реализация динамических массивов
Вот, как выглядит реализация динамического мас��ива:
typedef struct { int *data; size_t size; // Количество элементов size_t capacity; // Распределённое пространство } vector_t; void vector_init(vector_t *v) { v->data = NULL; v->size = 0; v->capacity = 0; } void vector_free(vector_t *v) { free(v->data); v->data = NULL; v->size = 0; v->capacity = 0; } void vector_push(vector_t *v, int value) { if (v->size >= v->capacity) { size_t new_capacity = v->capacity ? v->capacity * 2 : 16; int *new_data = realloc(v->data, new_capacity * sizeof(int)); if (!new_data) { // Обработка сбоя распределения return; } v->data = new_data; v->capacity = new_capacity; } v->data[v->size++] = value; } int vector_pop(vector_t *v) { if (v->size > 0) { return v->data[--v->size]; } return -1; // Ошибка } int vector_get(vector_t *v, size_t index) { if (index < v->size) { return v->data[index]; } return -1; // Ошибка }
Главные архитектурные решения:
Исходная ёмкость: 16 (избегаем малых распределений).
Коэффициент роста: 2× (экспоненциальный рост).
realloc(): может избежать копирования, если есть место.
Анализ коэффициента роста
Коэффициент роста влияет и на объём используемой памяти, и на производительность.
Часто используемые коэффициенты роста:
1,5×: применяется в некоторых реализациях (например, в библиотеке Facebook folly).
2×: самый распространённый (std::vector языка C++, list языка Python).
φ (1,618): золотое сечение, теоретический оптимум.
Компромиссы:
Рост 2×:
Плюсы: простой, быстрый (битовый сдвиг), хорошая амортизированная производительность.
Минусы: может впустую тратить до 50% памяти.
Рост 1,5×:
Плюсы: меньше пустой траты памяти (примерно 33%), более оптимальное повторное использование памяти.
Минусы: больше перераспределений, чуть медленнее.
Бенчмарк (рост до 1 миллиона элементов):
Коэффициент роста 1,5×: Перераспределения: 34 Пиковый объём памяти: 1,5 МБ Время: 12 мс Коэффициент роста 2×: Перераспределения: 20 Пиковый объём памяти: 2 МБ Время: 8 мс
В 2 раза быстрее (меньше перераспределений), но требует больше памяти.
Рекомендация: если память не в дефиците, использовать 2×.
Уменьшение размеров: когда освобождать память
Следует ли уменьшать размер массива при удалении элементов?
Наивный подход: уменьшение при каждом удалении
void vector_pop(vector_t *v) { if (v->size > 0) { v->size--; if (v->size < v->capacity / 2) { v->capacity /= 2; v->data = realloc(v->data, v->capacity * sizeof(int)); } } }
Проблема: скачки при удалении/добавлении рядом с границей ёмкости
Добавление до 1024 → ёмкость 1024 Удаление до 512 → уменьшение до 512 Добавление до 513 → рост до 1024 Удаление до 512 → уменьшение до 512 ...
Более оптимальное решение: гистерезис (уменьшение на 1/4, а не на 1/2)
void vector_pop(vector_t *v) { if (v->size > 0) { v->size--; if (v->size < v->capacity / 4 && v->capacity > 16) { v->capacity /= 2; v->data = realloc(v->data, v->capacity * sizeof(int)); } } }
В этом случае: необходимо выполнить удаление до 256 элементов, прежде чем произойдёт уменьшение массива с 1024.
Ещё лучше: не выполнять уменьшение массива автоматически, создать явную функцию vector_shrink_to_fit().
void vector_shrink_to_fit(vector_t *v) { if (v->size < v->capacity) { v->data = realloc(v->data, v->size * sizeof(int)); v->capacity = v->size; } }
Рекомендация: если память не критична, не выполнять автоматическое уменьшение массива.
Резервирование и ёмкость
Если окончательный размер известен заранее, то заблаговременно резервируйте пространство:
void vector_reserve(vector_t *v, size_t capacity) { if (capacity > v->capacity) { int *new_data = realloc(v->data, capacity * sizeof(int)); if (new_data) { v->data = new_data; v->capacity = capacity; } } } // Применение vector_t v; vector_init(&v); vector_reserve(&v, 1000); // Распределение выполняется один раз for (int i = 0; i < 1000; i++) { vector_push(&v, i); // Перераспределения нет! }
Бенчмарк (1000 элементов):
Без резервирования: Перераспределения: 7 Время: 45 мкс С резервированием: Перераспределения: 1 Время: 12 мкс
В 3,75 раза быстрее благодаря отсутствию перераспределений.
Рекомендация: если размер известен, всегда выполняйте резервирование.
Оптимизация малых векторов
В случае малых векторов преобладающим оказывается оверхед распределения кучи.
Оптимизация малых векторов: малые массивы следует хранить встраиваемым образом и выполнять распределение только для больших массивов.
#define SMALL_SIZE 16 typedef struct { int small_data[SMALL_SIZE]; // Встроенное хранилище int *data; // Хранилище в куче (если необходимо) size_t size; size_t capacity; } small_vector_t; void small_vector_init(small_vector_t *v) { v->data = v->small_data; // Начинаем со встроенного хранилища v->size = 0; v->capacity = SMALL_SIZE; } void small_vector_push(small_vector_t *v, int value) { if (v->size >= v->capacity) { size_t new_capacity = v->capacity * 2; int *new_data = malloc(new_capacity * sizeof(int)); // Копирование из встроенного хранилища или кучи memcpy(new_data, v->data, v->size * sizeof(int)); // Освобождение старого хранилища в куче (если есть) if (v->data != v->small_data) { free(v->data); } v->data = new_data; v->capacity = new_capacity; } v->data[v->size++] = value; } void small_vector_free(small_vector_t *v) { if (v->data != v->small_data) { free(v->data); } }
Преимущества:
Отсутствие распределений в случае малых векторов (≤ 16 элементов).
Повышенная локальность кэша (встраивание данных с помощью struct).
Высокая скорость в общем случае.
Затраты:
Увеличенный размер struct (64 байт против 16 байт).
Одно лишнее копирование при переходе к куче.
Бенчмарк (средний размер: 8 элементов):
Обычный вектор: Распределения: 1 на вектор Время: 850 нс на вектор Малый вектор: Распределения: 0 (встроенное хранение) Время: 120 нс на вектор
В 7 раз быстрее для малых векторов.
Рекомендация: используйте оптимизацию малых векторов для векторов, которые обычно имеют небольшой размер (< 16-32 элементов).
Распределитель памяти
Производительность realloc() зависит от распределителя.
Наилучший случай: распределитель может расширять объём на месте (без копирования)
// Распределение 1 КБ void *ptr = malloc(1024); // Расширение до 2 КБ (может расширяться на месте) ptr = realloc(ptr, 2048); // Если пространство есть, копирование отсутствует
Наихудший случай: необходимо распределить новый блок и выполнить копирование
// Распределение 1 КБ void *ptr = malloc(1024); // Другое распределение использует соседнее пространство void *other = malloc(1024); // Теперь realloc должна выполнить копирование ptr = realloc(ptr, 2048); // Необходимо распределить новый блок и выполнить копирование
Встраиваемые системы: часто используют простые распределители, которые не могут расширяться на месте.
Решение: использовать специализированный распределитель или пул памяти
typedef struct { char pool[64 * 1024]; // Пул 64 КБ size_t used; } memory_pool_t; memory_pool_t global_pool = {0}; void *pool_alloc(size_t size) { if (global_pool.used + size > sizeof(global_pool.pool)) { return NULL; // Память закончилась } void *ptr = &global_pool.pool[global_pool.used]; global_pool.used += size; return ptr; } // Невозможно освободить отдельные распределения, но можно сбросить весь пул void pool_reset(void) { global_pool.used = 0; }
Сценарий использования: временные векторы, которые можно освобождать вместе.
Вставка и удаление
Для вставки и удаления в середине требуется сдвиг элементов.
Вставка по индексу:
void vector_insert(vector_t *v, size_t index, int value) { if (index > v->size) return; // Обеспечение достаточной ёмкости if (v->size >= v->capacity) { size_t new_capacity = v->capacity ? v->capacity * 2 : 16; v->data = realloc(v->data, new_capacity * sizeof(int)); v->capacity = new_capacity; } // Сдвиг элементов вправо memmove(&v->data[index + 1], &v->data[index], (v->size - index) * sizeof(int)); v->data[index] = value; v->size++; }
Удаление по индексу:
void vector_delete(vector_t *v, size_t index) { if (index >= v->size) return; // Сдвиг элементов влево memmove(&v->data[index], &v->data[index + 1], (v->size - index - 1) * sizeof(int)); v->size--; }
Производительность:
Вставка/удаление в конце: O(1)
Вставка/удаление в начале: O(n) (необходимо сдвинуть все элементы)
Вставка/удаление в середине: O(n)
Бенчмарк (1000 элементов):
Вставка в конце: 50 нс Вставка в начале: 12000 нс (в 240 раз медленнее) Вставка в середине: 6000 нс (в 120 раз медленнее)
Рекомендация: если вам нужны частые вставки/удаления в середине, то задумайтесь о применении другой структуры данных (например, связанного списка или буферного окна).
Встраиваемые системы: векторы с фиксированной ёмкостью
Во встраиваемых системах использование динамического распределения часто недопустимо.
Вектор с фиксированной ёмкостью:
#define MAX_CAPACITY 256 typedef struct { int data[MAX_CAPACITY]; size_t size; } fixed_vector_t; void fixed_vector_init(fixed_vector_t *v) { v->size = 0; } int fixed_vector_push(fixed_vector_t *v, int value) { if (v->size >= MAX_CAPACITY) { return -1; // Заполнен } v->data[v->size++] = value; return 0; }
Преимущества:
Отсутствие распределения.
Предсказуемый объём занимаемой памяти.
Быстрый (нет перераспределения).
Простой.
Затраты:
Фиксированный максимальный размер.
Может тратить память впустую, если не заполнен.
Рекомендация: если вам не требуется динамическое изменение размеров, во встраиваемых системах используйте векторы с фиксированной ёмкостью.
Пример из реального мира: оптимизация буфера логов
Вернёмся к моему агрегатору логов. Вот, как выглядит оптимизация целиком:
До (увеличение размера на 1):
typedef struct { char **messages; int size; int capacity; } log_buffer_t; void add_message(log_buffer_t *buf, const char *msg) { if (buf->size >= buf->capacity) { buf->capacity++; buf->messages = realloc(buf->messages, buf->capacity * sizeof(char*)); } buf->messages[buf->size++] = strdup(msg); }
Проблемы:
1000 перераспределений для 1000 сообщений.
Копирование 500500 элементов.
Ужасная производительность.
После (экспоненциальный рост + резервирование):
typedef struct { char **messages; int size; int capacity; } log_buffer_t; void log_buffer_init(log_buffer_t *buf, int expected_size) { buf->messages = malloc(expected_size * sizeof(char*)); buf->size = 0; buf->capacity = expected_size; } void add_message(log_buffer_t *buf, const char *msg) { if (buf->size >= buf->capacity) { buf->capacity *= 2; buf->messages = realloc(buf->messages, buf->capacity * sizeof(char*)); } buf->messages[buf->size++] = strdup(msg); }
Улучшения:
Предварительное резервирование ожидаемого размера.
Экспоненциальный рост при превышении ёмкости.
7 перераспределений (против 1000).
Копирование 2000 элементов (против 500500).
Результат: в 60 раз быстрее, с 60% CPU до < 1% CPU.
Буферное окно (gap buffer): эффективное редактирование текста
Текстовым редакторам нужны эффективные вставки/удаления в позиции курсора.
Проблемы динамического массива: вставки в позиции курсора требуют сдвига всего текста после курсора.
Решение: буферное окно (используется в Emacs)
typedef struct { char *buffer; size_t gap_start; // Начало окна size_t gap_end; // Конец окна size_t capacity; } gap_buffer_t; void gap_buffer_init(gap_buffer_t *gb, size_t capacity) { gb->buffer = malloc(capacity); gb->gap_start = 0; gb->gap_end = capacity; gb->capacity = capacity; } void gap_buffer_insert(gap_buffer_t *gb, char c) { if (gb->gap_start >= gb->gap_end) { // Увеличение буфера (удвоение размера) size_t new_capacity = gb->capacity * 2; char *new_buffer = malloc(new_capacity); // Копирование перед окном memcpy(new_buffer, gb->buffer, gb->gap_start); // Копирование после окна size_t after_gap = gb->capacity - gb->gap_end; memcpy(new_buffer + new_capacity - after_gap, gb->buffer + gb->gap_end, after_gap); free(gb->buffer); gb->buffer = new_buffer; gb->gap_end = new_capacity - after_gap; gb->capacity = new_capacity; } gb->buffer[gb->gap_start++] = c; } void gap_buffer_move_cursor(gap_buffer_t *gb, int new_pos) { if (new_pos < gb->gap_start) { // Сдвиг окна влево size_t move = gb->gap_start - new_pos; memmove(&gb->buffer[gb->gap_end - move], &gb->buffer[new_pos], move); gb->gap_start = new_pos; gb->gap_end -= move; } else if (new_pos > gb->gap_start) { // Сдвиг окна вправо size_t move = new_pos - gb->gap_start; memmove(&gb->buffer[gb->gap_start], &gb->buffer[gb->gap_end], move); gb->gap_start += move; gb->gap_end += move; } }
Как это работает:
Исходное состояние (ёмкость 10): [_, _, _, _, _, _, _, _, _, _] ^gap_start ^gap_end Вставка "abc": [a, b, c, _, _, _, _, _, _, _] ^gap_start ^gap_end Перемещение курсора в 1: [a, _, _, _, _, _, _, b, c, _] ^gap_start ^gap_end Вставка "x": [a, x, _, _, _, _, _, b, c, _] ^gap_start ^gap_end
Преимущества:
Вставка в позиции курсора за O(1) (достаточно переместить gap_start).
Удаление в позиции курсора за O(1).
Затраты только на перемещение курсора (амортизированное O(1) для последовательного редактирования).
Бенчмарк (1000 вставок в позиции курсора):
Динамический массив: 12000 мкс (сдвиг при каждой вставке) Буферное окно: 120 мкс (в 100 раз быстрее)
Подведём итог
Проблема перераспределения была решена благодаря пониманию стратегий роста. Агрегатор логов, тративший 60% своего времени на realloc(), разрастался по одному элементу за раз, из-за чего при всего 1000 элементов копировалось 500500 элементов. Переход на экспоненциальный рост (удвоение ёмкости) снизил количество перераспределений с 1000 до всего 10, что сильно повысило скорость системы.
Ключевые выводы:
Экспоненциальный рост (2×) для амортизированного добавления за O(1).
Резервирование пространства, если известен размер.
Не нужно выполнять автоматическое уменьшение размера (используйте shrink_to_fit).
Оптимизация малых векторов в общем случае.
Фиксированная ёмкость для встраиваемых систем.
Стратегии роста:
Рост 2×: меньше перераспределений, больше памяти.
Рост 1,5×: больше перераспределений, меньше памяти.
Рекомендация: если память не критична, используйте 2×.
Оптимизации:
Резервирование: если размер известен, избегаем перераспределений.
Оптимизация малых векторов: встроенное хранилище для малых массивов.
Пулы памяти: избегаем оверхеда распределителя.
Буферное окно: эффективное редактирование текста.
Встраиваемые системы:
Векторы с фиксированной ёмкостью (без распределения).
Предсказуемый объём памяти.
Простые распределители не могут выполнять расширение на месте.
Стоит рассмотреть возможность использования пулов памяти.
Когда использовать динамические массивы:
Необходимость переменного размера.
В основном применяются операции добавления.
Требуется произвольный доступ.
Удобный для кэша последовательный доступ.
Когда их НЕ использовать:
Частые вставки/удаления в середине → буферное окно или rope.
Известен фиксированный размер → статический массив.
Встраиваемая система с дефицитом памяти → вектор с фиксированной ёмкостью.
Дальнейшие шаги: мы рассмотрели фундаментальные структуры данных (массивы, списки, стеки, очереди, хэш-таблицы динамические массивы). В следующей части мы исследуем деревья и иерархические структуры, в которых поведение кэша становится ещё более критичным.
