news.shamcode.ru | Деконструкция GO: Низкоуровневые концепции. Atomics. Часть 2.1

Я самую малость обленился и как-то давно не делал новых разборов, поэтому следующим нашим этапом деконструкции будут низкоуровневые операции. Иногда здесь будет в отрыве от аллокаторов/планировщиков и прочего, но опять же, статьи для тех, кто знает и хочет разобраться поглубже, как тут всё устроено.

Поэтому, в этой части начнем с самого простого – пакета 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 делает:

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-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
}

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

Буду рад любой обратной связи и вашим лайкам!