Мифы о кэше процессора, в которые верят программисты

https://software.rajivprab.com/2018/04/29/myths-programmers-believe-about-cpu-caches/
  • Перевод
Как компьютерный инженер, который пять лет занимался проблемами кэша в Intel и Sun, я немного разбираюсь в когерентности кэша. Это одна из самых трудных концепций, которые пришлось изучить ещё в колледже. Но как только вы действительно её освоили, то приходит гораздо лучшее понимание принципов проектирования систем.

Вы можете удивиться: зачем же разработчику ПО думать о механизме кэширования в CPU? Отвечу. С одной стороны, многие понятия из концепции когерентности кэша непосредственно применимы в распределённых системах и на уровнях изоляции СУБД. Например, представление реализации когерентности в аппаратных кэшах помогает лучше понять разницу в моделях согласованности (консистентности) — отличие строгой согласованности (strong consistency) от согласованности в конечном счёте (eventual consistency). У вас могут появиться новые идеи, как лучше обеспечить согласованность в распределённых системах, используя исследования и принципы из аппаратного обеспечения.

С другой стороны, неправильные представления о кэшах часто приводят к ложным утверждениям, особенно когда речь идёт о параллелизме и состоянии гонки. Например, часто говорят о трудности параллельного программирования, потому что «у разных ядер в кэшах могут быть разные/устаревшие значения». Или что квалификатор volatile в языках вроде Java нужен, чтобы «предотвратить локальное кэширование общих данных» и принудительно «читать/записывать только в основную память».

Такие заблуждения в основном безвредны (и могут быть даже полезны), но также ведут к плохим решениям при проектировании. Например, разработчики могут подумать, что они избавлены от вышеупомянутых ошибок параллелизма при работе с одноядерными системами. В действительности даже одноядерные системы подвержены риску ошибок параллелизма, если не используются соответствующие конструкции параллелизма.

Или ещё пример. Если переменные volatile действительно каждый раз пишутся/считываются из основной памяти, то они будут чудовищно медленными — ссылки в основной памяти в 200 раз медленнее, чем в кэше L1. На самом деле volatile-reads (в Java) часто настолько же производительны, как из кэша L1, и это развенчивает миф, будто volatile принуждает читает/записывать только в основную память. Если вы избегали volatile из-за проблем с производительностью, возможно, вы стали жертвой вышеуказанных заблуждений.

Важность согласованности


Но если у разных ядер собственный кэш, хранящий копии одних и тех же данных, не приведёт ли это к несоответствию записей? Ответ: аппаратные кэши в современных процессорах x86, как у Intel, всегда синхронизируются. Эти кэши не просто тупые блоки памяти, как многие разработчики, похоже, думают. Наоборот, очень сложные протоколы и встроенная логика взаимодействия между кэшами обеспечивает согласованность во всех потоках. И всё это происходит на аппаратном уровне, то есть нам, разработчикам программного обеспечения/компиляторов/систем, не нужно об этом думать.

Кратко объясню, что имеется в виду под «синхронизированными» кэшами. Здесь много нюансов, но в максимальном упрощении: если два разных потока в любом месте системы читают с одного и того же адреса памяти, то они никогда не должны одновременно считывать разные значения.

В качестве простого примера, как непротиворечивые кэши могут нарушить вышеупомянутое правило, просто обратитесь к первому разделу этого учебника. Ни один современный процессор x86 не ведёт себя так, как описано в учебнике, но глючный процессор, безусловно, может. Наша статья посвящена одной простой цели: предотвращению таких несоответствий.

Наиболее распространённый протокол для обеспечения согласованности между кэшами известен как протокол MESI. У каждого процессора своя реализация MESI, и у разных вариантов есть свои преимущества, компромиссы и возможности для уникальных багов. Однако у всех них есть общий принцип: каждая строка данных в кэше помечена одним из следующих состояний:

  1. Модифицированное состояние (M).
    1. Эти данные модифицированы и отличаются от основной памяти.
    2. Эти данные являются источником истины, а все остальные источники устарели.
  2. Эксклюзивное (E).
    1. Эти данные не модифицированы и синхронизированы с основной памятью.
    2. Ни в одном другом кэше того же уровня нет этих данных.
  3. Общее (S).
    1. Эти данные не модифицированы и синхронизированы.
    2. В других кэшах того же уровня тоже (возможно) есть те же данные.
  4. Недействительное (I).
    1. Эти данные устарели и не должны использоваться.

