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

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

Вы наверняка учили таблицу: вставка в массив — O(n), потому что нужно сдвигать элементы, а в связный список — O(1), достаточно переставить указатели. Вывод: если много вставляете — берите список. Но когда вы пишете оба варианта и измеряете, массив всё равно выигрывает. Почему? Ответ скрыт не в коде, а в том, как физически устроена память. В этой статье мы разберём, что такое кэш-линия, префетчер и pointer chasing, и покажем, как эти концепции влияют на реальную производительность.

Измерение, с которого всё начинается

Возьмём десять миллионов целых чисел: одно непрерывное хранилище (массив) и десять миллионов связанных узлов. Пройдёмся по каждому, суммируя элементы — одинаковое количество операций, одинаковый класс сложности O(n):

# layout.py — те же 10,000,000 чисел, два способа хранения
data = list(range(10_000_000))  # ОДИН блок: элемент i лежит рядом с i+1

class Node:
    __slots__ = ('val', 'next')  # 48 байт, без лишнего __dict__

def sum_array(data):
    total = 0
    for i in range(len(data)):
        total += data[i]
    return total

def sum_linked(head):
    total, node = 0, head
    while node is not None:
        total += node.val
        node = node.next  # адрес следующего узла лежит ВНУТРИ текущего
    return total

Замеры на реальной машине:

• Массив: 0.53 секунды (52.6 нс на элемент)
• Связный список: 1.53 секунды (153.3 нс на элемент)

Разница в 2.9 раза! Оба цикла делают одно сложение на элемент. Big-O говорит, что они идентичны. Но железо не согласно. В чём причина?

Аналогия с книгами: как работает кэш

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

Вся история производительности — это именно эта аналогия. Осталось назвать железо, которое играет роль «рук» и «ходьбы».

Кэш-линия: почему массив быстрее

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

Для непрерывного массива 8-байтовых значений одно обращение к памяти приносит восемь полезных значений. Вы платите за одну поездку и получаете ещё семь элементов бесплатно. Обход миллиона элементов стоит примерно 125,000 обращений, а не миллион.

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

Цена обращения не пустяк:

• Переход по указателю, уже в L1-кэше: 1.26 нс
• Переход по указателю в основной памяти: 81.5 нс

Это в 65 раз! Не фольклорное «кэш-промах стоит ~100×», а измеренное на конкретной машине. (Единственное число ~100× — это 132×, но там сравнение случайного перехода с последовательным чтением, это другой контекст.)

Префетчер: невидимый помощник

Когда процессор замечает, что вы идёте по памяти предсказуемым образом, он начинает подгружать строки до того, как вы их запросите. Обход непрерывного массива на 1 ГиБ в порядке возрастания стоит 0.62 нс на элемент — быстрее, чем один переход по указателю в L1, потому что трафик памяти идёт в фоне, пока вы вычисляете.

Префетчер не может помочь связному списку: он не угадает адрес, который ещё не загружен.

Сравнение наглядно

Эксперимент без связного списка

Всё вышесказанное — лишь теория. Может, разница в объектах узлов или в количестве аллокаций? Проведём эксперимент, который изолирует причину. Возьмём тот же массив. Сделаем те же сложения. Изменим только одно: порядок, в котором мы обращаемся к элементам.

• Обход в порядке: 44.4 нс на операцию
• Обход тех же данных в перемешанном порядке: 265.8 нс на операцию

Разница в ~6 раз, и в эксперименте нет ни одного связного списка! Изменился только паттерн доступа. Это чистое влияние кэша.

Есть аналогичный эксперимент на стороне аллокаций: оставим связный список, но изменим только порядок выделения узлов. Это даёт замедление в 2.1 раза — чистое влияние раскладки в памяти.

Запомните: связный список медленный не потому, что он связный, а потому, что он разбрасывает данные, что сводит на нет все оптимизации памяти процессора.

Что Big-O считает, а что — нет

Big-O не ошибается. Он отвечает на другой вопрос. Big-O считает операции и намеренно отбрасывает константные множители — в этом суть абстракции. Он отбрасывает: расстояние, которое прошли данные, попадание в L1 или DRAM, работу префетчера.

Два O(n) обхода могут отличаться в 2.9 раза. Две O(1) операции — в 65 раз. Big-O говорит, как растёт стоимость, но не говорит, чему равна единица этой стоимости на реальном кремнии. Для больших асимптотических разрывов (O(n) против O(log n)) рост доминирует, и Big-O решает. Для сравнений внутри одного класса он молчит, и решает иерархия памяти.

Честная правда: где связные структуры действительно выигрывают

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

