Структуры данных на практике. Глава 1: Разрыв в производительности

Часть I: Основы

«В теории теория и практика одинаковы. На практике это не так». — авторство приписывается разными специалистам по computer science

Загадка

Два часа утра. Я смотрю на совершенно нелогичные данные профилирования.

В процессе работы над загрузчиком для SoC RISC-V у нас возникла проблема с производительностью. Загрузчик должен был искать конфигурации устройств в таблице: примерно пятьсот элементов, каждый с 32-битным ID устройства и указателем на данные конфигурации. Всё просто.

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

Но загрузчик работал медленно. Недопустимо медленно. Время загрузки должно было находиться в пределах 100 мс, но превышало это значение на три порядка.

Я попробовал использовать очевидную оптимизацию: заменить хэш-таблицу двоичным поиском по отсортированному массиву. Двоичный поиск занимает O(log n), что теоретически хуже, чем O(1). Так написано в учебниках. Мой преподаватель алгоритмов был бы разочарован.

Но в результате загрузчик оказался на 40% быстрее.

Как O(log n) смогло победить O(1)? Что происходит?

Расследование

Я запустил Linux-инструмент профилирования производительности perf и прогнал обе реализации:

# Версия с хэш-таблицей $ perf stat -e cache-references,cache-misses ./bootloader_hash   Performance counter stats:     1,247,832  cache-references       892,441  cache-misses  (71.5% miss rate)  # Версия с двоичным поиском $ perf stat -e cache-references,cache-misses ./bootloader_binsearch   Performance counter stats:       423,156  cache-references        89,234  cache-misses  (21.1% miss rate)

Вот и ответ: хэш-таблица обеспечивает частоту промаха кэша в 71,5%. При двоичном поиске промахов оказывается всего 21,1%.

В этой системе каждый промах кэша стоит примерно сто тактов CPU. Хэш-таблица тратила основную часть времени на ожидание памяти.

Хэш-таблица O(1) выполняла меньше операций, но каждая операция была дорогой. Двоичный поиск O(log n) выполнял больше операций, но каждая операция была дешёвой.

«Железо» победило алгоритм.

Почему это важно

Моя серия статей посвящена этому разрыву — разнице между тем, что написано в учебниках и тем, что происходит на самом деле, когда код работает на реальном кремнии.

На традиционных курсах по структурам данных учат подходить к алгоритмам с точки зрения сложности «O» большого:

• Массивы: доступ — O(1), вставка — O(n)

• Связанные списки: вставка — O(1), доступ — O(n)

• Хэш-таблицы: O(1) в среднем

• Деревья двоичного поиска: операции O(log n)

Это полезные абстракции, позволяющие нам рассуждать об алгоритмах в целом. Но они не всеобъемлющи.

Они подразумевают, что все операции доступа к памяти стоят одинаково. Они подразумевают, что операции выполняются изолированно. Они подразумевают работу на идеальном компьютере, которого не существует.

У реальных компьютеров есть:

• Иерархии памяти: регистры, кэш L1, кэш L2, кэш L3, DRAM

• Провалы в задержках: 1 такт или 100 с лишним тактов

• Линии кэша: 64 байт получаются вместе

• Устройства упреждающей выборки: оборудование, угадывающее, что вам понадобится дальше

• Ограниченная пропускная способность: невозможно получить все данные сразу

А если вы работаете со встраиваемыми системами, то ограничений ещё больше:

• Крошечные кэши: обычно от 8 КБ до 64 КБ

• Отсутствие кэша L3: у многих микроконтроллеров есть максимум L1 или L2

• Медленная память: DRAM может работать на частоте 100 МГц, а не 3 ГГц

• Требования работы в реальном времени: важен наихудший, а не усреднённый сценарий

Модель реальной производительности

Вот более подробная ментальная модель современных компьютеров:

Время = Операции ? (Вычислительные затраты + Затраты памяти)

Где:

• Вычислительная затраты: сами операции АЛУ (обычно дешёвые)

• Затраты памяти: промахи кэша, доступ к DRAM (обычно дорогие)