Если мы применяем и обновляем вышеуказанные состояния, то можно добиться согласованности кэша. Рассмотрим несколько примеров для процессора с четырьмя ядрами, у каждого из которых собственный кэш L1, а также глобальный кэш L2 на кристалле.

Запись в память


Предположим, что поток на core-1 хочет записать в память по адресу 0xabcd. Ниже приведены некоторые возможные последовательности событий.

Попадание в кэш


  1. В L1-1 есть данные в состоянии E или M.
  2. L1-1 производит запись. Всё готово.
    1. Ни в одном другом кэше нет данных, так что немедленная запись будет безопасной.
    2. Состояние строки кэша изменяется на M, поскольку она теперь изменена.

Промах локального кэша, попадание одноуровневого кэша


  1. В L1-1 есть данные в состоянии S.
    1. Это значит, что в другом одноуровневом кэше могут быть эти данные.
    2. Та же последовательность применяется, если в L1-1 вообще нет этих данных.
  2. L1-1 отправляет Request-For-Ownership в кэш L2.
  3. L2 смотрит по своему каталогу и видит, что в L1-2 сейчас есть эти данные в состоянии S.
  4. L2 отправляет snoop-invalidate в L1-2.
  5. L1-2 помечает данные как недействительные (I).
  6. L1-2 отправляет запрос Ack в L2.
  7. L2 отправляет Ack вместе с последними данными в L1-1.
    1. L2 проверяет, что в L1-1 эти данные хранятся в состоянии E.
  8. В L1-1 теперь последние данные, а также разрешение войти в состояние E.
  9. L1-1 осуществляет запись и изменяет состояние этих данных на M.

Чтение памяти


Теперь предположим, что поток на core-2 хочет считать с адреса 0xabcd. Ниже приведены некоторые возможные последовательности событий.

Попадание кэша


  1. L1-2 имеет данные в состоянии S, E или M.
  2. L1-2 считывает данные и возвращает в поток. Готово.

Промах локального кэша, промах кэша верхнего уровня


  1. L1-2 имеет данные в состоянии I (недействительное), то есть не может их использовать.
  2. L1-2 отправляет запрос Request-for-Share в кэш L2.
  3. В L2 тоже нет данных. Он считывает данные из памяти.
  4. L2 возвращает данные из памяти.
  5. L2 отправляет данные в L1-2 с разрешением войти в состояние S.
    1. L2 проверяет, что в L1-2 эти данные хранятся в состоянии S.
  6. L1-2 получает данные, сохраняет их в кэше и отправляет в поток.

Промах локального кэша, попадание кэша верхнего уровня


  1. В L1-2 есть данные в состоянии I.
  2. L1-2 отправляет запрос Request-for-S в кэш L2.
  3. L2 видит, что в L1-1 данные в состоянии S.
  4. L2 отправляет Ack в L1-2, вместе с данными и разрешением войти в состояние S.
  5. L1-2 получает данные, сохраняет их в кэше и отправляет в поток.

Промах локального кэша, попадание одноуровневого кэша


  1. В L1-2 есть данные в состоянии I.
  2. L1-2 отправляет запрос Request-for-S в кэш L2.
  3. L2 видит, что в L1-1 данные в состоянии E (или M).
  4. L2 отправляет snoop-share в L1-1
  5. L1-1 понижает состояние до S.
  6. L1-1 отправляет Ack в L2 вместе с модифицированными данными, если это применимо.
  7. L2 отправляет Ack в L1-2 вместе с данными и разрешением войти в состояние S.
  8. L1-2 получает данные, сохраняет их в кэше и отправляет в поток.

Вариации


Выше приведены лишь некоторые из возможных сценариев. На самом деле существует много вариаций и нет двух одинаковых реализаций протокола. Например, в некоторых конструкциях используется состояние O/F. В некоторых есть кэши обратной записи, а другие используют сквозную запись. Некоторые используют snoop-трансляции, а другие — snoop-фильтр. В некоторых инклюзивные кэши, а в других — эксклюзивные. Вариации бесконечны, а мы даже не затронули буферы хранения (store-buffers)!

