Что такое pointer chasing

Замените связный список на массив, не трогая алгоритм — и получите ускорение. Обе структуры дают O(n) на обход, но процессор читает их по-разному.

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

LinkedBlockingQueue хранит элементы как цепочку узлов, и каждый узел — отдельный объект в куче. Адрес следующего узла известен только после того, как вы прочитали текущий узел и поле next внутри него — заранее его вычислить нельзя. Процессор не может загрузить следующий узел, пока не получит текущий. Обращения к памяти выстраиваются в цепочку зависимостей и идут одно за другим, а не параллельно.

Между процессором и оперативной памятью стоит кэш — маленькая, но быстрая память прямо на кристалле. Нужные данные уже там — это cache hit, чтение занимает единицы тактов. Данных там нет — это промах кэша (cache miss): процессор идёт в оперативную память, а она на порядки медленнее кэша.

У процессора есть аппаратный prefetcher — он смотрит на паттерн обращений к памяти и заранее подтягивает данные в кэш. С массивом это работает отлично: адреса предсказуемы, элемент N+1 лежит сразу за элементом N. Со связным списком prefetcher бессилен: следующий адрес — это данные, а не арифметика, и предсказать его нельзя. Каждый переход по next с высокой вероятностью — промах кэша, а один промах на современном CPU стоит порядка сотен тактов ожидания памяти.

class Node(val value: Long, var next: Node? = null)

fun sumLinked(head: Node?): Long {
    var sum = 0L
    var n = head
    while (n != null) {
        sum += n.value   // адрес следующего узла узнаём только сейчас
        n = n.next
    }
    return sum
}

fun sumArray(values: LongArray): Long {
    var sum = 0L
    for (v in values) sum += v   // адреса предсказуемы заранее
    return sum
}

Обе функции линейны по сложности. На практике sumArray на больших объёмах данных обгоняет sumLinked в разы — именно за счёт того, что памяти не приходится ждать: prefetcher успевает подтянуть данные до того, как они понадобятся.

Подход со сплошным массивом предаллоцированных событий применён в Ring Buffer у Disruptor. Обход по нему для producer’а и consumer’а — это sumArray, а не sumLinked. Такой доступ к памяти дружелюбен к железу.

Проверяем цифрами

Всё выше это конспект “по учебнику”, и оно легко может оказаться неточным на практике: современный аллокатор, JIT и иерархия кэшей ведут себя не всегда так, как рисуется на схемах. Поэтому проведём замер: та же пара функций прогнана через микробенчмарк с прогревом на железе.

Мерить System.currentTimeMillis() вокруг цикла — плохая идея: первые вызовы метода интерпретируются, а не выполняются JIT-скомпилированным кодом, GC может вклиниться посреди замера, а один прогон ничего не говорит о разбросе. Инструмент для такого - микробенчмарк-харнесс (я использовал JMH), который:

• несколько раз “прогревает” код (даёт JIT время скомпилировать горячий путь) и только потом начинает считать время;
• повторяет измерение много раз в нескольких отдельно стартованных JVM (fork), чтобы усреднить и увидеть разброс;
• умеет мерить время с точностью до наносекунды и сам защищает бенчмарк от того, что компилятор возьмёт и выкинет “бесполезный” код, который ни на что не влияет (dead code elimination) — обычная ловушка ручных замеров.

Конкретные настройки: 5 итераций прогрева по 300 мс + 5 измерительных итераций по 500 мс, повторено в 3-х отдельных JVM - то есть 15 независимых замеров на каждую точку с прогретым JIT. Считалось на JDK 25 (обычный OpenJDK), байткод под JIT, как выполняется большинство Java/Kotlin-кода в проде. Железо — MacBook Pro на Apple M2 Max: у P-ядра 128 КБ кэша L1, у кластера P-ядер общий L2 на 16 МБ, оперативной памяти 32 ГБ.

Кроме массива и списка — ещё два варианта

Чтобы не путать “промах кэша” со “связным списком вообще”, в замер добавлены ещё две структуры между двумя крайностями:

Первая добавка — “дружелюбный” связный список: те же узлы Node, что и раньше, но создаются и связываются в одном и том же порядке, от первого до последнего:

fun buildSequentialLinkedList(size: Int): Node {
    val nodes = Array(size) { Node(it.toLong()) }
    for (i in 0 until size - 1) nodes[i].next = nodes[i + 1]
    return nodes[0]
}

Аллокатор кладёт объекты, созданные подряд, почти впритык друг к другу в памяти — значит, физические адреса узлов тут почти такие же предсказуемые, как у массива. Разница с массивом только в том, что каждое значение приходится доставать через лишний прыжок по ссылке.

Вторая добавка — перемешанный список: те же самые узлы (созданы в том же порядке 0..N-1, лежат по тем же адресам), но next теперь связывает их в случайном порядке — один цикл, построенный тасовкой Фишера — Йетса, чтобы обход всё равно прошёл каждый узел ровно один раз.

fun buildShuffledLinkedList(size: Int, seed: Long): Node {
    val nodes = Array(size) { Node(it.toLong()) }
    val order = IntArray(size) { it }
    val random = Random(seed)
    for (i in size - 1 downTo 1) {           // тасовка Фишера — Йетса
        val j = random.nextInt(i + 1)
        val tmp = order[i]; order[i] = order[j]; order[j] = tmp
    }
    for (i in 0 until size - 1) nodes[order[i]].next = nodes[order[i + 1]]
    return nodes[order[0]]
}

