Комментарии 22
Поражает воображение, насколько всё это сложно по сравнению с песочницей интерпретируемых языков. Слава суровым дядькам-бородачам!
Пара вопросов:
1. ваш лок содержит обычную TAS блокировку, которую хватают неудачливые читатели и писатели, но я не вижу причин, почему эта блокировка не вынесена в отдельную компоненту, я что-то пропустил или просто так?
2.1. есть ли у вас результаты тестирования в случае, если количество потоков больше чем константа-параметр класса блокировки? У меня в данный момент в наличии нет машины, чтобы самому померить, но интересует на сколько сильно неудачливые читатели будут мешать писателям и друг другу (тем более, что там просто активное ожидание)?
2.2. нет ли смысла, например, заменить TAS на какой-нибудь ticket rwlock, чтобы и неудачливым читателям дать какую-то свободу, или вообще для них просто откатиться к стандартному shared_mutex?
1. ваш лок содержит обычную TAS блокировку, которую хватают неудачливые читатели и писатели, но я не вижу причин, почему эта блокировка не вынесена в отдельную компоненту, я что-то пропустил или просто так?
2.1. есть ли у вас результаты тестирования в случае, если количество потоков больше чем константа-параметр класса блокировки? У меня в данный момент в наличии нет машины, чтобы самому померить, но интересует на сколько сильно неудачливые читатели будут мешать писателям и друг другу (тем более, что там просто активное ожидание)?
2.2. нет ли смысла, например, заменить TAS на какой-нибудь ticket rwlock, чтобы и неудачливым читателям дать какую-то свободу, или вообще для них просто откатиться к стандартному shared_mutex?
1. Только не TAS, а именно CAS (std::atomic want_x_lock;), если вы про contention_free_shared_mutex<>. Здесь CAS не вынесен в отдельную компоненту, чтобы сразу было видно какой барьер в нем используется, без необходимости заглядывать во внутренности отдельной компоненты. Т.е. многое сделано для легкого чтения и понимания статьи.
2. В лучшем случае cont-free shared-mutex будет работать как cont-free, а в худшем как spinlock.
Spinlock далеко не всегда хуже, чем std::mutex, особенно если важно, чтобы не было слишком больших задержек.
Начиная с 15%-write блокировка std::shared_mutex уже уступает блокировке std::mutex. Поэтому к чему стоит откатываться и стоит ли вообще откатываться — ещё большой вопрос.
К тому же, читателям требуется операция проверки — установлена ли эксклюзивная блокировка без её захвата (чтобы не гонять x-state кэш-линии) — такой интерфейс не предоставляют ни std::mutex, ни std::shared_mutex, сюда не подходят ни lock(), ни try_lock().
2. В лучшем случае cont-free shared-mutex будет работать как cont-free, а в худшем как spinlock.
Spinlock далеко не всегда хуже, чем std::mutex, особенно если важно, чтобы не было слишком больших задержек.
Начиная с 15%-write блокировка std::shared_mutex уже уступает блокировке std::mutex. Поэтому к чему стоит откатываться и стоит ли вообще откатываться — ещё большой вопрос.
К тому же, читателям требуется операция проверки — установлена ли эксклюзивная блокировка без её захвата (чтобы не гонять x-state кэш-линии) — такой интерфейс не предоставляют ни std::mutex, ни std::shared_mutex, сюда не подходят ни lock(), ни try_lock().
Spinlock далеко не всегда хуже, чем std::mutex, особенно если важно, чтобы не было слишком больших задержек.Ну я не говорил, что он хуже, но то что он не всегда хуже не значит, что он всегда лучше. Да и более или менее разуменые реализации mutex-ов обычно таки оптимистично ожидают активно некоторое время, т. е. в случае отсутсвия конкуренции, они не должны быть супер плохи.
К тому же, читателям требуется операция проверки — установлена ли эксклюзивная блокировка без её захвата (чтобы не гонять x-state кэш-линии) — такой интерфейс не предоставляют ни std::mutex, ни std::shared_mutex, сюда не подходят ни lock(), ни try_lock().Ну это только часть правды, они действительно такой интерфейс не предоставляют, но без него можно обойтись, как-нибудь так:
void lock_shared() {
int const register_index = register_thread();
if (register_index >= 0) {
int recursion_depth = shared_locks_array[register_index].value.load(std::memory_order_acquire);
assert(recursion_depth >= 1);
if (recursion_depth > 1) {
shared_locks_array[register_index].value.store(recursion_depth + 1, std::memory_order_release);
else {
shared_locks_array[register_index].value.store(recursion_depth + 1);
while (writers.load()) {
shared_locks_array[register_index].value.store(recursion_depth);
for (size_t i = 0; writers.load(); ++i)
if (i % 100000 == 0) std::this_thread::yield();
shared_locks_array[register_index].value.store(recursion_depth + 1);
}
}
}
else {
if (owner_thread_id.load(std::memory_order_acquire) != get_fast_this_thread_id())
mtx.lock_shared();
++recursive_xlock_count;
}
}
void lock() {
int const register_index = get_or_set_index();
if (register_index >= 0)
assert(shared_locks_array[register_index].value.load(std::memory_order_acquire) == 1);
if (owner_thread_id.load(std::memory_order_acquire) != get_fast_this_thread_id()) {
++writers;
mtx.lock();
owner_thread_id.store(get_fast_this_thread_id(), std::memory_order_release);
for (auto &i : shared_locks_array)
while (i.value.load() > 1);
}
++recursive_xlock_count;
}
Таким образом, если я ничего не напутал, даже неудачливые читатели не будут хватать блокировку в эксклюзивном виде.
Заменить CAS на RMW + mtx.lock() — пробовал.
И std::shared_mutex и std::mutex заметно снижали производительность, особенно на большом количестве ядер.
И std::shared_mutex и std::mutex заметно снижали производительность, особенно на большом количестве ядер.
Ну shared_mutex там только для примера, вместо него можно поставить все что угодно и интерфейс не будет особо важен в этом и суть вопроса. В том числе и обычную TAS/CAS/XCHG блокировку с произвольной стратегией ожидания, или Ticket Lock или MCS, которые должны неплохо справляться с неожиданныыми припадками, когда все вдруг ломятся хватать блокировку.
Статья монументальная и исчерпывающая. Во всяком случае многие вещи которые у вас описаны я нигде не встречал, удивительно. Единственное, признаюсь честно, я не гуру в многопоточности, но если бы я не занимался ею повседневно, на практике, я бы ничего не понял. Уж не знаю почему, но материал очень тяжелый. Может быть нужно будет еще раз внимательно все перечитать. А может быть и не раз. Все равно, спасибо вам большое за труд. И если, вдруг, будет время и желание, не могли бы вы разбить ее на несколько частей поменьше и поподробней, более детально, разложить все по полочкам. С x86-x64 я еще дружу, но с остальными memory orders, у меня теперь каша полная.
Спасибо! Да, возможно в будущем напишу отдельно о барьерах памяти, с упрощенными правилами — как проверить работоспособность каких-то lock-free алгоритмов. И отдельно как барьеры ложатся на разные архитектуры — где может менять порядок компилятор, а где процессор. А может что-то другое.
Посмотрим, что будет интересно мне и читателям.
Посмотрим, что будет интересно мне и читателям.
Спасибо большое, будем с нетерпением ждать.
Кстати, хотелось бы спросить, чем вы на практике таким занимаетесь, что скорость примитива синхронизации становится настолько критичной, что даже атомарная смена указателя перестает устраивать? Я, на в своей практике, практически любую задачу мог, в итоге, свести к смене указателя. Для примера, я реализовывал подобие базы данных, но только на очень низком уровне. Размер данных для транзакции может занимать несколько десятков гигабайт, но даже в такой задаче коммит, по сути, сводится к замене одного указателя (на практике это конечно сектор диска). Ну если данные уж совсем быстро меняются, то можно использовать очередь (т… е. память) и передавать данных другому потоку большими группами, «размазывая» таким образом издержки на синхронизацию.
Из всего этого, я делаю вывод, что это какие-то задачи, где нет лишней памяти, а данные приходят из вне и вы не можете объединить их обработку, т.е не можете влиять на контекст. Похоже на ядро, я прав? Меня интересуют именно такие скоростные блокировки, т.к. с lockfree все понятно.
Кстати, хотелось бы спросить, чем вы на практике таким занимаетесь, что скорость примитива синхронизации становится настолько критичной, что даже атомарная смена указателя перестает устраивать? Я, на в своей практике, практически любую задачу мог, в итоге, свести к смене указателя. Для примера, я реализовывал подобие базы данных, но только на очень низком уровне. Размер данных для транзакции может занимать несколько десятков гигабайт, но даже в такой задаче коммит, по сути, сводится к замене одного указателя (на практике это конечно сектор диска). Ну если данные уж совсем быстро меняются, то можно использовать очередь (т… е. память) и передавать данных другому потоку большими группами, «размазывая» таким образом издержки на синхронизацию.
Из всего этого, я делаю вывод, что это какие-то задачи, где нет лишней памяти, а данные приходят из вне и вы не можете объединить их обработку, т.е не можете влиять на контекст. Похоже на ядро, я прав? Меня интересуют именно такие скоростные блокировки, т.к. с lockfree все понятно.
Это нужно для алгоритмов сложнее упорядоченного map, когда разработка lock-free слишком долгая и затраты на rollback слишком высокие. Когда заранее неизвестно какие данные какому потоку передавать.
Атомарная смена указателя — относительно быстрая операция. То, что вы описали — это оптимистическая блокировка, она может быть медленной. Основная проблема ABA, и дополнительная — накладные расходы на rollback при conflicting modifications.
Чем не устраивает оптимистическая блокировка?
Если надо многопоточно использовать очень сложный алгоритм, то:
1. Защитить его оптимистической блокировкой, предполагает сильное изменение самого алгоритма — это обычно означает реализовать его obstruction/lock-free версию, что может занять месяцы
2. сложность алгоритма может предполагать большой объем работы во время rollback при conflicting modifications — в этом случае это будет работать намного медленней, чем пессимистическая блокировка.
Т.е. сложность использования оптимистической блокировки пропорциональна сложности защищаемого алгоритма.
А пессимистическую блокировку всегда одинаково легко использовать.
Изменить lock-free алгоритм сложнее, чем однопоточный алгоритм защищаемый пессимистической блокировкой.
— Если есть готовый быстрый lock-free алгоритм, то лучше использовать его.
— Если нет, то берёте быстрый однопоточный алгоритм, и защищаете его пессимистической блокировкой, они универсальны — поэтому есть в стандарте. Tom Kyte их фанат.
Блокировку из статьи можно использовать и в обычных приложениях, и для прототипов высокопроизводительных приложений, из-за её легкого использования.
— Это нужно там, где требуются одновременно много чтений, low latency и есть сложные структуры данных: OLTP (in-memory-DB/noSQL), HFT (High Frequency Trading), для сложных систем с обратной связью критичных к задержке…
— Так же это нужно и там, где требуется high performance, но по какой-то причине нельзя использовать GPU/FPGA, тогда блокировку сложного алгоритма можно совмещать с batching (обработка запросов группой).
В более общем случае, write contention-free очереди я используя для low latency кросс-аппаратного обмена в кластерах с множеством CPU, GPU,… Отдать 16 KB на GPU, обработать и вернуть на CPU занимает 5.5 usec. Занимаюсь реализацией различных задач на HPC кластерах.
Атомарная смена указателя — относительно быстрая операция. То, что вы описали — это оптимистическая блокировка, она может быть медленной. Основная проблема ABA, и дополнительная — накладные расходы на rollback при conflicting modifications.
Чем не устраивает оптимистическая блокировка?
Если надо многопоточно использовать очень сложный алгоритм, то:
1. Защитить его оптимистической блокировкой, предполагает сильное изменение самого алгоритма — это обычно означает реализовать его obstruction/lock-free версию, что может занять месяцы
2. сложность алгоритма может предполагать большой объем работы во время rollback при conflicting modifications — в этом случае это будет работать намного медленней, чем пессимистическая блокировка.
Т.е. сложность использования оптимистической блокировки пропорциональна сложности защищаемого алгоритма.
А пессимистическую блокировку всегда одинаково легко использовать.
Изменить lock-free алгоритм сложнее, чем однопоточный алгоритм защищаемый пессимистической блокировкой.
— Если есть готовый быстрый lock-free алгоритм, то лучше использовать его.
— Если нет, то берёте быстрый однопоточный алгоритм, и защищаете его пессимистической блокировкой, они универсальны — поэтому есть в стандарте. Tom Kyte их фанат.
Блокировку из статьи можно использовать и в обычных приложениях, и для прототипов высокопроизводительных приложений, из-за её легкого использования.
— Это нужно там, где требуются одновременно много чтений, low latency и есть сложные структуры данных: OLTP (in-memory-DB/noSQL), HFT (High Frequency Trading), для сложных систем с обратной связью критичных к задержке…
— Так же это нужно и там, где требуется high performance, но по какой-то причине нельзя использовать GPU/FPGA, тогда блокировку сложного алгоритма можно совмещать с batching (обработка запросов группой).
В более общем случае, write contention-free очереди я используя для low latency кросс-аппаратного обмена в кластерах с множеством CPU, GPU,… Отдать 16 KB на GPU, обработать и вернуть на CPU занимает 5.5 usec. Занимаюсь реализацией различных задач на HPC кластерах.
Обычно в комментариях таких статей кто-то пишет «Хабр — торт» :)
я вот только одного не понял — если все так круто, красиво и быстро, то почему в стандарте не было реализовано именно так? неужели из-за лишних 60 байт на поток?
(в смысле я то конечно много чего мог не понять, а некоторые особо сложные ассемблерные куски даже пропускал, но это основной вопрос который у меня возник)
(в смысле я то конечно много чего мог не понять, а некоторые особо сложные ассемблерные куски даже пропускал, но это основной вопрос который у меня возник)
1. эти локи существенно полагаются на compile time параметр:
— если его выбрать неправильно, то пострадает производительность
— при каждом изменении придется пересобирать код, а в случае библиотек это еще и ABI сломает
2. это 60 байт умножить на compile time константу и на количество блокировок
3. стандартные блокировки не так уж и плохи, просто не лучшее решение на все случаи жизни
— если его выбрать неправильно, то пострадает производительность
— при каждом изменении придется пересобирать код, а в случае библиотек это еще и ABI сломает
2. это 60 байт умножить на compile time константу и на количество блокировок
3. стандартные блокировки не так уж и плохи, просто не лучшее решение на все случаи жизни
1. Должно быть скомпилировано несколько вариантов блокировки с разным параметрами шаблона: 16, 32, 64, 128, 256, 512, 1024, 2048, 4096… И в run-time автоматически единожды выбираться подходящая на основе, например, std::thread::hardware_concurrency(); или умноженное на 2. Это может быть реализовано в библиотеке содержащей такую блокировку.
2. Касаемо 64 байт на поток, на 64 потоках это может вытеснить 4 КБ ваших данных из кэш L1 в L2 при вызове eXclusive lock — т.е. это дополнительное чтение 64-ёх кэш-линий из L2 по 5нс на каждую, итого ~320нс (на x86_64). Надо доказать, что в большинстве задач это заметно меньше снижает производительность, чем гонять eXlusive-state кэш линию от каждого ядра к каждому при каждом Shared lock и Shared unlock.
Выше все тесты показали, что это так.
3. Да, стандартные блокировки вполне нормальные. Их большой плюс, что их kernel-часть контролируется планировщиком ОС, который может держать их во сне до нужного момента при длительных блокировках — это может повысить энергоэффективность.
4. Для широкого круга пользователей необходимо, как вы верно выше заметили, сделать откат к std::shared_mutex для неудачливых потоков. На длительных блокировках std::shared_mutex безусловно лучше, чем spin-lock.
И даже в этом случае, основная проблема contention-free shared-mutex, что разработчик может создать потоков в десятки или сотни раз больше, чем ядер, и во всех использовать одну cont-free блокироку. В этом случае всех преимуществ contention-free видно не будет, а тот недостаток виден будет.
В этом плане стандартные блокировки дают больше возможностей разработчику делать сколь угодно плохую архитектуру и не проваливаться сразу в ад :)
2. Касаемо 64 байт на поток, на 64 потоках это может вытеснить 4 КБ ваших данных из кэш L1 в L2 при вызове eXclusive lock — т.е. это дополнительное чтение 64-ёх кэш-линий из L2 по 5нс на каждую, итого ~320нс (на x86_64). Надо доказать, что в большинстве задач это заметно меньше снижает производительность, чем гонять eXlusive-state кэш линию от каждого ядра к каждому при каждом Shared lock и Shared unlock.
Выше все тесты показали, что это так.
3. Да, стандартные блокировки вполне нормальные. Их большой плюс, что их kernel-часть контролируется планировщиком ОС, который может держать их во сне до нужного момента при длительных блокировках — это может повысить энергоэффективность.
4. Для широкого круга пользователей необходимо, как вы верно выше заметили, сделать откат к std::shared_mutex для неудачливых потоков. На длительных блокировках std::shared_mutex безусловно лучше, чем spin-lock.
И даже в этом случае, основная проблема contention-free shared-mutex, что разработчик может создать потоков в десятки или сотни раз больше, чем ядер, и во всех использовать одну cont-free блокироку. В этом случае всех преимуществ contention-free видно не будет, а тот недостаток виден будет.
В этом плане стандартные блокировки дают больше возможностей разработчику делать сколь угодно плохую архитектуру и не проваливаться сразу в ад :)
1. только придется таскать все эти инстанцирования за собой, хотя проблему с ABI это решит
2. в большинстве задач впринципе стоит стараться избегать ситуации, когда куча потоков постоянно деруться за одну блокировку — ваши тесты, из того что я увидел, оценивают ровно эту ситуацию.
2. в большинстве задач впринципе стоит стараться избегать ситуации, когда куча потоков постоянно деруться за одну блокировку — ваши тесты, из того что я увидел, оценивают ровно эту ситуацию.
2. В последнем тесте из 3-ей статьи показан более реальный пример, когда симулируется 20 000 ns однопоточной работы между каждым захватом блокировки. Стандартные блокировки там показывают себя совсем плохо на 64 потоках и ядрах.
Достаточно реальных low-latency задач, в которых такое поведение неизбежно.
Достаточно реальных low-latency задач, в которых такое поведение неизбежно.
Такие задачи есть, но не все задачи такие, а память тратится всегда. Я это к тому, что при разработке стандартной библиотеки, которая используется довольно широко, задумываются не только о скорости, но и о памяти.
Поправьте меня, если я не правильно понял результаты, но в тестах там идет сравнения мапы с одним стандартным локом защищяющим доступ к ней, против варианта с партицированием и вашими локами? Если так, то честно говоря сравнение не очень честно, ведь партицированные очень сильно влияет. А в репозитории результатов бенчмарка для 60 ядер я не нешел (тольк для 16 потоков на 10 ядрах с HT) и там safe_map_partitioned_t с дефолтными локами не так уж и плох.
Поправьте меня, если я не правильно понял результаты, но в тестах там идет сравнения мапы с одним стандартным локом защищяющим доступ к ней, против варианта с партицированием и вашими локами? Если так, то честно говоря сравнение не очень честно, ведь партицированные очень сильно влияет. А в репозитории результатов бенчмарка для 60 ядер я не нешел (тольк для 16 потоков на 10 ядрах с HT) и там safe_map_partitioned_t с дефолтными локами не так уж и плох.
В 3-ей статье много тестов — 6 графиков, я предлагал посмотреть последний, а вы добрались только до первого :)
В нем сравнивается много разных блокировок на 16 потоках.
— Партиционированный с моим локом в 2 — 7 раз быстрее, чем партиционированный с дефолтными локами.
— Если партиционированные не очень честные, то зачем вы их смотрите? Странно как-то. Смотрите остальные :)
На том же графике отображены 6 непартиционированных, например:
А в последнем тесте идет сравнение 6 контейнеров на 1 — 64 потока на 72 логических ядра, с симуляцией реальной однопоточной работы 20 000 ns.
Для 64 потоков, непартиционированные:
— contfree-shared-mutex + std::map (это contfree_safe_ptr<std::map>) в 5 раз быстрее, чем std::map + std::shared_mutex
— contfree-shared-mutex + std::map (это contfree_safe_ptr<std::map>) в 3.3 раз быстрее, чем std::map + std::mutex
В нем сравнивается много разных блокировок на 16 потоках.
— Партиционированный с моим локом в 2 — 7 раз быстрее, чем партиционированный с дефолтными локами.
— Если партиционированные не очень честные, то зачем вы их смотрите? Странно как-то. Смотрите остальные :)
На том же графике отображены 6 непартиционированных, например:
При 15% изменений, наш shared-mutex (в составе contfree_safe_ptr<map> & rowlock) показывает производительность 8.37 Mops, что в 10 раз быстрее, чем стандартный std::shared_mutex (в составе safe_ptr<map, std::shared_mutex>), который показывает только 0.74 Mops.
А в последнем тесте идет сравнение 6 контейнеров на 1 — 64 потока на 72 логических ядра, с симуляцией реальной однопоточной работы 20 000 ns.
Для 64 потоков, непартиционированные:
— contfree-shared-mutex + std::map (это contfree_safe_ptr<std::map>) в 5 раз быстрее, чем std::map + std::shared_mutex
— contfree-shared-mutex + std::map (это contfree_safe_ptr<std::map>) в 3.3 раз быстрее, чем std::map + std::mutex
Так вот не надо тут, я посмотрел на два последних, стандартные блокирвки упоминаются в std::mutex & std::map и std::shared_mutex & std::map, но в легенде нет ни слова про то, что в них используется партицирование, отсюда и возник вопрос.
Более того у вас же в репозитории в каталоге banchmark есть бенчмарк и график, где std::map с партицированнием и стандартными мьютексами вы обозначили как safe_map_partitioned_t<>, а std::map & std::mutex обозначает, как я понял стандартную мапу защищенную одним мьютексом.
Я посмотрел ровно то, на что вы указали.
Более того у вас же в репозитории в каталоге banchmark есть бенчмарк и график, где std::map с партицированнием и стандартными мьютексами вы обозначили как safe_map_partitioned_t<>, а std::map & std::mutex обозначает, как я понял стандартную мапу защищенную одним мьютексом.
Я посмотрел ровно то, на что вы указали.
Стандарт не описывает внутреннюю реализацию shared-mutex — она может отличаться в разных компиляторах и разных версиях. Стандарт описывает только некоторые внешние требования.
Меня больше удивляет, почему вообще так долго принимали std::shared_mutex. Сама идея RW-locks существует с незапамятных времен, но только 2 месяца назад утвердили черновик стандарта C++17 — § 33.4.3.4 Shared mutex types
На данный момент: https://isocpp.org/std/status
Также удивляет почему даже в boost так мало lock-free контейнеров: http://www.boost.org/doc/libs/1_64_0/doc/html/lockfree.html
И после всего этого уже ничего не удивляет :)
Меня больше удивляет, почему вообще так долго принимали std::shared_mutex. Сама идея RW-locks существует с незапамятных времен, но только 2 месяца назад утвердили черновик стандарта C++17 — § 33.4.3.4 Shared mutex types
На данный момент: https://isocpp.org/std/status
The committee has completed work on C++17, which is now in its final ISO balloting process, and aims to begin work on C++20 in July.
Также удивляет почему даже в boost так мало lock-free контейнеров: http://www.boost.org/doc/libs/1_64_0/doc/html/lockfree.html
И после всего этого уже ничего не удивляет :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Ускоряем std::shared_mutex в 10 раз