Иерархия памяти: одна и та же сумма в шесть раз медленнее

Если ты знаешь лестницу кешей, строку кеша и предвыборку и понимаешь, почему обход вразброс медленнее только на больших данных, листай до «Теперь сам».

Как думаешь, во сколько раз медленнее

Два списка по два миллиона дробных чисел. Во втором - те же самые объекты, что в первом, только перемешанные. sum по обоим делает одно и то же: два миллиона сложений, ни одного лишнего действия. Асимптотика одинакова, число операций одинаково. Будет ли разница во времени, и какая?

Ответь себе до чтения. Модель RAM говорит «никакой». Замер на этом сайте - в пять с лишним раз.

На что это похоже

Повар у плиты. На столе - то, что нужно прямо сейчас (L1), на полке над столом - побольше (L2), в холодильнике кухни - ещё больше (L3), а на складе в подвале - всё (оперативная память). Сходить в подвал - минута, взять со стола - секунда. Из подвала приносят не одну луковицу, а ящик (строка кеша). Если повар режет лук по порядку, помощник замечает это и заранее несёт следующий ящик (предвыборка). А если рецепт требует то луковицу, то соль, то рыбу с разных стеллажей - каждый раз минута в подвал.

Механизм: лестница задержек

Порядки задержек на типичном процессоре: L1 - около наносекунды, L2 - несколько, L3 - десяток-другой, оперативная память - около сотни наносекунд. На машине этого сайта (Intel Core i5-3350P) L1 данных - 32 КБ на ядро, L2 - 256 КБ на ядро, L3 - 6 МБ на все четыре ядра. Каждый промах на ступень ниже - это ожидание, в которое процессор мог бы сделать десятки и сотни операций.

Память движется строками по 64 байта: прочитал байт - получил ещё 63 соседних. Предвыборка (prefetch) следит за адресами промахов и, видя шаг подряд или с постоянным шагом, заказывает следующие строки до того, как они понадобятся. Чтение вразброс она предсказать не может.

В CPython список хранит ссылки, а числа - отдельные объекты по 24 байта. Созданные подряд, объекты лежат в памяти подряд: обход списка по порядку идёт и по объектам подряд. Перемешанный список ведёт по тем же объектам скачками.

Правило

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

Разбор: лестница на этой машине

Сумма по списку подряд и вразброс при разном размере данных. Время - лучшее из семи прогонов, в наносекундах на элемент; память - объекты по 24 байта плюс ссылки по 8.

import random
import time


def luchshee(spisok, povtorov):
    best = None
    for popytka in range(7):
        t = time.perf_counter()
        for k in range(povtorov):
            sum(spisok)
        dt = (time.perf_counter() - t) / povtorov
        if best is None or dt < best:
            best = dt
    return best


