Бенчмаркинг структур данных: теория против практики

Почему бенчмаркинг структур данных — это важно

Вы знаете, что поиск в массиве — это O(n), а в хеш-таблице — O(1). Но что если на практике массив из 50 элементов обходит хеш-таблицу? В этой статье я расскажу, как я построил бенчмаркинг-сьют на C++ и какие уроки извлек. Вы узнаете, почему теория и практика расходятся, и как правильно измерять производительность.

Цель проекта: сравнить массивы, списки и хеш-таблицы

Я хотел создать учебный проект, который реализует динамические массивы, связные списки и хеш-таблицы с нуля, бенчмаркает операции вставки, поиска и удаления, находит точки пересечения производительности и экспортирует результаты в CSV. Звучит просто? Через четыре месяца у меня был кастомный трекер памяти, несколько стратегий хеширования, бутстрэп для доверительных интервалов и глубокое понимание кэшей CPU.

Урок 1: Полиморфизм имеет цену (но оно того стоит)

Первое архитектурное решение — общий интерфейс DataStructure:

class DataStructure {
public:
    virtual void insert(int key, const std::string& value) = 0;
    virtual bool search(int key, std::string& value) const = 0;
    virtual bool remove(int key) = 0;
    virtual size_t memory_usage() const = 0;
    virtual std::string type_name() const = 0;
    // ...
};

Это делает бенчмаркинг элегантным: можно писать обобщенный код для любой структуры:

for (auto& structure : structures) {
    timer.start();
    structure->insert(key, value);
    timer.stop();
}

Но виртуальные вызовы имеют накладные расходы. В тесных циклах поиск по vtable накапливается. Я потратил выходные, думая, что хеш-таблица медленнее, чем ожидалось... пока не понял, что измеряю стоимость полиморфизма, а не самой структуры. Решение: оставил чистый интерфейс для харнесса, но внутри использовал шаблоны для критичных к производительности участков. Полиморфный интерфейс все равно оправдан для поддерживаемости и легкого добавления новых структур.

Урок 2: Бенчмаркинг сложнее, чем кажется

Мой первый таймер был наивным:

auto start = std::chrono::high_resolution_clock::now();
do_operation();
auto end = std::chrono::high_resolution_clock::now();

Числа прыгали: некоторые запуски были в 10 раз быстрее других. В чем дело?

Проблема 1: Прогрев важен. Первые запуски всегда медленнее, потому что кэши CPU холодные, а предсказатель ветвлений еще не обучился. Я добавил настраиваемый прогрев:

template <typename Func>
void warmup(size_t warmup_count, Func&& operation) {
    for (size_t i = 0; i < warmup_count; ++i) {
        operation();
    }
    std::this_thread::sleep_for(std::chrono::milliseconds(1));
}

Проблема 2: Выбросы разрушают среднее. Тот запуск, когда ОС решила запустить сборку мусора? Он все испортит. Я реализовал автоматическое обнаружение выбросов с помощью Z-оценок:

// Удаляем выборки, отклоняющиеся более чем на 2 стандартных отклонения
std::vector<duration> remove_outliers(const std::vector<duration>& data) const;

Проблема 3: Масштабирование частоты CPU. Современные процессоры постоянно повышают и понижают частоту. Я добавил опции для привязки к ядру CPU и (на Linux) попытку зафиксировать губернатор CPU.

Проблема 4: Нужно больше, чем среднее. Отчет только среднего ± стандартное отклонение недостаточен. Я реализовал:

• Медиану и 95-й перцентиль
• Бутстрэп-доверительные интервалы
• Несколько форматов вывода (CSV и JSON)

JSON-вывод теперь включает метаданные об оборудовании, SHA коммита git и сид, использованный для случайных паттернов — потому что воспроизводимость важна.

Урок 3: Стратегии роста — это кроличья нора

Реализуя DynamicArray, я думал просто удваивать емкость при заполнении. Классическая амортизированная вставка O(1). Но потом задумался: а что если использовать рост 1.5x? А числа Фибоначчи? А фиксированные приращения? Я реализовал все четыре:

enum class GrowthStrategy {
    MULTIPLICATIVE_2_0, // коэффициент роста 2.0
    MULTIPLICATIVE_1_5, // коэффициент роста 1.5
    FIBONACCI,          // рост по Фибоначчи
    ADDITIVE            // фиксированный прирост
};

И вот результаты бенчмарков:

• 2.0x — самый быстрый для чистой вставки
• 1.5x — использует в среднем на 25% меньше памяти
• Фибоначчи — это по сути рост 1.618x с лишней сложностью
• Аддитивный — ужасен для больших массивов (как и ожидалось)

Интересный вывод: для большинства реальных задач, где вы не вставляете миллионы элементов, разница незначительна. Очевидный выбор — удвоение — обычно достаточен.

Урок 4: Хеш-таблицы имеют скрытую сложность

