Структуры данных на практике. Глава 5: Связанные списки — убийцы кэша

«Связанные списки — это goto структур данных.», — авторство приписывают разным системным программистам.

Оглавление

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

Глава 2: Иерархия памяти

Глава 3: Бенчмаркинг и профилирование

Глава 4: Массивы и локальность кэша

Глава 5: Связанные списки — убийцы кэша

История из учебника

Все студенты, изучающие computer science, узнают о связанных списках на первом курсе по структурам данных. Их описание звучит привлекательно:

Преимущества (согласно учебникам):

• Вставки и удаления за O(1) в известных позициях

• Динамический размер: увеличиваются и уменьшаются согласно необходимости

• Пространство не тратится впустую: можно распределять ровно столько, сколько нужно

• Гибкость: простота реализации стеков, очередей и других структур

Недостатки (согласно учебникам):

• Поиск за O(n): необходим обход, начиная с головы списка

• Лишняя память: указатели добавляют оверхед

• Невозможность произвольного доступа: нельзя выполнять переходы в произвольные позиции

Вывод из учебника: «Используйте связанные списки, когда требуются частые вставки/удаления и не нужен произвольный доступ».

Вроде бы звучит разумно?

Проверка реальностью

А вот, чего учебники нам не говорят: связанные списки — это почти всегда плохой выбор.

��е потому, что ошибочен анализ «О» большого, в нём всё правильно, а потому, что он неполон. Он забывает про оборудование.

Давайте проведём простой эксперимент: сравним три операции с 100000 элементов:

1. Последовательный обход: посещение каждого элемента

2. Произвольный доступ: доступ к элементам в произвольном порядке

3. Вставки: добавление элементов по одному

Протестируем и массивы, и связанные списки. Вот результаты:

=== Последовательный обход ===
Массив:              70 мкс
Связанный список:   179 мкс
Победитель: массив (быстрее в 2,5 раза)

=== Произвольный доступ ===
Массив:              95 мкс
Связанный список:  2847 мкс
Победитель: массив (быстрее в 30 раз!)

=== Вставки (в конец) ===
Массив:              42 мкс
Связанный список:  1234 мкс
Победитель: массив (быстрее в 29 раз!)

Что? Массив быстрее при вставках? Но они должны быть O(n) для массивов и O(1) для связанных списков!

Добро пожаловать в реальность современного оборудования.

Почему связанные списки медленные

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

Сравнение схем памяти:

Поведение кэша при обходе:

Разница огромна:

Шаг 1: доступ к узлу A
  CPU: "Получить адрес 0x1000"
  Кэш: ПРОМАХ (100 тактов)
  Память: возвращает узел A + 63 байта соседних данных
  
Шаг 2: доступ к узлу B (через A->next)
  CPU: "Получить адрес 0x5000"  (в произвольном местоположении)
  Кэш: ПРОМАХ (100 тактов)
  Память: возвращает узел B + 63 байта соседних данных
  
Шаг 3: доступ к узлу C (через B->next)
  CPU: "Получить адрес 0x2000"  (в произвольном местоположении)
  Кэш: ПРОМАХ (100 тактов)
  Память: возвращает узел C + 63 байта соседних данных

Каждый доступ к узлу — это промах кэша. Каждый промах кэша стоит примерно 100 тактов.

При 100000 узлов 10 миллионов тактов тратятся просто на ожидание памяти.

Сравним это с массивом:

Шаг 1: доступ к array[0]
  CPU: "Получить адрес 0x1000"
  Кэш: ПРОМАХ (100 тактов)
  Память: возвращает 64 байта (16 integer)
  
Шаги 2-16: доступ к значениям с array[1] по array[15]
  CPU: "Получить адреса 0x1004, 0x1008, ..."
  Кэш: ПОПАДАНИЕ (3 такта каждое)
  
Шаг 17: доступ к array[16]
  CPU: "Получить адрес 0x1040"
  Кэш: ПРОМАХ (100 тактов)
  Память: возвращает 64 байта (ещё 16 integer)

Всего один промах кэша на 16 элементов, то есть 6250 промахов кэша на 100000 элементов.

10 миллионов тактов против 625000 тактов. Из-за одного лишь поведения кэша массив быстрее в 16 раз.

Оверхед памяти

Кроме того, связанные списки впустую тратят память. Много памяти.

Рассмотрим простой узел связанного списка, хранящий 32-битный integer:

typedef struct node {
    int value;        // 4 байта
    struct node *next; // 8 байт (в 64-битных системах)
} node_t;             // Итого: 12 байт + 4 байта заполнения = 16 байт

Для 4-байтного integer мы используем 16 байт. Четырёхкратный оверхед.

Массив из 100000 integer:

• Массив: 400 КБ

• Связанный список: 1,6 МБ

Связанный список использует в 4 раза больше памяти и он в 2,5 раза медленнее. Это ужасно.

Затраты на распределение

Есть и ещё одни скрытые затраты: на распределение памяти.

Для создания связанного списка необходимо вызывать malloc() для каждого узла:

// Связанный список: 100000 вызовов malloc
for (int i = 0; i < 100000; i++) {
    node_t *node = malloc(sizeof(node_t));  // Очень затратно!
    node->value = i;
    node->next = head;
    head = node;
}

Каждый вызов malloc():

• Выполняет поиск по списку свободной памяти

• Обновляет метаданные

• Потенциально выполняет вызов ядра, чтобы запросить ещё памяти

• Фрагментирует кучу

Для создания массива требуется одно распределение:

// Массив: 1 вызов malloc
int *array = malloc(100000 * sizeof(int));  // Быстро!
for (int i = 0; i < 100000; i++) {
    array[i] = i;
}

В наших бенчмарках создание связанного списка занимало 1234 мкс, а массива — 42 мкс. Разница в 29 раза.

Когда имеет смысл использовать связанные списки

Так когда же нужно использовать связанные списки? Редко.

Когда стоит задуматься о применении связанных списков:

Существует несколько вполне допустимых сценариев их использования:

1. Интрузивные списки в ядрах

В ядре Linux активно используются связанные списки, только не их версия из учебника. Там применяются интрузивные списки:

struct list_head {
    struct list_head *next, *prev;
};

struct task_struct {
    // ... данные задачи ...
    struct list_head tasks;  // Встроенный узел списка
};

Узел списка встраивается в структуру данных, а не распределяется отдельно. Благодаря этому:

• Устраняется оверхед распределения

• Повышается локальность кэша (данные и ссылки находятся рядом)

• Один объект может находиться в нескольких списках

2. Алгоритмы без блокировки

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

• Атомарные обновления указателей выполнять проще, чем обновления массивов

• Нет необходимости изменения размера (которое бы потребовало блокировку)

Пример: стек без блокировки (стек Трейбера):

typedef struct node {
    int value;
    struct node *next;
} node_t;

void push(node_t **head, node_t *node) {
    do {
        node->next = *head;
    } while (!atomic_compare_exchange(head, &node->next, node));
}

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

3. Редкие вставки в большие датасеты

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

Но если говорить откровенно, обычно лучше динамический массив с амортизированными вставками за O(1).

Стратегии оптимизации

Если обязательно нужно использовать связанный список, то его можно сделать менее ужасным:

Стратегия 1: пулы памяти

Вместо вызова malloc() для каждого узла распределяйте узлы из пула:

#define POOL_SIZE 10000
node_t node_pool[POOL_SIZE];
int pool_index = 0;

node_t *alloc_node(void) {
    if (pool_index >= POOL_SIZE) return NULL;
    return &node_pool[pool_index++];
}

Преимущества:

• Повышение скорости распределения: нет оверхеда malloc

• Повышенная локальность: узлы находятся по соседству

• Предсказуемая память: отсутствие фрагментации

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

Связанный список (malloc):  1234 мкс
Связанный список (пул):      287 мкс
Массив:                       42 мкс

Пул в 4,3 раза быстрее, чем malloc, но всё равно в 6,8 раза медленнее, чем массив.

Стратегия 2: развёрнутые связанные списки

Храните в каждом узле несколько элементов:

#define ELEMENTS_PER_NODE 16

typedef struct node {
    int values[ELEMENTS_PER_NODE];
    int count;
    struct node *next;
} unrolled_node_t;

Преимущества:

• Оптимизация использования кэша: 16 элементов на промах кэша вместо одного

• Меньше оверхед указателей: 1 указатель на 16 элементов

• Меньшее количество распределений: 1/16 количества вызовов malloc

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

Стандартный связанный список:  179 мкс
Развёрнутый связанный список:   45 мкс
Массив:                         70 мкс

Что? Развёрнутый список быстрее, чем массив? Не совсем — это справедливо только для последовательного обхода. При произвольном доступе массив всё равно побеждает.

Стратегия 3: XOR связанных списков

Экономьте память, выполняя XOR предыдущего и следующего указателей:

typedef struct node {
    int value;
    struct node *prev_xor_next;  // prev XOR next
} xor_node_t;

Для обхода:

node_t *prev = NULL;
node_t *curr = head;
while (curr) {
    node_t *next = (node_t *)((uintptr_t)prev ^ (uintptr_t)curr->prev_xor_next);
    prev = curr;
    curr = next;
}

Преимущества:

• На 50% меньше памяти под указатели: один указатель вместо двух

• Те же затраты на обход: по-прежнему один промах кэша на узел

Недостатки:

• Более сложный код: логика XOR неочевидна

• Отсутствие обхода назад от произвольного узла: нужны и prev, и curr

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

Вердикт: в большинстве случаев не стоит того. Экономия памяти мала, а сложность высока.

Исследование реального примера: списки задач RTOS

Давайте рассмотрим реальный сценарий применения во встраиваемых системах: планирование задач в операционной системе реального времени (ОСРВ, RTOS).

Сценарии: FreeRTOS управляет готовыми задачами в списках с приоритетом.

Требования:

• Вставка задачи, когда она готова (O(1) или O(n))