Тасовка Фишера — Йетса — стандартный способ получить случайную перестановку массива без перекоса в вероятностях: проход с конца массива к началу, на каждом шаге i текущий элемент меняется местами со случайным элементом из диапазона 0..i включительно. За один линейный проход любой порядок из N! возможных получается с равной вероятностью — в отличие от наивных подходов вроде “для каждого элемента выбрать случайную пару”, которые на практике дают смещённое распределение.

Здесь она нужна не просто для случайности, а для того, чтобы обход остался связным. Массив order после тасовки — это перестановка индексов 0..N-1, и код связывает узлы next-ссылками строго в этом порядке: order[0] → order[1] → ... → order[N-1]. Получается один сплошной путь через все N узлов без пропусков и без повторов. Если вместо этого присвоить каждому узлу next на случайный другой узел независимо, гарантии такой уже нет: результат может распасться на несколько отдельных циклов, часть узлов вообще не попадёт в цепочку от head, а часть окажется внутри цикла, из которого sumLinked не выйдет никогда. Фишера — Йетса даёт вперемешку случайные адреса и при этом список ровно с одним проходом каждого узла.

Здесь адрес следующего узла больше никак не связан с адресом текущего — это и есть pointer chasing, который описан в начале заметки.

Третья добавка — ArrayList<Long>. Формально это тоже сплошной массив, но массив ссылок на объекты: сами числа хранятся как упакованные (боксированные) Long, отдельные объекты в куче. Это промежуточный случай: разыменование есть, а физическая раскладка почти как у последовательного списка, потому что боксы создаются при заполнении списка подряд.

Размеры взяты так, чтобы пересечь границы кэша: 1 000 элементов (long[] на 8 КБ — с запасом влезает в L1), 100 000 (long[] на 800 КБ, узлы ≈3 МБ — всё ещё влезает в L2 на 16 МБ) и 10 000 000 (long[] на 80 МБ, узлы ≈320 МБ — заведомо больше любого кэша на этой машине).

Результаты

Итоговое время одного полного обхода (наносекунды на операцию, ± — это полуширина 99,9%-го доверительного интервала по 15 замерам):

size	array	boxedArrayList	linkedSequential	linkedShuffled
1 000	276.6 ± 1.7	365.4 ± 1.9	1 760.0 ± 16.3	1 767.1 ± 25.8
100 000	29 741.8 ± 256.5	42 790.5 ± 188.3	177 102.1 ± 2 220.1	604 718.1 ± 8 318.8
10 000 000	3 009 404.6 ± 31 933.9	5 638 869.1 ± 161 506.4	18 813 440.5 ± 203 512.8	1 079 262 844.5 ± 18 622 236.9

В пересчёте на один элемент (наносекунд на элемент) картина понятнее:

size	array	boxedArrayList	linkedSequential	linkedShuffled
1 000	0.28	0.37	1.76	1.77
100 000	0.30	0.43	1.77	6.05
10 000 000	0.30	0.56	1.88	107.93

Что это значит

Главное подтверждается, причём с запасом. На 10 миллионах элементов pointer chasing (linkedShuffled) медленнее массива в 359 раз и медленнее “дружелюбного” списка в 57 раз, при абсолютно одинаковой сложности O(n) у всех вариантов. Разница на элемент между shuffled и sequential на этом размере — это 107.93 − 1.88 ≈ 106 наносекунд, и это уже чистая цена одного промаха кэша (похода в оперативную память), без всяких примесей. На частоте процессора около 3,5–3,7 ГГц это порядка 370–390 тактов — прямое попадание в “порядка сотен тактов”, о которых говорилось в начале заметки.

Но есть нюанс, который в исходном рассуждении не звучал. Отношение “дружелюбного” списка к массиву держится на уровне 6–6.4 раза на всех трёх размерах: и там, где данные заведомо не помещаются в кэш, и там, где 1000 узлов целиком лежат в L1. Если бы дело было в промахах кэша, этот разрыв рос бы вместе с размером данных, как это происходит у shuffled-варианта. А он не растёт. Значит, шестикратный штраф — цена самой формы обхода: чтобы узнать адрес следующего узла, процессор обязан сначала дождаться загрузки текущего. Он не может запустить несколько таких чтений параллельно и держать их “в полёте” одновременно, как это происходит с независимыми друг от друга чтениями массива. Даже там, где prefetcher вообще не нужен, потому что все данные и так горячие в кэше, связный список всё равно проигрывает массиву в разы — просто из-за цепочки зависимостей между чтениями.

ArrayList<Long> — это pointer chasing в лёгкой форме. Он тоже проигрывает массиву, но на 25–87%, не в разы, и разрыв растёт вместе с размером данных (0.37 против 0.28 нс на 1000 элементах, 0.56 против 0.30 — на 10 миллионах). Причина та же арифметика: значение упаковано в отдельный объект, поэтому на каждый элемент уходит два обращения к памяти — сначала за ссылкой в самом массиве, потом за значением внутри Long. Пока всё помещается в кэш, второй поход почти всегда попадание; когда данные вырастают за пределы кэша, он всё чаще оказывается промахом. Вывод: скорость определяется тем, сколько независимых обращений к памяти нужно на один элемент и насколько предсказуемы их адреса.

На маленьких данных разницы почти нет. На 1000 элементах “дружелюбный” и перемешанный список неотличимы — 1760 нс против 1767 нс, это шум измерения. Весь список из тысячи узлов (около 32 КБ) целиком помещается в кэш вне зависимости от того, в каком порядке связаны узлы, поэтому порядку адресов буквально не на чем сказаться: промахов кэша нет ни там, ни там. Разрыв в сотни раз — эффект больших объёмов данных. На типичных для бэкенда небольших коллекциях разница между списком и массивом — это 6 раз за счёт цепочки зависимостей, а не сотни раз за счёт кэша.