Что такое pointer chasing

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

Самый каноничный пример — обход linked list:

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

# Линкед-лист 1 -> 2 -> 3 -> 4 -> ...
def sum_linked(head):
    s = 0
    node = head
    while node:
        s += node.val      # читаем val
        node = node.next   # читаем next — адрес следующего
    return s

CPU выполняет это так:

1. Прочитать node.val -> прибавить к s.
2. Прочитать node.next -> получить адрес следующего узла.
3. Прочитать next.val (но адрес мы узнали только сейчас).
4. Прочитать next.next.
5. И так далее.

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

Sequential access: prefetcher творит чудеса

Контраст — обход массива:

arr = [1, 2, 3, 4, 5, 6, 7, 8]
for x in arr:
    process(x)

CPU видит: «обращения идут по адресам X, X+8, X+16, X+24, …». Это арифметическая прогрессия. CPU включает prefetcher — отдельный аппаратный блок, который начинает асинхронно подтягивать будущие cache lines, пока вы работаете с текущей.

К тому моменту, когда вам понадобится arr[i+8], его cache line уже в L1. Чтение бесплатное.

Когда prefetcher работает хорошо (предсказуемый pattern, не слишком большие данные) — sequential access становится практически бесплатным относительно RAM access. Это разница между 60 ns на элемент и ~1 ns на элемент = до 60x speedup.

Замер: list (массив) vs deque (linked list of blocks) vs class-based linked list

В Python нет «настоящего» linked list в stdlib. collections.deque — это двусвязный список блоков (каждый блок ~64 элемента), что делает его компромиссом между чистым linked list и массивом. Для демонстрации pointer chasing смастерим linked list сами:

import timeit
from collections import deque

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

def make_linked(n):
    head = Node(0)
    cur = head
    for i in range(1, n):
        cur.next = Node(i)
        cur = cur.next
    return head

def sum_linked(head):
    s = 0
    node = head
    while node:
        s += node.val
        node = node.next
    return s

def sum_list(lst):
    s = 0
    for x in lst:
        s += x
    return s

def sum_deque(d):
    s = 0
    for x in d:
        s += x
    return s

N = 1_000_000
linked_head = make_linked(N)
lst = list(range(N))
dq = deque(range(N))

t_linked = min(timeit.repeat(lambda: sum_linked(linked_head), number=3, repeat=3)) / 3
t_list   = min(timeit.repeat(lambda: sum_list(lst), number=3, repeat=3)) / 3
t_deque  = min(timeit.repeat(lambda: sum_deque(dq), number=3, repeat=3)) / 3

print(f"linked list (pointer chasing): {t_linked*1000:>6.0f} ms")
print(f"deque (blocks of ~64):         {t_deque*1000:>6.0f} ms")
print(f"list (array of pointers):      {t_list*1000:>6.0f} ms")
print(f"linked / list ratio:           {t_linked/t_list:.1f}x")

Типичный вывод:

linked list (pointer chasing):    280 ms
deque (blocks of ~64):             52 ms
list (array of pointers):          45 ms
linked / list ratio:               6.2x

Big-O идентичен — все O(n) на обход. Но реальная разница до 6x.

Почему deque близок к list? Потому что внутри deque — двусвязный список блоков по ~64 элемента. Pointer chase происходит только раз в 64 элемента, остальные 63 — sequential внутри блока. Это компромисс, который хорошо работает.

Когда prefetcher не помогает

Prefetcher хороший, но не магия. Он не помогает в случаях:

1. Random access — обращения по случайным адресам. Pattern непредсказуем.
2. Pointer chasing — следующий адрес зависит от данных, prefetcher не знает.
3. Слишком большие шаги (strides) — если читаете каждый 1000-й элемент массива, между чтениями prefetcher не видит «соседства».
4. Слишком много одновременных потоков memory accesses — prefetcher имеет ограниченное число in-flight prefetches.

Это объясняет, почему hash tables (dict, set) на больших размерах внезапно проседают: hash function разбрасывает ключи случайно, prefetcher слепнет.