При реализации многих алгоритмов преобладают затраты памяти.

Давайте покажем это на примере реальных значений типичной встраиваемой системы с RISC-V:

Единственный промах кэша может стоить до 100 операций с регистрами.

Из этого следует:

• Алгоритм O(n), оптимально использующий кэш, может победить алгоритм O(log n), использующий кэш плохо

• Хэш-таблица O(1) может проиграть двоичному поиску O(log n)

• «Медленный» алгоритм, умещающийся в кэше, может победить «быстрый» алгоритм, который в него не помещается

Наш первый бенчмарк: массив против связанного списка

Давайте добавим конкретики, проведя простой эксперимент. Сравним два способа суммирования 100000 целых чисел:

1. Массив: сплошная память, идеально для кэширования

2. Связанный список: разбросанная память, кошмар для кэширования

Сложность обоих O(n). В учебниках написано, что их показатели будут схожими. Посмотрим, что происходит на самом деле.

Вот версия с массивом:

// Массив: сплошная память int array[100000]; for (int i = 0; i < 100000; i++) {     array[i] = i; }  // Суммируем все элементы long long sum = 0; for (int i = 0; i < 100000; i++) {     sum += array[i]; }

И версия со связанным списком:

// Связанный список: разбросанная память typedef struct node {     int value;     struct node *next; } node_t;  node_t *head = NULL; for (int i = 0; i < 100000; i++) {     node_t *node = malloc(sizeof(node_t));     node->value = i;     node->next = head;     head = node; }  // Суммируем все элементы long long sum = 0; node_t *curr = head; while (curr) {     sum += curr->value;     curr = curr->next; }

Воспользуемся нашим фреймворком бенчмаркинга (о котором мы подробно поговорим в Главе 3):

=== Последовательное суммирование массива === Среднее время:      70147 нс Медианное время:    71724 нс Общее количество тактов:   17557410  === Последовательное суммирование связанного списка === Среднее время:      179169 нс Медианное время:    160527 нс Общее количество тактов:   44740656  Массив в 2,55 раза быстрее, чем связанный список

Один и тот же алгоритм (последовательное суммирование), одинаковая сложность O(n), но массив в 2,5 раза быстрее.

Почему? Давайте взглянем на поведение кэша:

Паттерн доступа к массиву:

Память:  [0][1][2][3][4][5][6][7][8][9]...          ?  ?  ?  ?  ?  ?  ?  ?  ?  ? Доступ:  последовательный, предсказуемый Кэш:   получение 64 байт (16 int) за раз Результат: попадание в кэш примерно в 94% случаев

Паттерн доступа к связанному списку:

Память:  [узел] ... [узел] ... [узел] ... [узел]          ?          ?          ?          ? Доступ:  произвольный, непредсказуемый (следует за указателями) Кэш:   вероятно, каждый узел будет находиться в отдельной линии кэша Результат:  промахи кэша примерно в 70% случаев

Массив выигрывает благодаря пространственной локальности — при доступе к array[0] CPU получает всю линию кэша (64 байт), то есть элементы с array[0] по array[15]. Следующие 15 операций доступа происходят без затрат.

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

Иерархия памяти

Чтобы понять, почему кэш так важен, нужно разобраться с иерархией памяти.

Современные компьютеры — это уже не простая модель «CPU + RAM», которую дают на вводных курсах. Больше они похожи на такую схему:

Ядро CPU   ? 1 такт Регистры (32-64 регистров, ~256 байт)   ? 3-4 тактов Кэш L1 (32-64 КБ, разделение на команды и данные)   ? 12-15 тактов Кэш L2 (256 КБ - 1 МБ, унифицированный)   ? 40-50 тактов Кэш L3 (4-32 МБ, общий) [есть не во всех системах]   ? 100-200 тактов DRAM (размер измеряется в ГБ)   ? от 10000 тактов SSD/флэш-память

Каждый уровень:

• Быстрее, но меньше по объёму, чем уровень ниже него

• Более дорогой на байт

