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.
Я попытаюсь коротко рассказать о ключевой мысли лекции. Она простая, очевидная и тысячу раз сказанная. Думаю, еще раз повторить азбуку — никогда не повредит.
Bandwidth — это ширина канала. Сколько можно прокачать данных за секунду, сколько можно пустить инструкций чтобы полностью загрузить ALU и так далее.
Latency — это длина канала, то есть через какое время к тебе придут данные, которые ты попросил. Через сколько тактов к тебе придет запрошенный бит из памяти, через сколько тактов будет готов результат инструкции, когда команда пройдет до конца пайплайна и так далее.
И они, разумеется, друг на друга влияют. Как только нужен результат, а делать больше нечего — весь bandwidth простаивает из-за latency. Запросили память, которой нет в кеше — сидим, ждем память. Захотели выполнить инструкцию, которой необходим результат предыдущей — ждем ее выполнения. Это создает «пузыри» в канале и соответственно уменьшает загрузку.
Херб в презентации использует пример нефтепровода, он вполне наглядный. Можно прокачивать дикое количество баррелей в минуту, но каждый баррель идет до места назначения несколько дней. В чистом виде bandwidth и latency.
Практически важный момент в том, что bandwidth всегда легко покупать. Поставить два процессора, брать из памяти за раз в два раза больше данных, поставить два компьютера в конце концов. Latency же гораздо дороже — две женщины не родят ребенка за 4.5 месяцев, и продвигается оно только прогрессом — увеличивать частоты, уменьшать размеры элементов, менять технологию и так далее.
Ща, у Херба там табличко была…
Из таблички хорошо видно, что процессор хорошо растет, размер памяти хорошо растет, 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 взаимодействие тредов — ушибешься.
Например:
Тред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 вот тут описывался хороший пример такой борьбы за локальность.
Но точно померять и предсказать все равно не получается. Все очень толсто, нелинейно и непрозрачно. Под тобой работает большая машина с непонятной логикой и, что хуже, непонятной загрузкой. Оживет в бэкграунде сеть и все спутает. Или индексер, упаси господь.
Вы уж простите, я из приложений писал только игры и буду рассуждать и сравнивать платформы только на примере любимого геймдева.
С одной стороны, хочется больше контроля. Иметь четкое место в кеше, где я могу иметь гарантированное время доступа. Иметь некие гарантии того, что мне не попортят кеш при первом же 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
Остается бороться, мужики. Понимать цену абстракции и на этом уровне, не давать мозгам расслабляться и жить в восьмидесятых годах.
Я наконец-то на одну такую попал, и очень радовался. На умных мужиков всегда радостно поглядеть и послушать.
Для отчета — кроме Херба, видел живого Олександреску и живого 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
Остается бороться, мужики. Понимать цену абстракции и на этом уровне, не давать мозгам расслабляться и жить в восьмидесятых годах.