Кроме того, в приведённом примере рассматривается простой процессор всего с двумя уровнями кэширования. Но обратите внимание, что этот же протокол можно применить рекурсивно. Легко добавляется кэш L3, который, в свою очередь, координирует несколько кэшей L2, используя тот же протокол, что приведён выше. У вас может быть многопроцессорная система с «домашними агентами», которые координируют работу нескольких кэшей L3 на совершенно разных чипах.

В каждом сценарии каждому кэшу нужно взаимодействовать только с кэшем верхнего уровня (для получения данных/разрешений) и его потомками (для предоставления/отмены данных/разрешений). Всё это происходит невидимо для программного потока. С точки зрения софта подсистема памяти выглядит как единый, консистентный монолит… с очень переменными задержками.

Почему синхронизация по-прежнему важна


Мы обсудили удивительную мощность и согласованность системы памяти компьютера. Остался один вопрос: если кэши настолько последовательны, то зачем вообще нужны volatile в языках вроде Java?

Это очень сложный вопрос, на который лучше ответить в другом месте. Позвольте только немного намекнуть. Данные в регистрах CPU не синхронизируются с данными в кэше/памяти. Программный компилятор выполняет всевозможные оптимизации, когда дело доходит до загрузки данных в регистры, записи их обратно в кэш и даже переупорядочивания инструкций. Всё это делается при условии, что код будет выполняться в одном потоке. Поэтому любые данные, подверженные риску состояния гонки, следует защищать вручную с помощью параллельных алгоритмов и языковых конструкций вроде atomic и volatile.

