«Связанные списки — это goto структур данных.», — авторство приписывают разным системным программистам.
Оглавление
Глава 1: Разрыв в производительности
Глава 3: Бенчмаркинг и профилирование
Глава 4: Массивы и локальность кэша
Глава 5: Связанные списки — убийцы кэша
История из учебника
Все студенты, изучающие computer science, узнают о связанных списках на первом курсе по структурам данных. Их описание звучит привлекательно:
Преимущества (согласно учебникам):
Вставки и удаления за O(1) в известных позициях
Динамический размер: увеличиваются и уменьшаются согласно необходимости
Пространство не тратится впустую: можно распределять ровно столько, сколько нужно
Гибкость: простота реализации стеков, очередей и других структур
Недостатки (согласно учебникам):
Поиск за O(n): необходим обход, начиная с головы списка
Лишняя память: указатели добавляют оверхед
Невозможность произвольного доступа: нельзя выполнять переходы в произвольные позиции
Вывод из учебника: «Используйте связанные списки, когда требуются частые вставки/удаления и не нужен произвольный доступ».
Вроде бы звучит разумно?
Проверка реальностью
А вот, чего учебники нам не говорят: связанные списки — это почти всегда плохой выбор.
Не потому, что ошибочен анализ «О» большого, в нём всё правильно, а потому, что он неполон. Он забывает про оборудование.
Давайте проведём простой эксперимент: сравним три операции с 100000 элементов:
Последовательный обход: посещение каждого элемента
Произвольный доступ: доступ к элементам в произвольном порядке
Вставки: добавление элементов по одному
Протестируем и массивы, и связанные списки. Вот результаты:
=== Последовательный обход === Массив: 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: фрагментация
Многократные 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
Результаты
Операция | Массив | Связанный список | Разница |
|---|---|---|---|
Последовательный обход | 70 мкс | 179 мкс | 2,5× |
Произвольный доступ | 95 мкс | 2847 мкс | 30× |
Вставка в конец | 42 мкс | 1234 мкс | 29× |
Вставка в начало | 0,01 мкс | 0,02 мкс | 2× |
Удаление из середины | 45 мкс | 1150 мкс | 25× |
Поиск элемента | 82 мкс | 2234 мкс | 27× |
Важнейшие выводы:
Массивы выигрывают почти во всём с перевесом в 2-30 раз
Единственное исключение: вставка в начало (но кто этим занимается?)
Важнее всего поведение кэша: для списков произвольный доступ в 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), фиксированный размер, отсутствие гибкости
Реальность:
Связанные списки: медленные из-за промахов кэша, оверхед памяти, затраты на распределение
Массивы: быстрые, удобные для кэша, предсказуемые
Когда использовать связанные списки:
Интрузивные списки в ядрах (встроенные узлы)
Алгоритмы без блокировок (с пулами памяти)
Маленькие списки (<100 элементов) с редкими вставками
Когда вы провели бенчмарки и доказали, что они быстрее (но такое бывает редко!)
Когда использовать массивы:
Почти всегда
Серьёзно, просто используйте массивы
Или динамические массивы, если нужно их увеличивать
Я уже говорил о массивах?
Стратегии оптимизации (если вы вынуждены использовать связанные списки):
Пулы памяти для распределения
Развёрнутые списки для улучшения использования кэша
Встроенные узлы, чтобы избежать отдельного распределения
Списки должны быть маленькими
Встроенные системы:
Избегайте связанных списков из-за фрагментации, непредсказуемых таймингов и оверхеда памяти
Используйте массивы или пулы памяти
Профилируйте и измеряйте всё
Главный вывод: связанные списки — это goto структур данных; используйте их только в самых крайних случаях.
