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

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

  • alll

    Ну положим в мультитредном коде
    flag1 = 1;
    if (flag2 != 0) { …}
    flag1/2 всё одно надо объявлять как volatile, так что у компилятора есть возможность понять, что f1 в out of order не пролезет.

  • IronPeter

    volatile – он не memory barrier. Ни разу. Если бы было достаточно volatile, то люди не придумывали бы EnterCriticalSection.

  • IronPeter

    In C, the volatile keyword is provided to inhibit optimisations which remove or reorder memory operations on a variable marked as volatile. This will provide a kind of barrier for interruptions which occur on a single CPU, such as signal handlers or concurrent threads on a uniprocessor system. However, the use of volatile is insufficient to guarantee correct ordering for multiprocessor systems because it only impacts reorderings performed by the compiler, not those which may occur at runtime such as those performed by the CPU.

    http://en.wikipedia.org/wiki/Memory_barrier

    Многопоточное программирование – это сложно. Современные многоядерные процессоры вынуждены работать в слабо когеретном окружении. Иногда полезно задумываться о том, что происходит, когда один процессор модифицирует переменную, которая лежит в кешах других процессоров. Как HW инженеры такое дизайнят – одному Богу известно.

  • IronPeter

    На самом деле, очень хорошо прочувствовать силу и слабость современных архитектур можно, чуть-чуть пописав на SPU. Надо посчитать один dot для векторов – считай пачкой для 4, в SOA стиле. Только латентности операций никак не ниже 4, так что приходится считать сразу 16 dot. Вместо одного – 16.

    Про линейку памяти тоже очень хорошо.

    Вот есть XDR память, есть DMA запрос из нее в локальную память SPU. Ну естественно, что src в XDR памяти должен быть выровнен на линейку ( 128 байт ). Нетривиально, что выравнивать надо и в локальной памяти. Казалось бы – нахуй, там все плоское! А вот надо. Не будешь выравнивать – потеряешь bandwidth. В два раза.

  • CEMEH

    Вах, коммент про SPU был аж четвертым! Афигеть!

  • IronPeter

    Я кстати сурово не согласен про неудобство SPU в качестве multithreaded среды. Существующие обертки вполне себе гармонично запускают spe threads на освободившихся мультипроцессорах.

    Есть апулеты, которые так и запускаются под управлением операционной системы. Особенно меня воткнул пример от IBM, где апулет копировал из файла A в файл B. Без участия PPU, DMA запросами. CRT полностью на SPU. fopen, mmap, memcopy ( внутри DMA ). Запускается из командной строки. Запустишь сто штук – будут тихонько себе ждать очереди.

  • look4awhile

    я тоже не согласный про SPU в качестве multithreaded среды.
    но замечу, что если делать job-based среду – выйдет гораздо лучше.
    и даже файберы

  • CEMEH

    Ну в общем и целом да – много процессоров, которые запускают jobs выглядит неплохо. Может, и можно баланисровать независимыми процессорами, а не timeslice.
    Там сразу оговорка – “если на одном процессоре много приложений”.

    То есть, сделать multithread-среду можно. На PC не заживет только. Чтобы сколько-то программ стали писать Jobs…

  • CEMEH

    Поторопился. Возможно, вот это все увеличение количества ядер позволит делать такую модель. Чтобы некоторые приложения могли сказать “это мое ядро, я могу локать куски его кеша” и фактически были jobs.
    С другой стороны, L2 пока общий.

  • http://virtul.livejournal.com virtul

    Статья классная, спасибо.

    >И это малая часть проблем. Я бы сказал, фундаментальные – backward compatibility и совсем другой >чем в играх баланс “performance против стоимости разработки”.
    +5. Еще есть такая вещь как шарп :)

  • CEMEH

    .net, java и прочее – как раз еще один шаг в строну “уменьшения стоимости разработки” ценой производительности и контроля.

  • alll

    При чём здесь CriticalSection и прочие семафоромьютексы?

    IronPeter> И будет тотальный превед – memory read на flag1 произойдет очень рано из-за out of order
    IronPeter> (формально, этот read ни от чего не зависит, поэтому его можно делать рано), и никакой синхронизации
    IronPeter> не будет.

    IronPeter> In C, the volatile keyword is provided to inhibit optimisations which remove or reorder memory
    IronPeter> operations on a variable marked as volatile.

    При наличии volаtile “этот read” формально уже зависит. Сумеет ли компилятор транслировать информацию об этой зависимости на уровень, занимающийся оптимизацией конвейера – отдельный философский вопрос, конечно. :)

  • IronPeter

    >Сумеет ли компилятор транслировать информацию об этой зависимости на уровень, занимающийся оптимизацией конвейера – отдельный философский вопрос, конечно

    Это не философский вопрос. Это простой вопрос, допускающий проверку. Компилятор, очевидно, не может это сделать. Потому что уровень “оптимизации конвейера” – он внутри в железе. Язык ассемблера x86 один, железо – разное. Есть, вроде, striclty ordered x86 реализации. Есть более другие.

    Семен очень хорошо и чисто написал.

  • alll

    IronPeter> Компилятор, очевидно, не может это сделать. Потому что уровень “оптимизации конвейера” – он внутри в железе.

    Я особо не вникал, но не вижу причин, запрещающих существования инструкций, оказывающих влияние на уровень “оптимизации конвейера”. Равно как не знаю про существование таковых. Так что для меня это а) не очевидно и б) чисто философский вопрос. :)

    Ну и немного в сторону: http://mejedi.livejournal.com/15674.html

  • Pingback: NilColor » Blog Archive » Уважаю()

  • CEMEH

    Насколько я понимаю, нужно ставить memory barrier чтобы такое работало, т.е. механизмы уже есть. В C++0x будет специальный тип std::atomic, для которого компилятор будет ставить их сам. volatile – не такой.