Где живут узлы

Когда вы создаёте Node через Node(), Python запрашивает у аллокатора блок памяти под объект. Аллокатор отдаёт какой-то свободный блок — не обязательно рядом с предыдущим. Между узлами могут жить другие объекты, могут быть «дыры», узлы могут быть в разных страницах памяти.

Это и есть суть проблемы linked list: узлы разбросаны по памяти. Cache line (64 байта) почти никогда не содержит двух соседних по логике узлов. Каждое node = node.next — это потенциально cache miss.

Что происходит в CPU при sum:

1. Прочесть head (адрес N1).
2. Загрузить cache line N1 из RAM (200-400 тактов в худшем случае, ~4 в L1).
3. Прочитать value и next.
4. Перейти по next к N2 — другая cache line. Снова возможный cache miss.
5. И так до конца.

Каждый узел = потенциальный cache miss. На 1M узлов это до 1M штрафов по 200-400 тактов = миллионы тактов потерь.

Зачем prefetcher и почему он не помогает

Современные CPU имеют prefetcher — аппаратный механизм, который предсказывает следующие чтения и загружает данные в кэш заранее. Для массива это работает идеально: prefetcher видит «читаю xs[0], xs[1], xs[2]» — линейный паттерн — и подгружает xs[3..10] заранее. К моменту, как программа их запросит, данные уже в L1.

Для linked list prefetcher не помогает: следующий адрес можно узнать только после прочтения текущего узла. Это сериализованная зависимость:

read N1 -> get N1.next -> read N2 -> get N2.next -> read N3 -> ...

Параллелизировать нельзя. Pipeline CPU простаивает в ожидании каждого чтения. Это и есть pointer chasing.

В массиве чтение xs[i+1] не зависит от xs[i] — prefetcher и out-of-order execution разворачивают это на параллельные чтения. Linked list блокирует обе оптимизации.

Бенчмарк: суммирование 1M элементов

Сравним list, deque и наш самописный linked:

import time

class Node:
    __slots__ = ('value', 'next')
    def __init__(self, value, next_=None):
        self.value = value
        self.next = next_

N = 1_000_000

# 1. Python list
lst = list(range(N))
t0 = time.perf_counter()
total = 0
for x in lst:
    total += x
t1 = time.perf_counter()
print(f"list:          {(t1-t0)*1000:>7.2f} ms")

# 2. Свой singly linked
head = None
for x in reversed(range(N)):
    head = Node(x, head)
t0 = time.perf_counter()
total = 0
node = head
while node is not None:
    total += node.value
    node = node.next
t1 = time.perf_counter()
print(f"linked (self): {(t1-t0)*1000:>7.2f} ms")

# 3. collections.deque (block-linked, разберём в уроке 5)
from collections import deque
dq = deque(range(N))
t0 = time.perf_counter()
total = sum(dq)
t1 = time.perf_counter()
print(f"deque:         {(t1-t0)*1000:>7.2f} ms")

# 4. numpy для сравнения
import numpy as np
arr = np.arange(N, dtype='int64')
t0 = time.perf_counter()
total = arr.sum()
t1 = time.perf_counter()
print(f"numpy:         {(t1-t0)*1000:>7.2f} ms")

Типовой результат (CPython 3.13, Apple M-серии):

list:            38.50 ms
linked (self):  140.20 ms        # в 4 раза медленнее list!
deque:           37.10 ms        # как list
numpy:            0.50 ms        # для контекста

Linked list в 4 раза медленнее list. И это в Python, где overhead интерпретатора маскирует cache miss-стоимость. В C/Rust разница ещё больше: чистый array sum получает SIMD и prefetcher, linked list — pointer chasing с миллионом cache miss-ов.

Почему deque не страдает

collections.deque — это block-linked list: список блоков, каждый блок — массив из ~64 значений (об этом подробно в уроке 5 модуля и модуле 7). Pointer chasing идёт от блока к блоку, не от элемента к элементу. На 1M значений = ~16000 блоков вместо 1M узлов. В 64 раза меньше cache miss-ов. Плюс внутри блока — спокойная итерация по массиву.

Это инженерное решение: «много маленьких» (linked) объединяется в «несколько средних» (block-linked). Получаем O(1) append/popleft (как у linked) и хорошую cache locality (как у array). Это пример того, как реальные структуры адаптируются под железо.

Когда linked list всё-таки выигрывает

Не везде кэш-миссы убивают linked list. Есть сценарии, в которых linked всё-таки оправдан:

1. Frequent middle-insertion с известным указателем. Например, LRU cache — get/put должны быть O(1), кэш-миссы здесь не критичны, потому что операций мало.
2. Persistent (immutable) data structures. Когда нужно историческое version-list, share хвост между версиями. В Haskell/Clojure это базовая стратегия.
3. Очень большие узлы. Если value сам по себе уже 64 байта и больше, то overhead от next-указателя несущественен.
4. Хорошая локальность через arena. Если все узлы аллоцированы из одного большого блока (memory pool), они могут лежать подряд. В C/Rust это распространено — линкед лист на arena почти не страдает от pointer chasing.

В обычном Python ни один из этих сценариев не оправдывает прямой self-made linked list. Используйте deque или list.

Замер cache miss-ов

На Linux можно посмотреть реальные cache miss-ы через perf:

# собираем статистику cache miss-ов
perf stat -e cache-misses,cache-references python bench_linked.py

Типовой вывод покажет миллионы cache-miss для linked vs тысячи для list. На macOS можно использовать dtrace (требует privilege) или Instruments.

Для python это сложнее измерить «честно» (overhead интерпретатора сильно маскирует), но для C-кода с массивом и связным списком разница в cache miss-ах различима в десятки раз.

Сводная таблица

Попробуй сам

Сравните, насколько pointer chasing медленнее линейного скана, на одинаковом объёме данных:

import time

# два варианта 1M указателей
import random
N = 1_000_000

# Вариант A: указатели идут по индексам подряд
ordered = list(range(N))
random.shuffle(ordered)  # перемешаем чтобы это была pointer-chase цепочка

# Создаём цепочку: следующий индекс хранится в текущей ячейке
chain = [0] * N
prev = -1
for idx in ordered:
    if prev != -1:
        chain[prev] = idx
    prev = idx
chain[prev] = -1  # конец

# Pointer chasing: ходим по chain
t0 = time.perf_counter()
i = ordered[0]
count = 0
while i != -1:
    i = chain[i]
    count += 1
t1 = time.perf_counter()
print(f"pointer chase {count}: {(t1-t0)*1000:.2f} ms")

# Линейный скан: просто sum
t0 = time.perf_counter()
total = sum(chain)
t1 = time.perf_counter()
print(f"linear scan:  {(t1-t0)*1000:.2f} ms")

Pointer chase обычно в 5-20 раз медленнее линейного скана на больших N — это и есть стоимость cache miss на каждом узле.