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

В этот раз снова будет Go Assembler, а также снова будут примеры на Go. В прошлый раз это было необходимое зло во имя соответствия реальности!!!

Напоминаю, что эта статья – часть большого цикла разбора языка программирования Golang End 2 End. Но если вы уверены, что понимаете природу многозадачности, многопоточности, проблемы оных, а также то, как выполняются инструкции и пришли разбираться в самых примитивных механизмах синхронизации, то велком.

Instructions reordering

Обычно мы считаем, что CPU добросовестно выполняет свои инструкции последовательно. Ровно так, как мы ему сказали. Но это не всегда верно!

Допустим есть код

x = 1
ready = true

Сначала в память попадёт x = 1

Потом в память попадёт ready = true

Но в реальности, процессор может переставить местами эти инструкции т.к. они независимы друг от друга и не меняют результат потока исполнения.

Причина простая: CPU пытается выполнять код быстрее.
Ему выгодно:

Менять порядок независимых операций,
Держать значения в регистрах,
Откладывать запись в память,
Заранее читать данные,
Исполнять инструкции спекулятивно.

Для однопоточного кода это обычно незаметно, но для многопоточного – уже нет!

Зафиксируем:

Переупорядочивание инструкций (instruction reordering) – это оптимизация, выполняемая процессором или компилятором, при которой порядок выполнения команд меняется для повышения производительности (ускорения кода), сохраняя при этом логическую последовательность.

Пока будем рассматривать в контексте процессора.

Пример был чисто демонстрационный, давайте посмотрим более реальный пример с проблемой которая тут решается

Если две инструкции независимы, их можно выполнить параллельно или поменять местами.

MOVQ A(SB), AX ; load в AX из памяти переменную A
MOVQ B(SB), BX ; load в BX из памяти переменную B
ADDQ DX, CX    ; Сложение двух других переменных

Внимательно рассмотрев код, можно утверждать следующее:

Первая инструкция ждет значение из памяти.

Вторая тоже ждет значение из памяти.

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

С точки зрения здравого смысла при условии, что надо выполнить быстрее, выгоднее начать с последней инструкции и в порядке например:

ADDQ DX, CX    ; Сложение двух других переменных
MOVQ A(SB), AX ; load в AX из памяти переменную A
MOVQ 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 = 1
y = 1

Для другого может быть как

y = 1
x = 1

Соответственно

Переупорядочивание памяти (memory reordering) – это ситуация, при которой разные потоки наблюдают операции чтения и записи памяти в порядке, отличающемся от порядка инструкций в программе.

А теперь почему это проблема:

Допустим у нас есть 2 горутины, которые исполняются физически на разных потоках:

G1: 
x = 1
ready = true

G2:
if ready {
  print(x)
}

Вроде бы логично, что

ЕСЛИ ready == true

ТО x уже = 1

Но из-за вышеуказанного механизма может произойти такая ситуация:

1) store x=1 отправляется в store buffer.

2) store ready=true отправляется в store buffer.

3) Далее 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) -> ret
	MOVQ	ptr+0(FP), BX ; BX = ptr, загружаем указатель на изменяемую переменную
	MOVQ	delta+8(FP), AX ; AX = delta, загружаем величину прибавления
	MOVQ	AX, CX ; CX = delta, сохраняем delta, т.к. XADDQ перезапишет AX старым значением
	LOCK ; делаем следующую read-modify-write инструкцию атомарной
	XADDQ	AX, 0(BX) ; atomically: tmp = *ptr; *ptr = *ptr + AX; AX = tmp
	ADDQ	CX, AX ; AX = old + delta, получаем новое значение
	MOVQ	AX, 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 обязательна, остальное пока неважно
	MOVQ	ptr+0(FP), BX      // BX = ptr (64-битный указатель, из-за архитектуры)
	MOVB	mask+8(FP), AX     // AX = mask (8 бит)

	LOCK
	ANDB	AX, 0(BX)          // атомарно: *ptr &= mask
	RET

main.go

package main

func And8(ptr *uint8, mask uint8)

func main() {

	var smth uint8 = 3

	And8(&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 & mask

		if 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 будет позже.

Деконструкция GO: CPU, RAM и что там происходит. Reordering, atomics, locks, fences. Часть 1.3