Я реализовал две стратегии хеширования: открытую адресацию (линейное пробирование) и метод цепочек. Я думал, что открытая адресация выиграет из-за лучшей локальности кэша. Реальность оказалась тоньше:

enum class HashStrategy {
    OPEN_ADDRESSING,
    SEPARATE_CHAINING
};

Открытая адресация выигрывает, когда:

• Коэффициент заполнения низкий (~0.7)
• Ключи хорошо распределены
• Преобладают операции поиска

Метод цепочек выигрывает, когда:

• Есть кластеризация из-за плохого распределения хешей
• Часто происходит удаление (томбстоуны вредят открытой адресации)
• Коэффициент заполнения высокий

Проблема томбстоунов особенно коварна. При удалении из хеш-таблицы с открытой адресацией нельзя просто пометить ячейку как пустую — будущие пробы могли пропустить ее. Поэтому помечаем как «томбстоун», но слишком много томбстоунов ухудшают производительность так же, как и коллизии. Я добавил отслеживание количества проб на операцию:

double insert_probes_mean {0.0};
double search_probes_mean {0.0};
double remove_probes_mean {0.0};

Это сразу показало, когда хеш-функция распределяет плохо.

Урок 5: Отслеживание памяти раскрывает все

В начале я создал синглтон MemoryTracker, перехватывающий все выделения:

class MemoryTracker {
public:
    void record_allocation(void* ptr, size_t size, const char* file, int line);
    void record_deallocation(void* ptr);
    bool check_leaks() const;
    // ...
};

Вместе с кастомным TrackedAllocator<T>, подключаемым к STL, я мог ответить на вопросы: сколько памяти реально использует каждая структура? Каков пик памяти во время бенчмарка? Есть ли утечки? Цифры накладных расходов памяти оказались поучительными:

Связные списки имеют почти в два раза большие накладные расходы по сравнению с массивами, если учесть указатели на узлы. С оптимизацией пула памяти (MemoryPool<Node>) я снизил это, но массивы все равно выигрывают по плотности.

Урок 6: Воспроизводимость обязательна

Нет ничего более раздражающего, чем «вчера было быстрее». Чтобы сделать бенчмарки воспроизводимыми, я добавил:

• Явное сидирование RNG: каждый запуск со случайным паттерном записывает свой сид
• Режимы паттернов: последовательный, случайный или смешанный
• Снятие отпечатков оборудования: JSON-вывод включает модель CPU, ОС и информацию о сборке
• Проверки регрессий: сравнение текущего запуска с сохраненными базовыми

struct BenchmarkConfig {
    enum class Pattern { SEQUENTIAL, RANDOM, MIXED };
    Pattern pattern = Pattern::SEQUENTIAL;
    std::optional<unsigned long long> seed;
    bool seed_was_generated = false;
    // ...
};

Теперь, когда кто-то сообщает странные цифры, я могу спросить: «Какой сид? Какой паттерн? Какое оборудование?» — и реально воспроизвести проблему.

Анализ точек пересечения: вот ради чего все затевалось

После всей этой инфраструктуры я наконец мог ответить на вопрос: когда одна структура обходит другую? Анализ пересечений проходит по размерам и находит, где кривые производительности пересекаются:

Операция: поиск
Точка пересечения массива и хеш-таблицы при N ≈ 150
(При менее 150 элементах линейный поиск по массиву быстрее, чем поиск по хешу!)

Да, для небольших коллекций накладные расходы на хеширование часто превышают выгоду. Хеш-таблица с 50 элементами может быть медленнее линейного сканирования массива. Локальность кэша — вот что важно.

Ключевые выводы

• Бенчмаркайте перед оптимизацией. Ваша интуиция о производительности, вероятно, ошибочна.
• Big-O необходимо, но недостаточно. Константы важны. Локальность кэша важна. Накладные расходы памяти важны.
• Сначала создайте инфраструктуру измерения. Нельзя улучшить то, что нельзя точно измерить.
• Простые интерфейсы, сложные реализации. Чистый базовый класс DataStructure упростил расширение и тестирование.
• Воспроизводимость — это фича. Сиды, информация об оборудовании и сравнение с базовыми линиями экономят время отладки.
• «Лучшая» структура данных зависит от вашей нагрузки. Универсального победителя нет.

Попробуйте сами

hashbrowns — открытый исходный код, созданный для обучения:

git clone https://github.com/aeml/hashbrowns.git
cd hashbrowns
scripts/build.sh -t Release --test
./build/hashbrowns --size 10000 --runs 10 --structures array,hashmap

Код подробно прокомментирован, есть туториалы по добавлению собственных структур данных. Иногда лучший способ понять производительность — измерить ее самостоятельно.

Какие предположения о структурах данных вас удивляли? Поделитесь в комментариях — мне интересно узнать о ваших бенчмарк-приключениях!