PC и performance - Latency

Как обычно, начнем издалека.
Дядя Herb Sutter работает в MS, и иногда устраивает аццкие отжыги.
Я наконец-то на один такой попал, и очень радовался. На умных мужиков всегда радостно поглядеть и послушать.
Для отчета - кроме Херба, видел живого Олександреску и живого Walter Bright (который "D"). У них тут, сцуко, гнездо.

Отжыг назывался "Machine Architecture: Things Your Programming Language Never Told You" (здесь можно скачать презентацию и видео) и был про конкретную часть abstraction penalty - Latency.

Я попытаюсь коротко рассказать о ключевой мысли доклада. Она простая, очевидная и тысячу раз сказанная. Думаю, еще раз повторить азбуку - никогда не повредит.


Для самых маленьких, о том что такое Latency и Bandwidth.
Bandwidth - это ширина канала. Сколько можно прокачать данных за секунду, сколько можно пустить инструкций чтобы полностью загрузить ALU и так далее.
Latency - это длина канала, то есть через какое время к тебе придут данные, которые ты попросил. Через сколько тактов к тебе придет запрошенный бит из памяти, через сколько тактов будет готов результат инструкции, когда команда пройдет до конца пайплайна и так далее.
И они, разумеется, друг на друга влияют. Как только нужен результат, а делать больше нечего - весь bandwidth простаивает из-за latency. Запросили память, которой нет в кеше - сидим, ждем память. Захотели выполнить инструкцию, которой необходим результат предыдущей - ждем ее выполнения. Это создает "пузыри" в канале и соответственно уменьшает загрузку.

Херб в презентации использует пример нефтепровода, он вполне наглядный. Можно прокачивать дикое количество баррелей в минуту, но каждый баррель идет до места назначения несколько дней. В чистом виде bandwidth и latency.

Практически важный момент в том, что bandwidth всегда легко покупать. Поставить поставить два процессора, брать из памяти за раз в два раза больше данных, поставить два компьютера в конце концов. Latency же гораздо дороже - две женщины не родят ребенка за 4.5 месяцев, и продвигается оно только прогрессом - увеличивать частоты, уменьшать размеры элементов, менять технологию и так далее.

И вот последние 20 с лишним лет показывают, что latency улучшается гораздо медленней. Особенно - latency памяти.
Ща, у Херба там табличко была...

1980 VAX-11/750 Modern Desktop Improvement since 1980 Clockspeed (MHz) 6 3000 +500x Memory size (RAM, MB) 2 2000 +1000x Memory bandwidth (MB/s) 13 7000(read) +540x 2000(write) +150x Memory latency (ns) 225 ~70 +3x Memory latency (cycles) 1.4 210 -150x

_Winnie C++ Colorizer

Из таблички хорошо видно, что процессор хорошо растет, размер памяти хорошо растет, bandwidth памяти опять же зашибато, а вот latency со времен VAX - стало всего в три раза лучше. В расчете на такты (последняя строка) - ухудшилось в 150 раз.
Что означает, что промах кеша стоит на порядки больше даже самых тяжелых инструкций процессора.

В 80-х годах было просто и здорово - стоимость доступа к памяти была вполне сравнима, а то и меньше, вычислительных инструкций (а на floating point так и вообще),
Есть процессор, диск и память, программист ими непосредственно и оперирует. Код выполняется прозрачно и предсказуем до такта.

Сейчас же в железе на самом деле все по-другому. Доступ к памяти - сотни тактов. Да, за раз можно взять целый cache line (32 или 64 байта), но ждать все равно сотни тактов. В миллисекунду, например, получается обратиться в разные места памяти примерно 10000 раз. 100 объектов разных классов, вызов 10 виртуальных функций в каждом - уже 20+% от миллисекунды. В геймдеве - очень реальные цифры. А трафик памяти, вообще говоря, самое важное что у нас есть.

И это все про память. Если полезли к диску - это уже совсем за пределами добра и зла, там latency в десятки миллионов тактов.

Как это лечить - разумеется кешем и иерархией. L1 - 2 такта, L2 - 14 тактов, L3 - let's say about 40. Отдельно для данных, отдельно для инструкций.
Сложная логика кеша, ноу-хау различных производителей процессоров и прочее.
Кроме этого - обязательно out of order, чтобы пытаться выполнять то, что не зависит от ждущих.
Out of order execution, register renaming, обязательно мощный branch prediction, обязательно стартовать доступы и записи в память как можно раньше. Если бранч пойдет не в ту сторону, это сразу рушит out of order и является катастрофой.
Опять же, там внутри длинный конвейер. На P4 был даже патологически длинный - до 25 инструкций за раз и out of order заглядывал вперед на сотню. На последних процессорах конвеер меньше, но все равно непрозрачный.

Саттер пишет, что на Itanium2 кеш занимает 85% площади процессора.
На Core Duo - я не смог нагуглить, думаю примерно также.
Еще 10 с лишним процентов - логика out of order, branch prediction и прочего добра.
Остаются считанные проценты на собственно ALU, которые реально что-то считают.

Современный процессор - это не вычислитель, а гигантский хардверный эмулятор x86-инструкций.
Вся это нужно для того, чтобы спрятать от программиста latency. Чтобы можно было продолжать программировать в 80-х годах - когда есть только процессор и память, причем к памяти доступаться можно сколько угодно недорого. Чтобы продолжать запускать старый код все лучше, чтобы новый можно было писать также.

