[perf] Асимптотика доступа к памяти
Недавно я писал о том, что один чувак обнаружил странную штуку: асимптотика доступа к памяти не O(1), а O(√N). У меня наконец-то дошли руки сделать какие-то около-математические выкладки.
У этого хорошего человека тоже были свои около-математические выкладки (см. “The Myth of RAM, part II”), но мне они не понравились. Не понравились они мне главным образом тем, что используется физическое понятие информации. Это понятие непрерывно связано с законами термодинамики, квант.мехом и черными дырами. Но при этом оно не связано с принципиальной возможностью извлечь эту информацию.
Поэтому мы попытаемся зайти с другой стороны. Нам нужно некоторое количество памяти. Соответственно нам нужно как-то в пространстве расположить элементы, хранящие память. Интуитивно более-менее понятно, что в трехмерном мире самая плотная упаковка возможна в виде концентрических сфер с общим центром.
Но сферы визуализировать трудно, поэтому давайте возьмем для начала круги. Итак, представим себе, что мы организовали память в виде концентрических кругов с общим центром. Процессор находится в центре круга. Вот так:
Расстояние между кругами одинаково и равняется константе distance, элементы памяти располагаются тоже на определенном расстоянии (определим через плотность заполнения — константа density factor). Естественно, не может быть два элемента памяти в одном и том же месте. Скорость перемещения константа и не превышает скорость света.
Уже по картинке видно, что в реальности элементы памяти блокируют друг-друга. Поэтому не факт, что такая упаковка возможна. Но чтобы сделать возможной такую упаковку нам понадобится всего-лишь перераспределять элементы и увеличивать расстояние от CPU до ближайшего элемента памяти. В результате у нас будут расти константы, а асимптотика останется та же.
Увы, если расписывать максимально точно формулы, то получится слишком много текста для проверки. Поэтому будем пользоваться прикидочным асимптотическим анализом.
Самый простой способ посчитать среднее время — посчитать время доступа ко всему и поделить.
Дальше, все время мы можем определить как сумму времен доступа для каждого круга. На одном и том же круге скорость доступа константа, а вот количество элементов различно. Количество кругов — N.
Общее количество памяти тоже можно определить через сумму на каждом круге:
Круги у нас нас одинаковом расстоянии, скорость фиксированная, поэтому время доступа к любому элемента круга растет линейно к номеру круга. Дальше, количество элементов на круге растет пропроционально радиусу, а он тоже растет линейно. Получаем:
Сумма элементов растет на один порядок быстрее элемента (к примеру, посмотрите на формулу вычисления интеграла степени).
Итак, среднее время доступа у нас растет линейно пропоционально количеству кругов. Теперь нам нужно выразить количество кругов через требуемую память.
Поскольку память растет квадратично количеству кругов, то количество кругов должно расти как корень от требуемой памяти:
В итоге, среднее время доступа к элементу действительно зависит от количества всей памяти.
Теперь, посмотрим что мы можем сделать, что будет влиять на константы, но не на асимптотику:
- Увеличивать количество памяти внутри элемента памяти (ибо мы не можем увеличивать её до бесконечности);
- Заменить круг на полукруг или еще что-нибудь;
- За один раз обходить несколько элементов памяти;
В общем, пространство действий весьма большое. Но очень трудно придумать что-то, что сможет снизить асимптотику.
Теперь вернемся к сферам. На окружностях количество элементов памяти растет пропорционально радиусу (а значит пропорционально номеру круга). А на сферах количество элементов памяти растет квадратично-пропорционально номеру сферы. Соответственно общее количество памяти растет как куб количества сфер.
По тем же формулам высчитываем и получаем, что среднее время доступа к памяти растет как кубический корень.
В двухмерном пространства квадратный корень, в трехмерном кубический корень, и т.д. Поскольку у нас все-же трехмерное пространство, то быстрее кубического корня мы быть не можем.
Если бы мы могли развивать бесконечную скорость, то асимптотика была бы равна O(1).
Если бы мы могли бесконечно плотно упаковывать элементы памяти, то асимптотика была бы равна O(1).
Но это зависимость от общего количества памяти на памяти. Для того, чтобы зависимость соблюдалась от количества выделенной памяти мы обязаны выделять память как можно ближе к центру. И время от времени её перемещать, иначе мы сильно будет просаживаться по скорости.
Увы, наши компьютеры устроены по другому. Поэтому асимптотика на компьютерах будет другая. Важно одно: мы не можем побить этот рекорд никакими физическими ухищрениями. Ну разве что мы можем сделать некоректный асимптотический анализ и попытаться выдать его за правду.
Нечто похожее делается очень часто для численных алгоритмов. Операция сложения чисел по скорости асимптотически равна O(n). Но в современных процессорах реализована поддержка сложения 64-битных. Причем настолько быстро, что сложение десяти-битных чисел от сложения шестидесяти-битных чисел отличается по времени чуть меньше, чем погрешность измерения. В таком случае для простоты анализа мы считаем, что сложение выполняется за O(1). Но так делать можно только очень осторожно.
Можно сказать, что память в наших компьютерах устроена по принципу иерархических кэшей. Чисто теоретически можно посчитать асимптотику доступа к памяти при условии наличия бесконечного уровня кэшей.