• Удаление задачи с наибольшим приоритетом (O(1))

• Изменение приоритетов (O(n))

Решение FreeRTOS: массив связанных списков, по одному на каждый уровень приоритета.

#define MAX_PRIORITIES 32

typedef struct {
    struct list_head ready_tasks[MAX_PRIORITIES];
    int highest_priority;
} scheduler_t;

Почему это работает:

• Малые списки: обычно по 1-5 задач на каждый уровень приоритета

• Узлы со встроенными списками: нет оверхеда распределения

• Удобство для кэша: структура задачи и узел списка находятся вместе

• Операции O(1): вставка/удаление с известным приоритетом

Бенчмарк (на ARM Cortex-M4):

Вставка задачи:          0,8 мкс
Удаление задачи:         0,6 мкс
Поиск следующей задачи:  0,3 мкс

Это обеспечивает достаточную скорость для планировщика, работающего с частотой 1 кГц (период 1000 мкс).

Важный вывод: здесь связанный список подходит, потому что:

1. Списки маленькие (удобные для кэша)

2. Узлы встроены (распределение не требуется)

3. Операции просты (нет сложного обхода)

Встраиваемые системы

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

Проблема 1: фрагментация

Многократные malloc/free приводят к фрагментации кучи:

Исходная куча: [----------------свободно----------------]
После 1000 распределений и 500 очисток:
[используется][свободно][используется][свободно][используется][свободно][используется]...

Рано или поздно выполнять распределения не получится, даже если места достаточно.

Решение: использовать пулы памяти или полностью отказаться от динамического распределения.

Проблема 2: непредсказуемые тайминги

Из-за промахов кэша обход связанного списка оказывается непредсказуемым:

Наилучший случай:  все узлы находятся в кэше → 50 мкс
Наихудший случай:  все узлы находятся в DRAM  → 500 мкс

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

Решение: использовать массивы с предсказуемыми паттернами доступа.

Проблема 3: оверхед памяти

В системе с 64 КБ ОЗУ связанный список из 1000 элементов занимает:

• Данные: 4 КБ (1000 × 4 байта)

• Указатели: 8 КБ (1000 × 8 байт)

• Оверхед malloc: ~2 КБ (метаданные)

• Всего: 14 КБ (22% ОЗУ!)

Массив занимал бы 4 КБ (6% ОЗУ).

Решение: использовать массивы или развёрнутые списки.

Советы по проектированию

Вот дерево принятия решений для выбора между массивами и связанными списками:

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

Бенчмаркинг связанных списков

Давайте проведём подробный бенчмарк по сравнению массивов и связанных списков при выполнении различных операций:

Параметры теста

• 100000 элементов

• Система x86_64, кэш L1 32 КБ

• Оптимизация GCC -O2

Результаты

Важнейшие выводы:

1. Массивы выигрывают почти во всём с перевесом в 2-30 раз

2. Единственное исключение: вставка в начало (но кто этим занимается?)

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

Анализ кэша

Используем perf для измерения поведения кэша:

$ perf stat -e cache-references,cache-misses ./benchmark

Array traversal:
  423,156 cache-references
   89,234 cache-misses (21.1% miss rate)

Linked list traversal:
  1,247,832 cache-references
    892,441 cache-misses (71.5% miss rate)

У связанного списка в 3,4 раза больше промахов кэша. И поэтому он такой медленный.

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

Рассказы о связанных списках из учебников расходятся с реальностью. Массивы побеждают связанные списки во всех бенчмарках. Такой разрыв в производительности объясняет частота промахов кэша: у связанного списка — 71,5%, у массива — 20,9%. Поведение кэша перевешивает алгоритмическую сложность.

История из учебника:

• Связанные списки: вставки за O(1), гибкость, динамичность

• Массивы: вставки за O(n), фиксированный размер, отсутствие гибкости

Реальность:

• Связанные списки: медленные из-за промахов кэша, оверхед памяти, затраты на распределение

• Массивы: быстрые, удобные для кэша, предсказуемые

Когда использовать связанные списки:

1. Интрузивные списки в ядрах (встроенные узлы)

2. Алгоритмы без блокировок (с пулами памяти)

3. Маленькие списки (<100 элементов) с редкими вставками

4. Когда вы провели бенчмарки и доказали, что они быстрее (но такое бывает редко!)

Когда использовать массивы:

1. Почти всегда

2. Серьёзно, просто используйте массивы

3. Или динамические массивы, если нужно их увеличивать

4. Я уже говорил о массивах?

Стратегии оптимизации (если вы вынуждены использовать связанные списки):

1. Пулы памяти для распределения

2. Развёрнутые списки для улучшения использования кэша

3. Встроенные узлы, чтобы избежать отдельного распределения

4. Списки должны быть маленькими

Встроенные системы:

• Избегайте связанных списков из-за фрагментации, непредсказуемых таймингов и оверхеда памяти

• Используйте массивы или пулы памяти

• Профилируйте и измеряйте всё

Главный вывод: связанные списки — это goto структур данных; используйте их только в самых крайних случаях.