• Ближе к CPU

Разрыв в скорости огромен. Для процессора RISC-V частотой 1 Гц:

• Кэш L1: 3-4 наносекунды

• DRAM: 100-200 наносекунд

• Разница в 50 раз

Для сравнения: если бы для доступа к кэшу L1 требовалась 1 секунда, то для доступа к DRAM требовалось бы 50 секунд.

Линии кэша: фундаментальная единица измерения

Крайне важно понимать, что CPU получает не отдельные байты, а линии кэша.

Линия кэша обычно содержит 64 байт. При доступе к одному байту CPU получает весь 64-байтный блок, содержащий этот байт.

Это влечёт за собой очень серьёзные последствия:

Хорошие: при доступе к соседним данным они уже находятся в кэше (пространственная локальность)

// Превосходно: последовательный доступ for (int i = 0; i < n; i++) {     sum += array[i];  // Следующий элемент, скорее всего, будет находиться в той же линии кэша }

Плохие: при каждом получении разбросанных данных мы теряем впустую 63 байта

// Ужасно: произвольный доступ for (int i = 0; i < n; i++) {     sum += array[random()];  // Каждая операция доступа, скорее всего, будет промахиваться мимо кэша }

Ещё хуже: если структура данных устроена плохо, вам придётся расплачиваться за данные, которые вы не используете

// Узел связанного списка: 16 байт (4-байтное значение + 8-байтный указатель + заполнитель) // Линия кэша: 64 байта // Впустую потрачено 48 байт (75% линии кэша не используется!)

Упреждающая выборка: оборудование пытается нам помочь

В современных CPU есть устройства для упреждающей выборки (prefetcher), пытающиеся спрогнозировать, к чему будет выполнять доступ в ближайшее время. Они хорошо справляются с распознаванием простых паттернов:

Последовательный доступ: prefetcher обожает его

