Конспект: внешняя память, кеш и локальность

Понятия

Модель внешней памяти (Аггарвал и Виттер, 1988) - быстрая память размера M, медленная, перенос блоками по B элементов; цена - число переносов. Та же модель - кеш процессора: блок - строка кеша.

Промах - обращение к элементу, чьего блока нет в быстрой памяти; вытесняется давно не нужный блок (LRU).

Прогон - отсортированный кусок на диске. Многопутевое слияние - сразу k ≈ M / B прогонов.

Локальность - загруженная строка используется целиком, пока она в кеше. Кеш-независимый алгоритм - локален без знания M и B.

LSM-дерево - вставки копятся в памяти, сбрасываются прогонами и сливаются в фоне.

Что унести

ЦЕНЫ В БЛОКАХ
проход N / B; случайный доступ ≈ N
1024 элемента, B = 16, 8 блоков в памяти:
    подряд 64, случайно 899, с шагом B - 1024
поиск: двоичный ≈ log₂(N / B), B-дерево ⌈log_B N⌉
    10⁸ ключей, B = 512: 18 блоков против 3

ВНЕШНЯЯ СОРТИРОВКА
прогоны по M: 2N/B; слияние k ≈ M/B − 1 путей: 2N/B за проход
всего 2N/B · (1 + ⌈log_{M/B}(N/M)⌉) - и это нижняя граница
один проход слияния, пока N ≤ M² / B
600 чисел, M = 30, B = 5: 2 пути - 5 проходов, 1440; 5 путей - 2, 720
выбор с замещением: прогоны ≈ 2M на случайных, один - на отсорт.,
    по M - на обратном порядке

КЕШ И ЛОКАЛЬНОСТЬ
массив по строкам: обход по строкам n²/B, по столбцам - до n²
транспонирование блоком t × t: 2t строк кеша должны поместиться
    16 × 16, B = 4, 8 строк: обычно 320, блок 2 - 192,
    блок 4 - 128 (граница 2n²/B), блок 8 - 320, рекурсия - 128
кеш-независимо: делить длинную сторону пополам (Фриго и др., 1999)
умножение блоками: три блока по t · t / B строк кеша

B-ДЕРЕВО ПРОТИВ LSM
B-дерево: вставка - чтение и запись листа, 2 случайных обращения
LSM: элемент переписан ~10 раз, но блоками: 0,208 обращения на вставку
по уровням: мало прогонов, много записи (9,9 раза, 2 прогона)
по ярусам: мало записи, много прогонов (1,9 раза, 15 прогонов)
фильтр Блума: 10 бит на ключ - около 1% ложных срабатываний

Ловушки джокера

Линейный - не значит быстрый. Случайный доступ к N элементам в B раз дороже прохода по ним.

Двоичный поиск по файлу. На диске он читает в шесть раз больше блоков, чем B-дерево.

Слияние по два. Терабайт сортируется за семь проходов вместо двух.

Слишком много путей. Буферы не помещаются в память, и слияние становится случайным доступом.

Циклы не в том порядке. Обход по столбцам массива, лежащего по строкам, - промах на каждое обращение.

Блок, который не помещается. Блок 8 × 8 в кеше на 8 строк не лучше обычного цикла.

B-дерево под потоком случайных вставок. Пропускная способность падает до числа случайных обращений диска в секунду.

LSM без фильтров Блума. Чтение отсутствующего ключа открывает все прогоны.

• Полувнешний Крускал: внешняя сортировка и скан рёбер, union-find на вершины в RAM; I/O Sort(m)+Scan(m). Filter-Kruskal после лёгкой части отбрасывает тяжёлые рёбра внутри уже связанных компонент.

• Многофазное слияние трёх файлов распределяет прогоны по соседним числам Фибоначчи, пустой вход становится новым выходом. Недостачу дополняют фиктивными прогонами; число фаз не равно числу полных проходов всех записей.