С постановкой проблем в прошлой статье мы почти закончили и вывели самое важное – природу состояния гонки и состязания за кэш. В этой статье мы также разберем оптимизацию, порождающую часть проблем синхронизации – instructions reordering, а также механизмы решения вышеуказанных проблем.
В этот раз снова будет Go Assembler, а также снова будут примеры на Go. В прошлый раз это было необходимое зло во имя соответствия реальности
Напоминаю, что эта статья – часть большого цикла разбора языка программирования Golang End 2 End. Но если вы уверены, что понимаете природу многозадачности, многопоточности, проблемы оных, а также то, как выполняются инструкции и пришли разбираться в самых примитивных механизмах синхронизации, то велком
Instructions reordering
Обычно мы считаем, что CPU добросовестно выполняет свои инструкции последовательно. Ровно так, как мы ему сказали. Но это не всегда верно!
Допустим есть код
x = 1ready = true
Сначала в память попадёт x = 1
Потом в память попадёт ready = true
Но в реальности, процессор может переставить местами эти инструкции т.к. они независимы друг от друга и не меняют результат потока исполнения
Причина простая: CPU пытается выполнять код быстрее.
Ему выгодно:
-
Менять порядок независимых операций,
-
Держать значения в регистрах,
-
Откладывать запись в память,
-
Заранее читать данные,
-
Исполнять инструкции спекулятивно.
Для однопоточного кода это обычно незаметно, но для многопоточного – уже нет!
Зафиксируем:
Переупорядочивание инструкций (instruction reordering) – это оптимизация, выполняемая процессором или компилятором, при которой порядок выполнения команд меняется для повышения производительности (ускорения кода), сохраняя при этом логическую последовательность
Пока будем рассматривать в контексте процессора
Пример был чисто демонстрационный, давайте посмотрим более реальный пример с проблемой которая тут решается
Если две инструкции независимы, их можно выполнить параллельно или поменять местами
MOVQ A(SB), AX ; load в AX из памяти переменную AMOVQ B(SB), BX ; load в BX из памяти переменную BADDQ DX, CX ; Сложение двух других переменных
Внимательно рассмотрев код, можно утверждать следующее:
Первая инструкция ждет значение из памяти
Вторая тоже ждет значение из памяти
Третья выполняет операцию над значениями, которые уже есть в регистрах
С точки зрения здравого смысла при условии, что надо выполнить быстрее, выгоднее начать с последней инструкции и в порядке например
ADDQ DX, CX ; Сложение двух других переменныхMOVQ A(SB), AX ; load в AX из памяти переменную AMOVQ B(SB), BX ; load в BX из памяти переменную B
То есть сначала быстро сложить за несколько единиц тактов, а потом 200-600 тактов ждать память(например из RAM). Такое явление называется out-of-order execution или внеочередное выполнение
Но формально правильно так: CPU может выполнить инструкцию раньше, если её операнды готовы
Зафиксируем:
Внеочередное исполнение (англ. out-of-order execution) машинных инструкций – исполнение машинных инструкций не в порядке следования в машинном коде, а в порядке готовности к выполнению
Вероятно, у вас возник вопрос: “А за счет чего это происходит?”
На самом деле, у CPU для обработки любой команды есть целый пайплайн. Давайте его рассмотрим
-
Fetch – считывание инструкций
-
Decode – парсинг инструкций ASM в свои внутренние
-
Register Rename – т.к. логических регистров мало, но физических относительно много(десятки-сотни), процессор делает отображение логических в физические(AX → R1 например), чтобы устранить ложные зависимости между инструкциями
-
Dispatch – после переименования инструкции попадают в очередь выполнения. Отсюда их выбирает планировщик(процессора) и смотрит, готовы ли операнды и свободен ли исполнительный блок. Если всё готово – инструкция отправляется на выполнение. Именно здесь появляется возможность out-of-order execution
-
Execute – инструкция выполняется в соответствующем блоке.
ALU – арифметика
FPU – float
Load unit – чтение памяти
Store unit – запись памяти
Vector – SIMD
-
Commit – несмотря на порядок выполнения, процессор должен сохранять логическую последовательность программы, т.к. CPU гарантирует логическую последовательность в рамках одного ядра. Для этого используется Reorder Buffer (ROB)
Но сохранение порядка commit не означает, что другие ядра увидят операции памяти в том же порядке!
Memory reordering
Вы, наверное, могли заметить, что load/store и другие операции с памятью стоят немного особняком. Для них есть специальные load unit, store unit и используют они буферы памяти, главным из которых является так называемый store buffer
Когда процессор выполняет запись например из строчки:
x = 1
Она не сразу попадает в cache или RAM, а кладётся в store buffer
Это нужно, чтобы пайплайн не блокировался медленной памятью!
Но появляется интересный эффект:
Что для одного ядра
x = 1y = 1
Для другого может быть как
y = 1x = 1
Соответственно
Переупорядочивание памяти (memory reordering) – это ситуация, при которой разные потоки наблюдают операции чтения и записи памяти в порядке, отличающемся от порядка инструкций в программе
А теперь почему это проблема:
Допустим у нас есть 2 горутины, которые исполняются физически на разных потоках:
G1: x = 1ready = trueG2:if ready { print(x)}
Вроде бы логично, что
если ready == true
значит x уже = 1
Но из-за вышеуказанного механизма может произойти такая ситуация:
store x=1 отправляется в store buffer
store ready=true отправляется в store buffer
Далее store buffer асинхронно сбрасывает их в cache line
И что мы по итогу можем иметь?
ready = true
x = 0
И вот мы получили проблему из-за того самого memory reordering – нарушился наблюдаемый порядок операций!
Ответив на вопрос “Кто виноват?”, мы получаем другой вопрос: “Что делать?”
P.S. Пример корректен скорее для ARM, для x86 – точно нет, ниже причина
Memory fences
Для того чтобы запретить опасные переупорядочивания операций памяти, процессоры предоставляют специальные инструкции – memory fences (memory barriers) или же барьеры памяти
Memory fence – это инструкция, которая запрещает определенные переупорядочивания операций памяти и гарантирует порядок их видимости между потоками
Барьер заставляет процессор:
-
Завершить все предыдущие операции памяти
-
Гарантировать их видимость до выполнения последующих операций
-
Запретить опасные переупорядочивания вокруг барьера
WARNING!
Барьер – это дорогая операция, потому что она ломает оптимизации CPU!
Выглядит это например так:
MOVQ $1, x(SB) ; Запись константы в памятьMFENCE ; БарьерMOVQ $1, ready(SB) ; Запись 1(true) в ready
Полный барьер для x86:
-
запрещает store-store reordering
-
запрещает load-load
-
запрещает load-store
-
запрещает store-load
Архитектура x86 имеет относительно строгую модель памяти, поэтому многие переупорядочивания уже запрещены аппаратно. Однако операция Store → Load может наблюдаться в другом порядке, поэтому для полной синхронизации используется инструкция MFENCE
То есть все операции памяти до барьера гарантированно видны операциям после барьера
Atomics
Наконец-то мы переходим к чему-то знакомому! Атомарные операции в Go достаточно часто применимы и время пришло их разобрать.
Большинство языков программирования не требуют использовать memory fences напрямую. Вместо этого они инкапсулируются внутри атомарных операций
На самом деле атомарные операции – уже более высокоуровневая абстракция, которая была придумана как более безопасная надстройка над барьерами!
Атомарная операция – это операция над памятью, которая выполняется как единое неделимое действие. Ни один другой поток не может наблюдать её промежуточное состояние
Это осуществляется с помощью инструкции LOCK на x86(на других архитектурах это может быть иначе)
LOCK ADDQ BX, AX
LOCK гарантирует, что операция будет атомарной для других ядер
А что конкретно он делает?
На старых процессорах он буквально блокировал системную шину(по которой MESI выполняет свои задачи)
Современные CPU делают иначе – блокируют строчку кэша
Происходит это так:
-
Блокируется cache line
-
Другие ядра не могут её изменить
-
Операция выполняется
-
Линия разблокируется
Это работает через MESI.
Ремарка
На x86 load/store атомарны как операция чтения/записи, но не создают memory ordering
Но если вы посмотрите например сюда, то возникнет закономерное замечание – LOCK есть, но не ADDQ, а XADDQ, да и вообще какие-то там CMPXCHGQ, XCMPQ. Что это вообще такое??
X в начале означает eXchange, то есть старое значение памяти возвращается в регистр
А зачем?
Проблема в том, что многие атомарные алгоритмы(В самом Go. Например sync.Map) требуют не просто изменить значение в памяти, а узнать, каким оно было до изменения. Без этого невозможно корректно реализовать счётчики, блокировки и большинство lock-free структур данных
Давайте попробуем что-нибудь уже разобрать!
TEXT ·Xadd64(SB), NOSPLIT, $0-24 ; функция Xadd64(ptr, delta) -> retMOVQptr+0(FP), BX ; BX = ptr, загружаем указатель на изменяемую переменнуюMOVQdelta+8(FP), AX ; AX = delta, загружаем величину прибавленияMOVQAX, CX ; CX = delta, сохраняем delta, т.к. XADDQ перезапишет AX старым значениемLOCK ; делаем следующую read-modify-write инструкцию атомарнойXADDQAX, 0(BX) ; atomically: tmp = *ptr; *ptr = *ptr + AX; AX = tmpADDQCX, AX ; AX = old + delta, получаем новое значениеMOVQAX, ret+16(FP) ; записываем возвращаемое значениеRET ; the end
То есть по сути мы меняем само значение возвращаем новое значение, собственно как и работает atomic.AddInt64
И вот теперь рассмотрим такую интересную концепцию – раз уж атомарные операции выполняются неделимо невозможна ситуация когда 2 ядра одновременно выполняют
-
load
-
add
-
store
А могут благодаря атомарным операциям либо «целиком» записать, либо «целиком» прочитать, то мы получаем простейшее решение проблемы состояния гонки
Finally, практика
Если у вас возникла крамольная мысль, что теперь вы фактически можете писать свои атомики, то эта мысль вообще не крамольная
Давайте попробуем написать… атомарный AND!
Для этого нам понадобятся:
-
main.go – гошный файл
-
Xmul64_x86.s – Go ASM файл
-
Команда go run .(чтобы ASM файл также подхватился)
“Из коробки” x86 предоставляет только такие атомарные инструкции
-
XADD – сложение с “обменом”
-
CMPXCHG – CAS
-
INC – инкремент
-
DEC – декремент
-
ADD – сложение
-
OR – ИЛИ
-
AND – И
-
XOR – Исключающее ИЛИ
-
BTC/BTR/BTS – инструкции для работы с битами
Отмечу, что нет операции XAND, поэтому функция не будет ничего возвращать. Будем смотреть сразу левый операнд
Xand8_x86.s
#include "textflag.h"TEXT ·And8(SB), NOSPLIT, $0-9 ; · перед And8 обязательна, остальное пока неважноMOVQptr+0(FP), BX // BX = ptr (64-битный указатель, из-за архитектуры)MOVBmask+8(FP), AX // AX = mask (8 бит)LOCKANDBAX, 0(BX) // атомарно: *ptr &= maskRET
main.go
package mainfunc And8(ptr *uint8, mask uint8)func main() {var smth uint8 = 3And8(&smth, uint8(2))println("Result:", smth)}
Прогоняем через go run . (можно через go build . → ./your_file)
Result: 2
То есть
0 0 0 0 0 0 1 1
AND
0 0 0 0 0 0 1 0
=
0 0 0 0 0 0 1 0
Тогда вопрос – а почему сами разрабы Go это не написали?
В отличие от x86, далеко не все архитектуры имеют прямые атомарные инструкции для побитовых операций, а Go у нас про платформенную независимость. Там, где не поддерживаются атомарные операции для например AND они будут реализовываться через CAS-loop:
-
load
-
compute
-
compare-and-swap
-
retry
// Можете попробовать реализовать так атомарное умножение
То есть универсальная реализация всё равно будет выглядеть как:
func AtomicAndUint64(addr *uint64, mask uint64) uint64 {for {old := atomic.LoadUint64(addr)new := old & maskif atomic.CompareAndSwapUint64(addr, old, new) {return new}}}
Поэтому в стандартной библиотеке часто выбирают более универсальный базовый примитив – CAS
А почему нельзя сделать платформенно зависимое?
Все просто – API должно быть переносимым
sync/atomic проектировался как кросс-платформенный слой над аппаратными атомиками.
Если добавить API, которое:
-
Работает одной инструкцией на x86
-
Но превращается в цикл на ARM
Это приведет к платформенной зависимости от производительности
Поэтому разработчики оставили минимальный набор операций, который одинаково реализуем на всех платформах.
Другой вопрос – а в чем была проблема реализовать например AddInt8?
В основном проблема та же – платформенная независимость. Не все архитектуры поддерживают атомарные операции над байтами
Однако помимо этого появляется проблема выравнивания.
Представим структуру из 4 байт
Процессор работает не с отдельными байтами, а с строкой кэша и машинным словом!
Если делать атомарную операцию над одним байтом, процессору может понадобиться:
-
Прочитать всё слово
-
Изменить нужный байт
-
Записать слово обратно
При этом другой поток может менять соседний байт того же слова. Что получаем? Правильно! false sharing = состязание за кэш, механизм которого был описан в предыдущей статье
Поэтому многие архитектуры допускают атомарность только для нативного размера слова(как правило 32/64 бит или же 4/8 байт)
А также с практической точки зрения это не особо нужно
Атомики и барьеры, а также переупорядочивание мы разобрали, соответственно в следующей статье мы чудеса оптимизаций на уровне CPU – NUMA, prefetch, TLB, alignment и согласуем это с производительностью на Go
P.S. Здесь я пока разбирал что с точки зрения CPU представляют из себя атомарные операции. Отдельный разбор пакета sync/atomic будет позже
ссылка на оригинал статьи https://habr.com/ru/articles/1025292/