for (int i = 0; i < n; i++) {     process(array[i]);  // Prefetcher: "Я вижу паттерн! Получаем всё сразу!" }

Доступ с периодическим шагом: prefetcher может с ним справиться

for (int i = 0; i < n; i += 2) {     process(array[i]);  // Prefetcher: "Понял, двигаемся с шагом 2!" }

Следование по указателям: prefetcher сдаётся

while (node) {     process(node->value);     node = node->next;  // Prefetcher: "Понятия не имею, что там дальше..." }

Именно поэтому связанные списки работают так медленно — prefetcher ничем не может помочь. Каждое разыменование указателя становится для него неожиданностью.

Встраиваемые системы: ещё более жёсткие ограничения

При работе со встраиваемыми системами ситуация ещё более серьёзная:

Типичный микроконтроллер RISC-V:

• Кэш L1: 16-32 КБ (32-64 КБ в десктопных процессорах)

• Кэш L2: 128-256 КБ (256 КБ - 1 МБ в десктопных процессорах)

• Кэш L3: отсутствует (4-32 МБ в десктопных процессорах)

• DRAM: 100 МГ(3 ГГц на десктопах)

При кэше L1 размером 16 КБ весь рабочий набор должен умещаться в 16 КБ, иначе пострадает кэш.

Для сравнения:

• 100000 чисел integer (массив): 400 КБ ? не поместятся в L1

• 100000 узлов связанного списка: 1,6 МБ ? не поместятся даже в L2

Именно поэтому разработчики встраиваемых систем так одержимы размером и конфигурацией структур данных. Важен каждый байт.

Реальное время

Во встраиваемых системах нас часто волнует не средний, а наихудший сценарий.

Для примера возьмём контур системы управления, работающий с частотой 1 кГц (период 1 мс):

• Наилучший сценарий: все данные находятся в кэше L1 ? 50 микросекунд

• Наихудший сценарий: все данные находятся в DRAM ? 500 микросекунд

Если алгоритм работает с кэшем непредсказуемым образом, то гарантировать сроки выполнения в реальном времени невозможно.

Поэтому в системах реального времени часто предпочтительны:

• Статическое распределение: прогнозируемая структура памяти

• Структуры данных фиксированного размера: отсутствие динамического изменения размеров

• Простые алгоритмы: предсказуемое поведение с кэшем

Даже если они «медленнее» в среднем сценарии с точки зрения «О» большого.

Что вы узнаете из этой серии статей

Она научит вас рассуждать о структурах данных с точки зрения реалий «железа»:

Часть I: Основы

• Как работает иерархия памяти (Глава 2)

• Как измерять и профилировать производительность (Глава 3)

Часть II: Основные структуры данных

• Массивы: удобный для кэша фундамент (Глава 4)

• Связанные списки: когда и как их использовать (Глава 5)

• Стеки, очереди и кольцевые буферы (Глава 6)

• Хэш-таблицы: как их проектировать с учётом кэша (Глава 7)

• Динамические массивы и управление памятью (Глава 8)

Часть III: Деревья и иерархии

• Двоичные деревья поиска: поведение кэша (Глава 9)

• B-деревья: как их проектировать с учётом кэша (Глава 10)

• Деревья и базисные деревья (Глава 11)

• Кучи и очереди с приоритетами (Глава 12)

Часть IV: Дополнительные темы

• Структуры данных без блокировок (Глава 13)

• Обработка строк (Глава 14)

• Графы и сети (Глава 15)

• Вероятностные структуры (Глава 16)

Часть V: Изучение примеров

• Структуры данных загрузчика (Глава 17)

• Очереди драйверов устройств (Глава 18)

• Управление памятью прошивок (Глава 19)

Каждая глава будет содержать:

• Реальные примеры из мира встраиваемых систем

• Бенчмарки, демонстрирующие истинную производительность

• Анализ кэша при помощи профилировщиков

• Инструкции по проектированию кода

Требования и подготовка

Чтобы извлечь из этой серии максимальную пользу, вы должны:

Знать:

• Программирование на C (указатели, struct, управление памятью)

• Базовые структуры данных (массивы, связанные списки, деревья)

• Базовые алгоритмы (сортировка, поиск)

Иметь:

• Систему с Linux (рекомендуется Ubuntu/Debian)

• Компилятор GCC

• Базовые навыки работы с командной строкой

Необязательно, но полезно:

• Макетная плата RISC-V или QEMU

• Опыт работы со встраиваемыми системами

• Знакомство с языком ассемблера

Что нас ждёт дальше

В следующей главе мы глубже изучим иерархию памяти. Вы узнаете:

• Как работают кэши на аппаратном уровне

• Что такое линии, наборы и каналы кэша

• Как прогнозировать поведение кэша

• Как измерять производительность кэша

В Главе 3 мы создадим готовый фреймворк для бенчмаркинга, тот же самый, который применяется для всех измерений в этой серии статей.

К концу Части I вы получите все необходимые инструменты и знания для анализа реальной производительности любой структуры данных.

Давайте приступим.

Подведём итог

Загадка, которую я исследовал в два часа ночи, была решена. Двоичный поиск с O(log n) обгоняет хэш-таблицу с O(1) на 40%, потому что работа с кэшем здесь важнее, чем алгоритмическая сложность. 71,5% промахов кэша у хэш-таблицы и 21,1% промахов у двоичного поиска объяснили всё. «Железо» оказалось важнее алгоритма.

Основные выводы:

1. Сложность «O» большого — необходимое, но недостаточное условие для понимания производительности в реальном мире

2. В производительности современных компьютеров важнее всего иерархия памяти

3. Промахи кэша стоят в сто раз больше, чем попадания в кэш

4. Важна пространственная локальность: последовательный доступ лучше произвольного

5. Встраиваемые системы обладают более жёсткими ограничениями: их кэши меньше, а память медленнее

6. Системам реального времени необходима предсказуемая производительность: важнее всего наихудший сценарий

Разрыв в производительности:

• Теория: хэш-таблица с O(1) должна обгонять двоичный поиск с O(log n)

• Практика: из-за промахов кэша всё может оказаться наоборот

• Вывод: необходимы измерения, а не предположения.