В случае квалификатора volatile в Java решение отчасти состоит в том, чтобы заставить все операции чтения/записи идти в обход локальных регистров, а вместо этого немедленно обращаться к кэшу для чтения/записи. Как только данные считаны/записаны в кэш L1, вступает в силу протокол аппаратного согласования. Он обеспечивает гарантированную согласованность во всех глобальных потоках. Таким образом, если несколько потоков читают/записывают в одну переменную, все они синхронизированы друг с другом. Вот как достигается координация между потоками всего за 1 наносекунду.
Поделиться публикацией
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 57
  • +26
    Что-то развенчаных мифов вопреки многообещающему заголовку негусто.
    • –1
      Уж не говоря о том, что самая популярная вычислительная платформа устроена, мягко говоря, не совсем так, как описано в статье.
      • 0
        Ну почему же. На АРМах есть Cache Coherent Interconnect для обеспечения когерентности кешей между кластерами и вариация MESI в пределах кластера.
        • –2
          В том-то и дело, что «вариации». На табличку смотрели? Хуже ARM'а — только Alpha…
          • 0
            Я бы не называл это «хуже» по ряду причин, начиная от очевидно более высокой достижимой производительности (чем компилятору/шедулеру больше позволено, тем лучше) и заканчивая, если хотите, дисциплинированием.
        • 0
          Если говорить о современных армах в мобильниках, то там когерентность кэшей имеется. Может в каких-то древних реализациях и не было, не знаю. Чего в армах по-другому, так это memory ordering, но это кешей и не касается.
          • –1
            Чего в армах по-другому, так это memory ordering, но это кешей и не касается.
            Очень даже касается. DSB не поставите — и всё, можно глюки ловить… долго.

            А он сам по себе не возьмётся из ниоткуда, если у вас переменная как volatile не помечена.
            • 0
              Каким образом перестановка операций чтения и записи касается когерентности кэшей? Барьеры ставят, чтобы соблюдать последовательность load/store операций как написал программист, а не как задумал процессор. Даже в amd64 с его гарантиями всего и вся есть барьеры, т.к. там допускается один вариант перестановки.
              • –1
                В amd64 нормальные инструкции сюрпризов не преподносят, нужно использовать MOVNTxxx инструкции, чтобы «выстрелить себе в ногу». У ARMа же один список хинтов (все эти «inner shareable domain», «outer shareable domain», «point of unification» и прочее) как бы намекает на то, что не всё так так просто.
              • 0
                Потому что когерентность кешей и соблюдение последовательности load/store операций — это эквивалентные проблемы.
                • 0
                  Только при некоторых дополнительных предположениях. Вы можете убрать кеш, но реордеринг/elision это автоматически не уберёт.
                  • +1
                    Именно об этом я и говорю. Система в которой нет кеша но есть реордеринг имеет все те же самые проблемы что и система с некогерентными кешами но без реордеринга.
                    • –2
                      Система с реордерингом, но без кешей — это такой «сферический конь в вакууме». В природе не встречается, насколько я знаю.
                      • –1
                        Но ничего не мешает убрать когерентность кэшей и оставить реордеринг. Это совершенно не связанные между собой вещи. То, что они там программисту примерно теже самые проблемы создают, никакого значения особо не имеет. Статья о кэшах, поэтому и реордеринг в ней упоминать не по теме. Была бы статья о проблемах многопоточных программ с общим изменяемым состоянием, то можно было бы упоминать и то, и другое.
                        • –3
                          То, что они там программисту примерно теже самые проблемы создают, никакого значения особо не имеет.
                          А что тогда имеет? Куда вы собираетесь «сферическое знание» о кешах применять? Для написания фантастики? Это не тематика Хабра, вроде бы…
      • +4
        Замечательная статья, спасибо! Про volatile узнал новое
        • 0
          Но тут больше проблема подготовки данных и мастерства бенчмаркать эти вещи. А не «вы всё врёти». Тоесть вероятность того, что на собеседовании с вас спросят тайминги доступа к кешу и длину кеш-линии — нулевая. Только если вы не идете в какие-нибудь жуткие data oriented вещи, типа программирования графики/физики.
          • 0
            Так они у каждого семейства разные, какой толк их спрашивать. А вот представлять, что процессор это не волшебная коробка, а вполне себе детерминированное устройство, очень полезно.
            • 0
              А вот представлять, что процессор это не волшебная коробка, а вполне себе детерминированное устройство, очень полезно.

              Правда Spectre/Meltdown показали, что процессоры — не слишком то уж детерменированные устройства :)
              • +2
                Правда Spectre/Meltdown показали, что процессоры — не слишком то уж детерменированные устройства :)
                Как раз Spectre/Meltdown работают именно из-за детерменированности кешей. Если бы там времена доступа случайными были бы — ничего бы не работало…
                • +1
                  Нене, с точки зрения обычного, нормального программиста, никакого meltdown в принципе существовать не может. А вот с точки зрения Интела да, кэш отработал отлично.
          • +8
            Мне кажется, автор зря здесь упомянул Java. В данном контексте его утверждения просто опасны.
            Да, на интеловых процессорах есть протокол когерентности кешей. Но java-приложение может работать на других процессорах. Этот протокол может быть выключен. В конце концов, есть распределенные java-машины.
            Плюс, не забываем, что компилятор банально может такой код:
            Integer x = 1;
            while(x > 0) { тут не изменяем x };

            оптимизировать до
            while(true) {...}

            (справедливости ради, самые известные компиляторы, насколько я знаю, так не делают)

            Ну и volatile — это болше чем просто запись\чтение мимо кешей. Это happens before.
            В остальном — очень интересно.
            • 0
              (справедливости ради, самые известные компиляторы, насколько я знаю, так не делают)

              Если компилятор докажет, что x нигде не меняется — очень даже делает.
              • 0
                1. Тут пример плохой (я ведь не статью писал). Здесь не очевидно, что в x может прилететь из другого треда. И вот тут и проблема: согласно java memory model, этого может никогда и не произойти. И компилятор имеет право так считать. А может и произойти.
                2. Там же С++
                • 0
                  Здесь не очевидно, что в x может прилететь из другого треда. И вот тут и проблема: согласно java memory model, этого может никогда и не произойти. И компилятор имеет право так считать. А может и произойти.

                  Это называется undefined behavior, это когда чего-то делать нельзя, но программист всё равно это делает. Компилятор имеет право делать вид, будто UB никогда не происходит, что очень сильно развязывает ему руки в плане оптимизаций. Как следствие, когда программист пытается делать то, чего делать нельзя, в общем случае это заканчивается плохо.
                  2. Там же С++

                  А какая разница, оптимизация одна и та же — обычный constant propagation.
                  • 0
                    Понятно, что это UB. Речь шла о том, что на практике (не)делают самые популярные компиляторы java — оракловый и gnu.
                    Но как уже отметил товарищ из соседней ветки, что не делают компиляторы, делает jit.
              • 0

                Я не понимаю, почему для f_atomic компилятор не имеет права сначала доказать, что terminate нигде не видно, и потом сделать тот же constant propagation.


                А, я зачем-то смотрел только на вывод gcc. clang ровно это и делает. Теперь мне интересно, на самом ли деле он имеет на это право.

              • +1
                Не знаю как в Java, но в C/C++ volatile просто говорит компилятору не пытаться оптимизировать операции с этой переменной. Т.е. каждый раз считывать значение переменной из памяти при обращении к ней. К кешам это никакого отношения не имеет.
                • 0
                  Так в статье же есть ссылка про сравнение
                  componenthouse.com/2016/12/28/comparing-the-volatile-keyword-in-java-c-and-cpp
                  • 0
                    Лично мне это кажется недоработкой Си/С++: отдельные языковая модель исполнения и «железная» модель памяти.

                    В Java и C# все намного проще: есть только одна модель исполнения и памяти, которой JVM/CLR следует; и видя ключевое слово volatile JIT не только отключает оптимизации операций над этим полем — но и сам расставляет барьеры чтобы процессор тоже ничего не напортачил. В частности, volatile read всегда дает барьер чтения, а volatile write — барьер записи.
                    • +2
                      Ну, так С\С++ гораздо ближе к железу. Это их «экологическая ниша». Они созданы для того, чтобы решать проблемы, которые в более высокоабстрактных (не знаю нужного термина) отсутствуют.
                      • –1
                        На самом деле всё проще: C был создан для того, чтобы писать операционную систему (одну).

                        Когда вы пишите операционную систему, то вам нужно как-то общаться с железом, у которого регистры размапированы в память (собственно никаких других у PDP и не было).

                        То, что он оказался удачным и его приспособили в кучу разных других мест — совсем другая история. Хотя тот факт, что низкоуровный механизм, который полвека назад был очень даже к месту там, где его разработали, применили в последующем для кучу разных других задач… ну, плохо, конечно… а чего делать? Других механизмов долгое время не было.
                        • 0
                          Вообще-то, у С ноги растут из В и совсем другой ОС, Multics.
                          • –1
                            Какая разница откуда у него «растут ноги»? Чтобы работать с «железом» на PDP вам нужно точно управлять тем, что и где вы читаете и пишите. Позже, во всемена DOS'а — это тоже было очень важное умение (всякие VGA и прочее просто-таки по спецификации так устроены — там можно записывать в одну и ту же ячейку памяти дважды и получать разные результаты).

                            А вот уже как раз когда появились Linux/Windows, кеши и многопоточность — требования изменились… а применяемый инструмент — остался.
                            • 0
                              В embedded все так же актуальна возможность дважды записать по одному адресу одни и те же данные.
                              • –1
                                В embedded другая проблема: для них зачастую очень полезно уметь писать код, использующий особенности железа. А не код, заточенный под PDP и при этом переносимый на миллион платформ.

                                Для этого C подходит плохо, но его используют за неимением лучшего.
                                • +1
                                  И чем простите мало подходит? Мне известно только то что нет операций работы с битами, приходиться возится с масками. На уровне железа это исправляет компилятор, а на уровне читаемости это исправляется макросами или инлайн функциями.

                                  В embedded, как раз, как нигде важна переносимость на другие платформы. И совсем не понятно чем мешает «заточенность под PDP»
                                  • 0
                                    И чем простите мало подходит?
                                    Там что до банальных вещей, которые процессор вычисляет «на раз» невозможно никак добраться. Ни до флага «overflow», ни до «carry», никуда.

                                    Да, можно пытаться делать странные вещи и надеяться на то, что оптимизатор поймёт и сделает «как надо», как-нибудь так:
                                    #include <inttypes.h>
                                    
                                    struct pair {
                                      uint64_t low;
                                      uint64_t hi;
                                    };
                                    
                                    pair add(pair& a, pair& b) {
                                     pair s;
                                     s.low = a.low + b.low;
                                     s.hi = a.hi + b.hi + (s.low < a.low); //carry
                                     return s;
                                    }
                                    
                                    Вот только…
                                    GCC5 — нормально
                                    GCC6 — ай-ай-ай
                                    GCC7 — всё ещё ай-ай-ай
                                    GCC8 — пофиксили
                                    И это — простейший пример! А если чего посложнее навернуть?

                                    В embedded, как раз, как нигде важна переносимость на другие платформы.
                                    Не знаю, не знаю, пока в основном видел жалобы на то, что попытки использовать низкоуровневое знание о том, как процессор устроен приводят к тому, что компилятор начинает «бузить».

                                    И совсем не понятно чем мешает «заточенность под PDP»
                                    К тому, что заточенность под «железо PDP» в виде volatile, ++/-- и прочего — поддерживаются на всех платформах, а вот вещи, которые современные DSP умеют (скажем переменные с фиксированной точкой) — вынесены в зависящие от конмпилятора расширения (если вообще есть поддержка).
                                    • 0
                                      Понятно, но тут или расширения для компилятора или разные языки для разных процессоров. Хотя в принципе могли и ввести в стандарт опциональные платформозависимые вещи, как ввели COMPLEX.

                                      Но на PDP-11 Вы зациклились, volatile, INC, DEC нужны почти на всем (за DSP не ручаюсь).
                                      • 0
                                        Но на PDP-11 Вы зациклились, volatile, INC, DEC нужны почти на всем (за DSP не ручаюсь)
                                        volatile (в том виде, в каком он изначально появился) не нужен в системе без мапирования регистров на память, а INC и DEC — в большинстве систем устроены совсем не так, как в PDP/VAX, где вы можете одной инструкцией процессора считать данные из массива, сдвинуть индекс и ещё что-нибудь в этими данными посчитать «этакое».

                                        Из распространённых процессоров такое есть разве что в ARM'е, большинство процессоров постфиксный ++/-- в том виде, в каком он есть в C на уровне машинных кодов не поддерживают.

                                        Хотя в принципе могли и ввести в стандарт опциональные платформозависимые вещи, как ввели COMPLEX.
                                        Опционально — оно есть. Но тут мы сходу вляпываемся в переносимость: стоит вам этими типами воспользоваться — так сразу получается, что ваш алгоритм вы уже на декстопе не запустите и под embedded — тоже далеко не под любой.

                                        В сухом остатке: работа с saturation arithmeticой есть на всех современных процессорах (в x86 меньше, в ARM и DSP — больше), но вот как раз её в языке нет, а зато вот те самые «штучки от PDP», которые из большинства процессоров давно пропали — есть…
                  • 0
                    (справедливости ради, самые известные компиляторы, насколько я знаю, так не делают)

                    Компиляторы — да, не делают. А вот JIT вполне может такое устроить...

                    • 0
                      А откуда информация, что это именно jit?
                      • 0
                        Источник не приведу, но вроде как это общеизвестная информация. Во всех языках семейств JVM и .NET компиляторы генерируют байт-код без хитрых оптимизаций, а оптимизацией занимается уже JIT.

                        Это нужно хотя бы потому что только JIT знает целевую платформу в которой будет исполняться код, а также информацию которая доступна только в рантайме; то есть у него попросту больше возможностей оптимизации.
                        • 0
                          Да, спасибо. Я выключил jit — и все отработало.
                          Надо будет почитать на эту тему. Как оказалось, здесь я «плаваю».
                          • 0
                            «Выключил jit» — это вообще как? Если вы имеете в виду использование AOT-компилятора, то он тоже занимается оптимизациями, только у него ограничения иные.
                • +7
                  Миф только один — что кэш «прозрачен» для программиста. Все остальное — детали.
                  • –1
                    Есть языки где это не миф :-)
                  • +1
                    Воистину годное чтиво! Спасибо за перевод.
                    • +1
                      если два разных потока в любом месте системы читают с одного и того же адреса памяти, то они никогда не должны одновременно считывать разные значения.

                      Что-то после слова "одновременно" возникли сомнения в квалификации автора. Во многопоточной среде понятие одновременности довольно расплывчато и вообще не нужно.

                      • 0
                        Одна из немногих статей, которые заставили меня улыбаться во время чтения; чистое удовольствие!

                        Автору спасибо.

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                        Самое читаемое