4 November 2008

Разработка на PC и производительность — Memory Latency

Website development
Herb Sutter (автор Exceptional C++, бывший глава ISO C++ standards committee, мистер Free Lunch Is Over и прочая, и прочая) работает в Microsoft и иногда по средам читает атомные лекции.

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

Лекция называлась «Machine Architecture: Things Your Programming Language Never Told You» (здесь можно скачать презентацию и видео) и была про конкретную часть abstraction penalty — Memory 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 (!!!!!!)


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

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

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

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

Как это лечить — разумеется кешем и иерархией. L1 — 2 такта, L2 — 14 тактов, L3 — lets 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

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



Тред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<T> vs std::vector<T*> (это, как все знают, и массив объектов в Java или .net ).

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

На gamedeff вот тут описывался хороший пример такой борьбы за локальность.

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

И я не знаю, что с этим делать в 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

Остается бороться, мужики. Понимать цену абстракции и на этом уровне, не давать мозгам расслабляться и жить в восьмидесятых годах.
Tags:gamedeffperformancelatencymemory
Hubs: Website development
+128
8.5k 92
Comments 70
Top of the last 24 hours