Вставка в начало

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

• Массив, N = 1,000,000: 572,255 нс
• Связный список, N = 1,000,000: 243 нс

Это огромная структурная победа. Но у O(1) есть предусловие: вы должны уже держать узел. Вставка после узла, который у вас в руках, действительно O(1). Но поиск этого узла — нет.

# insert_middle.py — O(1), о котором все говорят, с предусловием

def splice_after(node, value):
    # O(1) — верно, ТОЛЬКО если у вас есть node
    node.next = Node(value, node.next)

def insert_at(head, k, value):
    # что вам на самом деле приходится писать
    node = head
    for _ in range(k):  # это не memmove, а k зависимых промахов кэша
        node = node.next
    splice_after(node, value)

Замер на N = 1,000,000, вставка в середину:

• list.insert(mid, x): 255,486 нс
• Связный список (обход + вставка): 63,488,013 нс — в 249 раз медленнее!

Сдвиг в массиве — это memmove: один плотный, дружелюбный к префетчеру последовательный проход. Обход связного списка — это k зависимых промахов кэша подряд, каждый ждёт предыдущий. Один класс сложности, но совершенно разное железо.

Правило: связная структура выигрывает, когда вы уже держите позицию.

Таблица сравнения операций (N = 1,000,000)

Связные структуры также дают стабильные ссылки: адрес узла не меняется при изменении соседей. Массивы такой гарантии не дают. Это свойство — не скорость — причина, почему связные структуры используются в списках свободной памяти аллокаторов, LRU-кэшах и внутренних списках ядра.

Что ваш язык уже выбрал за вас

Большинство решений уже принято за вас, и полезно знать, что у вас есть:

• Python list — это непрерывный массив, но указателей. Сами целые — отдельные объекты в куче, поэтому миллион элементов стоит ~40 МБ, а не 8.2 МБ. Непрерывность ссылок, а не значений.
• array.array('q') — истинно непрерывный случай: 8-байтовые целые лежат рядом. Это 8.2 МБ.
• collections.deque — двусвязный список блоков, а не отдельных элементов. Каждый блок содержит много элементов подряд, что даёт кэш-дружественный обход и O(1) на концах. Именно поэтому appendleft обгоняет list.insert(0,x) в 477 раз.
• Java ArrayList vs LinkedList — та же история, и LinkedList почти повсеместно не рекомендуется в современной Java.
• NumPy массивы — истинно непрерывная типизированная память, причина, почему числовой Python быстр.

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

Тот же закон на уровень выше: LLM-инференс

Если вы работаете с инференсом, вы встречали этот компромисс в другом обличии.

Обслуживание LLM означает хранение KV-кэша — ключей и значений для каждого токена в каждой активной последовательности. Наивно вы выделяете один непрерывный буфер на последовательность, размером с максимальную длину. Это выбор массива: идеально последовательное чтение, дружелюбное к префетчеру, но огромные потери, потому что большинство последовательностей не достигают максимума.

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

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

История с батчингом та же. Continuous batching выигрывает частично потому, что держит тензоры, которые GPU читает, непрерывными и предсказуемыми; каждый gather/scatter — это эксперимент с перемешиванием, но на гораздо более дорогом железе. Локальность данных — не деталь эпохи CPU, память на GPU ещё более узкое место.

Пять вопросов, на которые стоит уметь отвечать

1. Два O(n) цикла по одним данным различаются в 3 раза. Почему? — Из-за раскладки памяти: кэш-линии и префетчер.
2. Что такое pointer chasing и почему он замедляет связный список? — Адрес следующего узла находится внутри текущего, поэтому нельзя начать загрузку следующего, пока не загружен текущий.
3. Когда связный список действительно быстрее? — Когда вы уже держите узел (вставка/удаление после известного узла) или при вставке в начало.
4. Почему deque быстрее списка на вставке в начало? — deque — это связный список блоков, а не отдельных элементов, что даёт кэш-дружественность.
5. Как связана локальность данных с LLM-инференсом? — KV-кэш требует компромисса между непрерывностью и гибкостью, решаемого блочными структурами.

Что делать прямо сейчас

Проведите собственный эксперимент: возьмите массив из 10 миллионов целых и связный список из такого же числа узлов, обойдите оба и замерьте время. Затем измените порядок обхода массива (перемешайте индексы) и снова замерьте — разница вас удивит. В своём коде отдавайте предпочтение непрерывным структурам (list, array, NumPy) для итераций, а связные структуры используйте только там, где нужны стабильные ссылки или вставка/удаление в известную позицию. И помните: Big-O — это не вся история, всегда измеряйте!