Я самую малость обленился и как-то давно не делал новых разборов, поэтому следующим нашим этапом деконструкции будут низкоуровневые операции. Иногда здесь будет в отрыве от аллокаторов/планировщиков и прочего, но опять же, статьи для тех, кто знает и хочет разобраться поглубже, как тут всё устроено.
Поэтому, в этой части начнем с самого простого – пакета atomic.
Концепции вокруг атомарных операций на уровне CPU я рассматривал здесь, поэтому советую почитать. Там мы даже пишем свой атомарный AND.
!Важно! Мы будем разбирать на примере src/internal/runtime/atomics, то есть внутреннего пакета, а не того, который представлен нам как пользователям(потому что в исходниках я не нашел реализации). Но по большей части операции одни и те же.
Что из себя представляет пакет
На самом деле, каким бы маленьким этот пакет вам не казался, реализаций у него достаточно много! Давайте заглянем в официальный репозиторий.
Данный пакет реализован под большое количество архитектур, следовательно даже реализации самых простых низкоуровневых операций могут разниться. Например:
//arm64TEXT ·Load(SB),NOSPLIT,$0-12MOVDptr+0(FP), R0LDARW(R0), R0MOVWR0, ret+8(FP)RET
// 386//go:nosplit//go:noinlinefunc 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-16MOVQptr+0(FP), BXMOVQval+8(FP), AXXCHGQAX, 0(BX)RET
И вот Swap:
// uint64 Xchg64(ptr *uint64, new uint64)// Atomically://old := *ptr;//*ptr = new;//return old;TEXT ·Xchg64(SB), NOSPLIT, $0-24MOVQptr+0(FP), BXMOVQnew+8(FP), AXXCHGQAX, 0(BX)MOVQAX, 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-25MOVQptr+0(FP), BXMOVQold+8(FP), AXMOVQnew+16(FP), CXLOCKCMPXCHGQCX, 0(BX) // это вообще ключевое, что нам здесь надоSETEQret+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.26func main() {var max intfor i := 1000; i > 0; i-- {go func () {if i > max {max = i}}()} fmt.Println(max)}
И вот её решение через CAS:
func main() {var (max uint64wg sync.WaitGroup)wg.Add(1000)for i := 1000; i > 0; i-- {go func() {defer wg.Done()for { // циклl := atomic.LoadUint64(&max) // loadif uint64(i) <= l { // операцияreturn}if atomic.CompareAndSwapUint64(&max, l, uint64(i)) { // CASreturn // 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 делает:
1. Load
2. Операция
3. CompareAndSwap
4. Повтор при неудаче
А 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-24MOVQptr+0(FP), BXMOVQdelta+8(FP), AXMOVQAX, CXLOCKXADDQAX, 0(BX) // вот здесьADDQCX, AXMOVQAX, 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 uint64TEXT ·Or64(SB), NOSPLIT, $0-24MOVQptr+0(FP), BXMOVQval+8(FP), CXcasloop: // циклMOVQ CX, DXMOVQ(BX), AX // loadORQAX, DX // операцияLOCKCMPXCHGQDX, (BX) // CASJNZ casloop // continueMOVQ AX, ret+16(FP) // breakRET// func And64(addr *uint64, v uint64) old uint64TEXT ·And64(SB), NOSPLIT, $0-24MOVQptr+0(FP), BXMOVQval+8(FP), CXcasloop: // циклMOVQ CX, DXMOVQ(BX), AX // loadANDQAX, DX // операцияLOCKCMPXCHGQDX, (BX) // CASJNZ casloop // continueMOVQ AX, ret+16(FP) // breakRET
Ну или можно через 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 countstate atomic.Uint64 // ← тутsema uint32}
Самое простое из низкоуровневого мы делать научились, далее будем разбирать работу с памятью, переключениями контекста и прочим, что мы не видим явно!
Буду рад любой обратной связи и вашим лайкам!
ссылка на оригинал статьи https://habr.com/ru/articles/1033780/