Lock-free структуры данных в Go | Очередь Майкла и Скотта | Concurrency в Go

Консультации:

Таймкоды:
00:00 - Введение
00:16 - Реализация очереди на связном списке
01:38 - Реализация lock-free очереди
04:10 - Реализация метода push
07:51 - Реализация метода pop
10:24 - Курс по Concurrency в Go

Golang. Lock free структуры данных. Concurrency Go. Concurrency Golang. Примитивы синхронизации. Golang уроки. Golang с нуля. Lock free алгоритмы. Параллельное программирование. Конкурентное программирование.

#айти #программирование #программист #golang #concurrency

[ДмитрийВ-чк]

Да. В программе допущена ошибка в 47 строке.
Должно быть:
47 atomic.CompareAndSwapPointer(&q.tail, tail, next)

Также предлагаю рефакторинг:
В методе Push три раза (строки 40, 42, 47) встречается unsafe.Pointer(node)
Лучше в строке 29 сразу один раз написать: node := unsafe.Pointer(&item{value: value})
Тогда в других строках вместо unsafe.Pointer(node) можно будет использовать просто node.
Для ясности кода я бы переменную node переименовал в newNode.

[RDmrcv]

7:32 На строке 47 в Push, случайно не должно быть next вместо unsafe.Pointer(node)?
Мы же пытаемся исправить хвост, а не пушнуть туда свой элемент. Или я неправильно понял?

[evgeniigordienko]

Радует, что видео выходят регулярно, спасибо!

[mkhalv]

Push можно сократить до одного ifика, так и читается легче.

func (queue *Queue[T]) Push(value T) {
element := &element[T]{value: value}

for {
tail := queue.tail.Load()

if tail.next.CompareAndSwap(nil, element) {
queue.tail.CompareAndSwap(tail, element)
return
} else {
queue.tail.CompareAndSwap(tail, tail.next.Load())
}
}
}

[mosceo]

У меня два подозрения:
1) В новую очередь добавить элементов. Первый Pop() вернет 0, потому что очередь инициализируется с нулевым элементом, который не удаляется.
2) Во время жизни очереди в ней иногда будет оставаться один элемент. Тогда head == tail и вернет -1, хотя лежит нормальное значение.

[barsik_the_cat]

Классный материал, Владимир, а можете порекомендовать какую-нибудь хорошую книгу по lock-free структурам данных? А то что то гуглятся одни статьи на Хабре.

[mirasalimov]

Привет! А на 47 строке не должно быть CAS(&q.tail, tail, next)? Кажется что unsafe.Pointer(node) уже может быть другой нодой, или просто я туплю 😅

[Vadyas]

В статье Скотта упоминается double CAS, которого в Go нет, для избежания проблемы ABA. Как вы обошли эту проблему? :)

[klimovevgeny]

Получается, придумали простой язык, чтобы на нем все заново изобретали велосипед? Очень напоминает ситуацию с ЯП C, на структурах которого изобретали ООП в стиле C++, реализовывали наследование, виртуальные методы и тд. Может, каждый язык для своих нужд? Молотком тоже можно кашу есть, но неудобно

[Max-sx]

Оооооооооооочень мелко на телефоне смотреть не возможно🤷🏻‍♂️ но за контент спасибо!

[ypohut]

Пока го не узучаю просто коммент в поддержку