Loser story

Loser story

Можно ли сделать лучше? В теории да, slow-path в reader/writer lock – wait-free, а в writer unlock – lock-free, вместо маленькой критической секции защищенной mutex/spinlock, нужны соответствующие очереди и логика. Будет ли это действительно быстрее? Вряд…

Что ещё можно сделать, если у вас есть алгоритм, который требует SharedMutex, но скорость стандартного подхода вас не устраивает.

В первую очередь можно посмотреть на SharedMutex, который сделан с приоритетом на перформанс читателей.
Идея везде примерно одинаковая, давайте пошардируем читателей и как следствие избавимся от контеншена, примеры:
1) https://arxiv.org/pdf/1810.01553.pdf красивая идея, как любой лок сделать reader biased
2) https://github.com/facebook/folly/blob/main/folly/SharedMutex.h#L43 довольно сложная имплементации SharedMutex, которая пытается избегать контеншена с помощью thread local слотов
https://blog.the-pans.com/shared-mutex

Если SharedMutex нужен для чего-то похожего на структуру данных, есть два варианта:

Очевидный с RCU, плюсы, читателям в kernel-space не нужна синхронизация, в user-space нужна довольно тривиальная (в виде счётчика, может быть шардированным).
Минусы, сложность реализации, может быть много версий структуры данных.

И менее известный вариант, left-right, тут есть необходимые ссылки: https://concurrencyfreaks.blogspot.com/2013/12/left-right-classical-algorithm.html
В целом же идея очень простая, давайте поддерживать две копии структуры данных.
Наличие/отсутствие контеншена зависит от имплементации read indicator -- счётчика читателей для соответствующей версии структуры данных (может быть шардированный), по сути аналогично RCU.
Основное преимущество перед scalable SharedMutex то, что наличие писателей никак не влияет на читателей.
Ну и простейшая реализация, в отличие от RCU.
Главный минус в сравнении с RCU, что две копии нужны всегда, и что писатель должен делать работу "дважды".

👍9

www.tgoop.com/reverse13/724

1.83K viewsedited  Feb 4, 2024 at 10:58

Что ещё можно сделать, если у вас есть алгоритм, который требует SharedMutex, но скорость стандартного подхода вас не устраивает.

В первую очередь можно посмотреть на SharedMutex, который сделан с приоритетом на перформанс читателей.
Идея везде примерно одинаковая, давайте пошардируем читателей и как следствие избавимся от контеншена, примеры:
1) https://arxiv.org/pdf/1810.01553.pdf красивая идея, как любой лок сделать reader biased
2) https://github.com/facebook/folly/blob/main/folly/SharedMutex.h#L43 довольно сложная имплементации SharedMutex, которая пытается избегать контеншена с помощью thread local слотов
https://blog.the-pans.com/shared-mutex

Если SharedMutex нужен для чего-то похожего на структуру данных, есть два варианта:

Очевидный с RCU, плюсы, читателям в kernel-space не нужна синхронизация, в user-space нужна довольно тривиальная (в виде счётчика, может быть шардированным).
Минусы, сложность реализации, может быть много версий структуры данных.

И менее известный вариант, left-right, тут есть необходимые ссылки: https://concurrencyfreaks.blogspot.com/2013/12/left-right-classical-algorithm.html
В целом же идея очень простая, давайте поддерживать две копии структуры данных.
Наличие/отсутствие контеншена зависит от имплементации read indicator -- счётчика читателей для соответствующей версии структуры данных (может быть шардированный), по сути аналогично RCU.
Основное преимущество перед scalable SharedMutex то, что наличие писателей никак не влияет на читателей.
Ну и простейшая реализация, в отличие от RCU.
Главный минус в сравнении с RCU, что две копии нужны всегда, и что писатель должен делать работу "дважды".

BY Loser story