random.seed(1)
print("элементов  память,КБ  подряд,нс  вразброс,нс  отношение")
for n in [1000, 10000, 100000, 1000000, 4000000]:
    chisla = [float(i) for i in range(n)]
    peremeshany = chisla[:]
    random.shuffle(peremeshany)
    povtorov = max(1, 2000000 // n)
    a = luchshee(chisla, povtorov) / n * 1e9
    b = luchshee(peremeshany, povtorov) / n * 1e9
    pamyat = n * (24 + 8) // 1024
    print(f"{n:>9} {pamyat:>9} {a:>10.1f} {b:>11.1f} {b / a:>10.1f}")

элементов  память,КБ  подряд,нс  вразброс,нс  отношение
     1000        31        7.9         8.0        1.0
    10000       312        7.9         8.9        1.1
   100000      3125        7.9        16.1        2.0
  1000000     31250        8.2        40.8        5.0
  4000000    125000        8.2        51.1        6.2

Столбец «память» - то, что трогает один проход: объекты по 24 байта и ссылки одного списка по 8 (второй список в этом проходе не участвует). Столбец «подряд» не меняется: 8 нс на элемент - это цена прохода sum в CPython: взять ссылку, проверить тип, прибавить число к накопленной сумме, память ему не мешает даже на 125 МБ, предвыборка успевает. Столбец «вразброс» растёт ступенями. 31 КБ - почти весь в L1, разницы нет. 312 КБ - вышли за L2, но в L3: +12%. 3 МБ - L3 ещё вмещает, но промахи L2 на каждом шаге: вдвое. 31 МБ и 125 МБ - в оперативной памяти: в пять-шесть раз.

Разбор: модель внешней памяти против машины

Повторим опыт в модели из прошлого раздела: кеш на 512 строк по 64 байта (32 КБ), объект - 32 байта, по два в строке. Считаем промахи на втором проходе - первый прогревает кеш.

import random

def promahi(poryadok, strok):
    # кеш прямого отображения: строка памяти b живёт в ячейке b % strok;
    # объект i занимает 32 байта, в строке кеша 64 байта - два объекта
    kesh = [-1] * strok
    schet = 0
    for prohod in range(2):              # первый проход прогревает
        for i in poryadok:
            b = i // 2
            if kesh[b % strok] != b:
                kesh[b % strok] = b
                if prohod == 1:
                    schet = schet + 1
    return schet

random.seed(3)
strok = 512                              # кеш 32 КБ: 1024 объекта
print("объектов  подряд  вразброс  (промахов на элемент)")
for n in [256, 1024, 1536, 2048, 4096]:
    podryad = list(range(n))
    vrazbros = podryad[:]
    random.shuffle(vrazbros)
    print(n, round(promahi(podryad, strok) / n, 2),
          round(promahi(vrazbros, strok) / n, 2))

объектов  подряд  вразброс  (промахов на элемент)
256 0.0 0.0
1024 0.0 0.0
1536 0.33 0.46
2048 0.5 0.67
4096 0.5 0.84

Модель верно ловит ступеньку: пока данные помещаются в кеш, промахов нет, за ним - есть. Но отношение она предсказывает около 1,7 (0,84 против 0,5), а машина показала 5-6. Две причины. Модель считает промах подряд таким же дорогим, как вразброс, а на машине его прячет предвыборка: столбец «подряд» в замере не вырос вовсе. И у модели одна ступень, а у машины три кеша, плюс таблица перевода адресов (TLB) - кеш перевода адресов программы в адреса памяти: при чтении вразброс по 125 МБ нужные переводы в него не помещаются, и каждый его промах - ещё один поход в память за таблицей страниц. Граница правила «модель внешней памяти предсказывает время»: она предсказывает, ГДЕ будет ступенька и кто выиграет, а во сколько раз - только замер.

Что ломается без этого

Бенчмарк на маленьких данных. Тест на тысяче элементов показывает, что перемешанная структура «не хуже», - всё лежит в L1. В бою данных в тысячу раз больше, и та же структура в пять раз медленнее.

Структура из узлов, разбросанная временем. Дерево или связный список, построенный за день работы сервиса вперемешку с другими объектами, обходится вразброс, даже если логически идёт по порядку. Свежий бенчмарк, где узлы созданы подряд, этого не покажет.

Сравнение «на моей машине». Размеры кешей у ноутбука и сервера разные: ступенька окажется на других размерах данных.

Зачем это в работе

Отсюда растут массивы вместо списков объектов (NumPy, array, столбцовые таблицы в pandas и в аналитических базах), обход матрицы по строкам, а не по столбцам, сортировка запросов к большой таблице по ключу перед обращением и B-дерево с широкими узлами вместо двоичного дерева поиска даже в памяти. Во всех случаях меняется не число операций, а то, сколько раз процессор ждёт память.

Теперь сам

1. Список из 10 000 перемешанных объектов-чисел занимает около 312 КБ. Будет ли обход вразброс заметно медленнее обхода подряд на этой машине?
2. В модели на 4096 объектах вразброс - 0,84 промаха на элемент, подряд - 0,5. Почему машина показала отношение больше 1,7?
3. Почему обход двумерного списка по столбцам медленнее, чем по строкам, хотя сложений столько же?