Pointer chasing в реальном Python

Где в Python мы платим за pointer chasing, хотя не пишем linked list руками?

• list of objects — обход for obj in objects: process(obj.field) это chase через ссылку на obj в куче.
• dict[key].field — двойной chase: указатель в dict-bucket, потом dereference value.
• Атрибуты класса — obj.attr это словарь __dict__ (или slot), снова pointer.
• Recursive data structures — JSON-like dict, tree-структуры.

В DE это критично — pandas DataFrame внутри строит компактные колонки (numpy-arrays), чтобы избежать pointer chasing. df['col'].sum() быстрый — потому что значения в колонке лежат подряд. for row in df.iterrows(): row['col'] медленный — потому что каждая строка восстанавливается как dict-объект.

Замер: dict iteration vs array iteration

import timeit

N = 1_000_000

dct = {i: i for i in range(N)}
lst = list(range(N))
arr = list(dct.values())   # тоже list, но получен из dict

t_dict = min(timeit.repeat(
    """
total = 0
for v in dct.values():
    total += v
""",
    globals=globals(), number=3, repeat=3
)) / 3

t_list = min(timeit.repeat(
    """
total = 0
for v in lst:
    total += v
""",
    globals=globals(), number=3, repeat=3
)) / 3

print(f"dict.values() iter: {t_dict*1000:.0f} ms")
print(f"list iter:          {t_list*1000:.0f} ms")
print(f"slowdown:           {t_dict/t_list:.2f}x")

Типичный вывод:

dict.values() iter:  55 ms
list iter:           45 ms
slowdown:            1.2x

Разница есть, но небольшая — потому что начиная с Python 3.6 dict хранит данные в compact form: внутренний массив values тоже относительно cache-friendly. На более старых Python разница была больше.

Попробуй сам: эффект размера блока

Сделайте свою «псевдо-linked list» с блоками разного размера и измерьте, как меняется производительность:

import timeit

def make_blocks(n, block_size):
    """Сделать pseudo-linked list of blocks"""
    blocks = []
    for i in range(0, n, block_size):
        blocks.append(list(range(i, min(i + block_size, n))))
    return blocks  # list of lists

def sum_blocks(blocks):
    s = 0
    for block in blocks:
        for x in block:
            s += x
    return s

N = 1_000_000
for block_size in [1, 4, 16, 64, 256, 1024]:
    blocks = make_blocks(N, block_size)
    t = min(timeit.repeat(lambda: sum_blocks(blocks), number=3, repeat=3)) / 3
    print(f"block_size={block_size:>5}: {t*1000:>5.0f} ms, blocks={len(blocks):>7}")

block_size=    1:  280 ms, blocks=1000000  -- классический pointer chase, кошмар
block_size=    4:  100 ms, blocks= 250000  -- уже сильно лучше
block_size=   16:   58 ms, blocks=  62500  -- хорошо
block_size=   64:   45 ms, blocks=  15625  -- одна cache line на блок -- оптимум
block_size=  256:   42 ms, blocks=   3906  -- едва быстрее
block_size= 1024:   42 ms, blocks=    977  -- плато

Главное правило для DE

В DE pointer chasing проявляется в самых неожиданных местах:

• Spark UDF на pyspark — каждый row передаётся как Python dict, что pointer-chase кошмарный. Поэтому groupBy().agg() (нативный) на порядки быстрее map(custom_function).
• JSON парсинг наивно — каждый объект — отдельный dict с pointers. orjson ускоряет в 5x именно через лучше layout.
• Pandas iteration vs vectorization — for i in range(len(df)) это chase, df['col'] * 2 — numpy vectorization.

Правило: если можно представить данные как плотный массив значений — представляйте. Если нет — используйте структуры с блоками (deque, B-tree, chunked array) вместо чистого linked list.

В следующем уроке — branch prediction: ещё один способ, которым CPU обманывает медленную RAM. Классический эксперимент с sorted vs unsorted массивом.