И все же - мы пытаемся скрыть падение скорости в 150 раз! Незаметно для программиста! Не изменяя его структур данных! Так, чтобы он не заметил изменения порядка выполнения инструкций!

Разумеется, это занятие никогда не будет оптимальным.

Из того что программист в некотором смысле живет в стране эльфов, Саттер делает два практических следствия.

Первое - это влияет на корректность программ.
Везде, где делаются предположения о последовательности чтений-записей в память, в любимой Саттером многопоточности.
Если, предполагая, что запись int в память атомарна, начать делать lock free взаимодействие тредов - ушибешься.

Например:

Thread1: flag1 = 1; if (flag2 != 0) { ...} // enter critical section

_Winnie C++ Colorizer

Thread2: flag2 = 1; if (flag1 != 0) { ...} // enter critical section

_Winnie C++ Colorizer

Тред1 сначала выставляет flag1 - флаг того, что он хочет shared resource, и проверяет не занят ли второй ресурс другим тредом. Делается предположение, что flag2 проверится только после установки flag1 (чтобы не войти в critical section если она занята другим тредом).
И будет тотальный превед - memory read на flag1 произойдет очень рано из-за out of order (формально, этот read ни от чего не зависит, поэтому его можно делать рано), и никакой синхронизации не будет.
Поэтому нужно честно локать. Полагаться на память как на что-то, что отражает значения переменных - нельзя.

Второе и самое веселое - конечно, производительность.
Уже давно в основном тормозит память. В основном из-за latency, а не bandwidth. Случайное чтение памяти - много дороже целой тучи вычислений. Locality matters, на всех масштабах.

Кстати, что такое "случайное" в реальной программе страшно размазывается из-за непрозрачной иерархии кешей.
Вроде бы если используется много - то и так будет в кеше. С другой стороны, сколько реальный working set в разные моменты - толком и не прикинуть.
А еще оно на каждом процессоре разное. А еще оно крайне зависит от данных. И самое классное - его еще и хрен померять!
Свел пример к синтетическому - он стал помещаться в кеш. Превед.

К счастью (к сожалению?), цена кеш-мисса столь велика, что серьезные проблемы можно померять и сквозь толстую прослойку.
Скорость random access (меряем latency) против sequential access (меряем bandwith) отличается на порядок. Это разница между std::vector vs std::list.
Хуже, это может быть разница между std::vector<Type> vs std::vector<Type*> (это, как все знают, и массив референсов в managed-коде).

В итоге - надо всегда думать о памяти. Как о локальности, так и о затратах.
Мерять, не в память ли уперся. Когда в random access - можно продуктивно думать и решать. И когда в footprint - бывает тоже.

Но точно померять и предсказать все равно не получается. Все очень толсто, нелинейно и непрозрачно. Под тобой работает большая машина с непонятной логикой и, что хуже, непонятной загрузкой. Оживет в бэкграунде сеть и все спутает. Или индексер, упаси господь.

И я не знаю, что с этим делать в PC-мире.
С одной стороны, хочется больше контроля. Иметь четкое место в кеше, где я могу иметь гарантированное время доступа. Иметь некие гарантии того, что мне не попортят кеш при первом же context switch.
Вот например, легко рассуждать о том, как хорошо все в консольном мире. SPU, 256 kb полностью управляемой очень быстрой локальной памяти, четкие запросы в основную память широкими (чтобы прятать latency) DMA-пакетами. Или Xbox360, где можно локнуть на время часть кеша, да еще и попросить GPU из него рендерять.
Ни одна из этих моделей не заживет на PC в чистом виде.
На одном процессоре живет множество тредов одновременно, если каждый будет управлять 256 килобайтами памяти, то при context switch ее всю надо выгрузить и загрузить. Будет тяжелый и долгий context switch, а типично в OS ну просто дофига даже полу-активных тредов.
Локать кеш нельзя позволять по тем же причинам - это означает либо буфферить его в память при context switch, либо забирать его навсегда от других приложений. Если забирать будут даже только активные - остальное станет тормозить.

Хуже, основные аппликейшены - без всяких верхних границ. Могут загрузить документ и в 10 килобайт, и в 100 мегабайт. Размер Excel-таблица может отличаться в тысячи раз, никаких верхних границ по памяти, как на консоли - не поставишь.

Причем и набор железа, и количество памяти всегда разное, таргет вязкий - "кушать памяти поменьше и работать побыстрее". И железо больше эмулирует, чем работает.

Жизнь одного аппликейшена в системе на фиксированном железе без обратной совместимости принципиально отличается от жизни тучи разношерстных на неопределенном железе, со старым кодом и другими требованиями. Чем дальше смотрю, тем больше думаю, что разные миры.

И это малая часть проблем. Я бы сказал, фундаментальные - backward compatibility и совсем другой чем в играх баланс "performance против стоимости разработки". Но об этом можно как-нибудь потом писать бесконечно много.

Напоследок, краткие медитативные цифирки (я брал у себя на домашней машине):

floating point mul: 0.5-4 cycles (на одном ядре)
L1 access (~16-32 kb) : ~2-3 cycles
L2 access (~2-4 mb) : ~15 cycles
Random Memory Access: ~200 cycles
Sequential Access with Prefetch: ~2 bytes/cycle

Остается бороться, мужики. Понимать цену абстракции и на этом уровне, не давать мозгам расслабляться и жить в восьмидесятых годах.

Crossposted to blog.gamedeff.com

UPD:
Must-read статья про то, как и почему работает память и что с этим делать - What every programmer should know about memory
На blog.ff Борис написал отличный пример того, как эти знания применять на практике.