Я самую малость обленился и как‑то давно не делал новых разборов, поэтому следующим нашим этапом деконструкции будут низкоуровневые операции. Иногда здесь будет в отрыве от аллокаторов/планировщиков и прочего, но опять же, статьи для тех, кто знает и хочет разобраться поглубже, как тут всё устроено.
Поэтому, в этой части начнем с самого простого — пакета atomic.
Концепции вокруг атомарных операций на уровне CPU я рассматривал здесь, поэтому советую почитать. Там мы даже пишем свой атомарный AND.
Важно! Мы будем разбирать на примере src/internal/runtime/atomics, то есть внутреннего пакета, а не того, который представлен нам как пользователям(потому что в исходниках я не нашел реализации). Но по большей части операции одни и те же.
Что из себя представляет пакет
На самом деле, каким бы маленьким этот пакет вам не казался, реализаций у него достаточно много! Давайте заглянем в официальный репозиторий.
Данный пакет реализован под большое количество архитектур, следовательно даже реализации самых простых низкоуровневых операций могут разниться. Например:
//arm64
TEXT ·Load(SB),NOSPLIT,$0-12
MOVD ptr+0(FP), R0
LDARW (R0), R0
MOVW R0, ret+8(FP)
RET
// 386
//go:nosplit
//go:noinline
func Load(ptr *uint32) uint32 {
return *ptr
}
Почему вообще так сделано?
Конкретно, в этом примере по очень простой причине — операции на 386/x86 достаточно строгие и не переупорядочивают load с другими load, store с другими store, и store с более старыми load, а так как на 386 размер машинослова 32 бит, а также load там сам по себе атомарен, то достаточно обычного разыменования. На arm такого нет, поэтому необходимо явно использовать LDARW(load‑acquire w).
О функции для 386 компилятор знает, как об атомарном чтении, но вот вопрос — а зачем нам go:nosplit и go:noinline? Эти комменты означают, что функция не вызывает проверку/расширение стека перед вызовом, а noinline запрещает встраивать это как обычное выражение.
Load, Store, Swap
Самое примитивное, что мы можем в принципе сделать — хранить, загружать и менять местами значения переменных. Пример с Load был выше, поэтому вот Store:
TEXT ·Store64(SB), NOSPLIT, $0-16
MOVQ ptr+0(FP), BX
MOVQ val+8(FP), AX
XCHGQ AX, 0(BX)
RET
И вот Swap:
// uint64 Xchg64(ptr *uint64, new uint64)
// Atomically:
// old := *ptr;
// *ptr = new;
// return old;
TEXT ·Xchg64(SB), NOSPLIT, $0-24
MOVQ ptr+0(FP), BX
MOVQ new+8(FP), AX
XCHGQ AX, 0(BX)
MOVQ AX, ret+16(FP)
RET
Что интересно, используют они одну и ту же операцию — XCHGQ, что наводит на крамольную мысль о том, что по большей части разница семантическая. Отчасти да, но всё‑таки иногда нужно получить замененное значение, что говорит нам о том, что фактически Swap можно использовать ровно так же как Store:)
CompareAndSwap и CAS‑loop
Если подходить по‑честному, то ключевая концепция очень многих lock‑free алгоритмов — CompareAndSwap(CAS)
Вот в этом файле например приведено следующее:
// func Cas64(ptr *uint64, old, new uint64) bool
// Atomically:
// if *ptr == old {
// *ptr = new
// return true
// } else {
// return false
// }
TEXT ·Cas64(SB), NOSPLIT, $0-25
MOVQ ptr+0(FP), BX
MOVQ old+8(FP), AX
MOVQ new+16(FP), CX
LOCK
CMPXCHGQ CX, 0(BX) // это вообще ключевое, что нам здесь надо
SETEQ ret+24(FP)
RET
Думаю, из кода понятно, что мы при равенстве значения по указателю и того, что лежит меняем и возвращаем true, а иначе false
Но как это вяжется с lock‑free алгоритмами? Здесь у нас ключевой паттерн этих самых алгоритмов, про который я ранее уже говорил в статье про атомики на CPU, но вспомним ещё раз:
Цикл
Load
Операция
CAS → break if success else continue
П. 2–4 также называют RMW(read‑modify‑write)
Это так называемый CAS‑loop. Дорого ли это? Ответ — да, достаточно, чтобы на куче воркеров быть медленнее например Mutex. Поэтому, настоятельно советую пользоваться атомарными операциями аккуратно(подробнее это разберем позже)!
Но если это сырые операции на CPU, то почему вдруг они медленнее? Очень просто — из‑за состязания за кэш, а также перезаходов в цикл. Каждая такая CAS‑операция заставляет
Получить эксклюзивное владение строкой CPU‑кэша
Инвалидировать/синхронизировать копии этой строки в других ядрах
Перезайти в цикл в случае неудачи
Давайте рассмотрим классическую задачу с собесов:
// go 1.26
func main() {
var max int
for i := 1000; i > 0; i-- {
go func () {
if i > max {
max = i
}
}()
}
fmt.Println(max)
}
И вот её решение через CAS:
func main() {
var (
max uint64
wg sync.WaitGroup
)
wg.Add(1000)
for i := 1000; i > 0; i-- {
go func() {
defer wg.Done()
for { // цикл
l := atomic.LoadUint64(&max) // load
if uint64(i) <= l { // операция
return
}
if atomic.CompareAndSwapUint64(&max, l, uint64(i)) { // CAS
return // break
}
// continue
}
}()
}
wg.Wait()
fmt.Println(max)
}
Чисто теоретически, оно должно быть достаточно быстро, но давайте разберем более конкретно
Итерация 1: 1 горутина отработала, 999 перезаходят в цикл
Итерация 2: 2 горутины отработали, 998 перезаходят в цикл
Итерация N: N горутин отработали, 1000-N перезаходят в цикл
То есть сложность выходит O(N^2) в худшем случае!
А если мы берем ещё в расчет, что происходит состязание за кэш, то получается мрак. Но зачем нам этот цикл? Чтобы в случае неудачного CAS не потерять потенциально бОльшее значение, а попробовать поменять его снова.
Add
Одна из самых известных операций, которую нам дает пакет atomic — Add. Собственно, добавление есть добавление, но есть нюанс
XADDQ — это не CAS‑loop, а отдельная аппаратная RMW инструкция.
CAS‑loop делает:
Load
Операция
CompareAndSwap
Повтор при неудаче
А LOCK XADD делает атомарное сложение одной инструкцией. У неё нет «неудачной попытки»: если CPU начал выполнять LOCK XADD над памятью, операция завершится и изменит значение. Но по наблюдаемому результату для простого Add она эквивалентна успешному CAS‑loop: значение будет увеличено атомарно, а функция вернёт новое значение.
// uint64 Xadd64(uint64 volatile *val, int64 delta)
// Atomically:
// *val += delta;
// return *val;
TEXT ·Xadd64(SB), NOSPLIT, $0-24
MOVQ ptr+0(FP), BX
MOVQ delta+8(FP), AX
MOVQ AX, CX
LOCK
XADDQ AX, 0(BX) // вот здесь
ADDQ CX, AX
MOVQ AX, ret+16(FP)
RET
По видимому результату это будет эквивалентно:
func MyAtomicAdd(addr *uint64, inc uint64) uint64 {
for {
v := atomic.LoadUint64(addr)
if atomic.CompareAndSwapUint64(addr, v, v + inc) {
return v + inc
}
}
}
Кстати, может понадобиться на собесах!
Учтите, второй вариант будет медленнее из‑за retry‑операций. XADD добавляет безусловно!
AND, OR
Что интересно, ранее, когда я приводил пример с реализацией своего атомика, я очень эффектно провтыкал, что в Go уже добавили атомарные AND и OR. Но, к счастью, я их нашел и мы на них будем разбирать как раз CAS‑алгоритмы! Интересный факт — хотя на некоторых архитектурах реализованы атомарные AND(без Exchange), разработчики Go всё‑таки реализовали их через CAS‑loop, чтобы минимизировать зависимость производительности от платформы!
// func Or64(addr *uint64, v uint64) old uint64
TEXT ·Or64(SB), NOSPLIT, $0-24
MOVQ ptr+0(FP), BX
MOVQ val+8(FP), CX
casloop: // цикл
MOVQ CX, DX
MOVQ (BX), AX // load
ORQ AX, DX // операция
LOCK
CMPXCHGQ DX, (BX) // CAS
JNZ casloop // continue
MOVQ AX, ret+16(FP) // break
RET
// func And64(addr *uint64, v uint64) old uint64
TEXT ·And64(SB), NOSPLIT, $0-24
MOVQ ptr+0(FP), BX
MOVQ val+8(FP), CX
casloop: // цикл
MOVQ CX, DX
MOVQ (BX), AX // load
ANDQ AX, DX // операция
LOCK
CMPXCHGQ DX, (BX) // CAS
JNZ casloop // continue
MOVQ AX, ret+16(FP) // break
RET
Ну или можно через Go:
func MyAtomicAnd(addr *uint64, mask uint64) uint64 {
for {
l := atomic.LoadUint64(addr)
if atomic.CompareAndSwapUint64(addr, l, l & mask) {
return l
}
}
}
func MyAtomicOr(addr *uint64, mask uint64) uint64 {
for {
l := atomic.LoadUint64(addr)
if atomic.CompareAndSwapUint64(addr, l, l | mask) {
return l
}
}
}
А где он вообще используется?
Если коротко — везде, где runtime нужно синхронизировать состояние между разными M, P, G, GC‑воркерами, сисмоном, профилировщиком и аллокатором без обычного пользовательского mutex.
Но здесь есть важный нюанс: runtime обычно использует не публичный пакет sync/atomic, а внутренний internal/runtime/atomic, который мы сегодня разбирали(потому что в sync/atomic не представлен assembler). Это мы будем разбирать потом так как это огромный раздел!
Если говорить о том, что ближе к земле, то естественно это пакет sync. Например в коде WaitGroup вы вполне можете увидеть атомарный счетчик waiters и count.
type WaitGroup struct {
noCopy noCopy
// Bits (high to low):
// bits[0:32] counter
// bits[32] flag: synctest bubble membership
// bits[33:64] wait count
state atomic.Uint64 // ← тут
sema uint32
}
Самое простое из низкоуровневого мы делать научились, далее будем разбирать работу с памятью, переключениями контекста и прочим, что мы не видим явно!
Буду рад любой обратной связи и вашим лайкам!