Вроде у всех на слуху современные C++ проекты:
— AI — Фреймворки искусственного интеллекта: Caffe, Caffe2/pytorch, Tensorflow, mxnet, MS CNTK, tiny-dnn
— DLT — Распределенные реестры: Bitcoin, Ethereum, Ripple, EOS, Stellar, Monero, Zcash, Nano, Zilliqa, Metahash
Хорошая статья. Готовый код всегда лучше общих рассуждений.
Встречались сетевые карты mellanox ...
Используете библиотеку VMA для обмена по LAN если на обоих серверах установлены Mellanox Ethernet-карты, или в ваших кейсах почти весь трафик внешний? http://www.mellanox.com/page/software_vma?mtag=vma
The result is a reduction in latency by as much as 300% and an increase in application throughput by as much as 200% per server as compared to applications running on standard Ethernet or InfiniBand interconnect networks.
When the scheduler moves a thread to a new CPU while it has outstanding
receive packets on the old CPU, packets may arrive out of order. To
avoid this, RFS uses a second flow table to track outstanding packets
for each flow
(привязка приложения к нодам во время запуска приложения (numactl, taskset) или потоков к ядрам на уровне приложения (sched_setaffinity, pthread_setaffinity_np) — очень полезная, но отдельная задача)
При RPS один и тот же пакет обрабатывается в kernel-space TCP/IP-stack на одном CPU-Core, и затем в user-space вашего приложения в потоке работающем на другом CPU-Core, это добавляет лишний обмен между ядрами процессора.
При RFS все пакеты одного соединения обрабатываются в kernel-space и user-space на одном ядре.
В 3-ей статье много тестов — 6 графиков, я предлагал посмотреть последний, а вы добрались только до первого :)
В нем сравнивается много разных блокировок на 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
2. В последнем тесте из 3-ей статьи показан более реальный пример, когда симулируется 20 000 ns однопоточной работы между каждым захватом блокировки. Стандартные блокировки там показывают себя совсем плохо на 64 потоках и ядрах.
Достаточно реальных low-latency задач, в которых такое поведение неизбежно.
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 видно не будет, а тот недостаток виден будет.
В этом плане стандартные блокировки дают больше возможностей разработчику делать сколь угодно плохую архитектуру и не проваливаться сразу в ад :)
Стандарт не описывает внутреннюю реализацию shared-mutex — она может отличаться в разных компиляторах и разных версиях. Стандарт описывает только некоторые внешние требования.
Меня больше удивляет, почему вообще так долго принимали std::shared_mutex. Сама идея RW-locks существует с незапамятных времен, но только 2 месяца назад утвердили черновик стандарта C++17 — § 33.4.3.4 Shared mutex types
Спасибо.
Имелось ввиду 4 способа избежать deadlock именно для safe_ptr<>.
Да, std::lock() — разрешает проблему дедлоков, но только для объектов с публичными функциями try_lock(), lock(), unlock().
Но в safe_ptr<> функции try_lock() нету, а lock()/unlock() приватные — спрятаны, чтобы их не блокировал пользователь опасным способом без RAII.
Почему я не сделал свою функцию аналогично std::lock()?
Лично мне lock_timed_any_infinity использовать удобнее, чем std::lock() — приведу 3 примера — последний мне удобнее (да, у меня пропадает возможность разблокировать один safe_ptr<> явно раньше другого):
К тому же во время отладки я могу в lock_timed_any_infinity устанавливать очень большое значение таймаута и добавлять логирование ситуаций, при которых он превышен — тем самым находя места, на которых тратятся ресурсы для разрешения вероятных deadlock-ов. А для рилиза ставить стандартное значение таймаута — для автоматического разрешения дедлоков, которые ещё не нашел.
Плюс бывает полезно самому контролировать алгоритм разрешения дедлоков (графы или таймауты) и размер таймаута. Стандарт позволяет разным реализациям компиляторов использовать разные алгоритмы разрешения дедлоков в void std::lock() / int std::try_lock().
§ 30.4.3 Generic locking algorithms
(5)
Effects: All arguments are locked via a sequence of calls to lock(), try_lock(), or unlock() on each
argument. The sequence of calls shall not result in deadlock, but is otherwise unspecified. [ Note: A
deadlock avoidance algorithm such as try-and-back-off must be used, but the specific algorithm is not
specified to avoid over-constraining implementations. — end note ] If a call to lock() or try_lock()
throws an exception, unlock() shall be called for any argument that had been locked by a call to
lock() or try_lock().
safe_ptr<int> safe_ptr1 = 1; // OK
safe_ptr<int> safe_ptr2 = 2; // OK
safe_ptr<int> safe_ptr3 = safe_ptr2; // OK
safe_ptr1 = safe_ptr2; // error: operator=() is implicitly deleted because the default definition would be ill-formed
Это нужно для алгоритмов сложнее упорядоченного 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 кластерах.
В любом случае для двух и более контейнеров в одном выражении — вам надо использовать lock_timed_any_infinity lock(vecc1, vecc2); или единожды link_safe_ptrs(vecc1, vecc2), т.к. стандарт не гарантирует взаимный порядок создания временных переменных tmp1 и tmp2.
Спасибо! Да, возможно в будущем напишу отдельно о барьерах памяти, с упрощенными правилами — как проверить работоспособность каких-то lock-free алгоритмов. И отдельно как барьеры ложатся на разные архитектуры — где может менять порядок компилятор, а где процессор. А может что-то другое.
Посмотрим, что будет интересно мне и читателям.
lock_timed_any_infinity lock(vecc1, vecc2); // причем не важно в каком порядке они здесь идут
res1 = f(vecc1->a(), vecc2->a());
res2 = f(vecc2->a(), vecc1->a());
Даже если другой поток в другом месте делает так:
lock_timed_any_infinity lock(vecc2, vecc1); // причем не важно в каком порядке они здесь идут
res1 = f(vecc1->a(), vecc2->a());
res2 = f(vecc2->a(), vecc1->a());
Там действительно есть что ещё оптимизировать, 1000% разве это предел :)
Но все они не настолько ускорят, насколько усложнят понимание статьи читателями.
А чего контейнеры попроще concurrent (queue, stack) или посложнее concurrent ordered map (из libcds) не предложили добавить?
— AI — Фреймворки искусственного интеллекта: Caffe, Caffe2/pytorch, Tensorflow, mxnet, MS CNTK, tiny-dnn
— DLT — Распределенные реестры: Bitcoin, Ethereum, Ripple, EOS, Stellar, Monero, Zcash, Nano, Zilliqa, Metahash
https://bitcointalk.org/index.php?topic=2037086.260
1. Так почему же в итоге Ethereum ERC-20?
2. И в чем основная причина неудачи ICO?
Используете библиотеку VMA для обмена по LAN если на обоих серверах установлены Mellanox Ethernet-карты, или в ваших кейсах почти весь трафик внешний?
http://www.mellanox.com/page/software_vma?mtag=vma
(привязка приложения к нодам во время запуска приложения (numactl, taskset) или потоков к ядрам на уровне приложения (sched_setaffinity, pthread_setaffinity_np) — очень полезная, но отдельная задача)
При RPS один и тот же пакет обрабатывается в kernel-space TCP/IP-stack на одном CPU-Core, и затем в user-space вашего приложения в потоке работающем на другом CPU-Core, это добавляет лишний обмен между ядрами процессора.
При RFS все пакеты одного соединения обрабатываются в kernel-space и user-space на одном ядре.
В нем сравнивается много разных блокировок на 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
Достаточно реальных low-latency задач, в которых такое поведение неизбежно.
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 видно не будет, а тот недостаток виден будет.
В этом плане стандартные блокировки дают больше возможностей разработчику делать сколь угодно плохую архитектуру и не проваливаться сразу в ад :)
Меня больше удивляет, почему вообще так долго принимали 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
И после всего этого уже ничего не удивляет :)
Имелось ввиду 4 способа избежать deadlock именно для safe_ptr<>.
Да, std::lock() — разрешает проблему дедлоков, но только для объектов с публичными функциями try_lock(), lock(), unlock().
Но в safe_ptr<> функции try_lock() нету, а lock()/unlock() приватные — спрятаны, чтобы их не блокировал пользователь опасным способом без RAII.
Почему я не сделал свою функцию аналогично std::lock()?
Лично мне lock_timed_any_infinity использовать удобнее, чем std::lock() — приведу 3 примера — последний мне удобнее (да, у меня пропадает возможность разблокировать один safe_ptr<> явно раньше другого):
http://coliru.stacked-crooked.com/a/26b1b20bbcc87700
Поэтому для safe_ptr<> я сделал свой класс блокирования с разрешением дедлоков — lock_timed_any_infinity.
К тому же во время отладки я могу в lock_timed_any_infinity устанавливать очень большое значение таймаута и добавлять логирование ситуаций, при которых он превышен — тем самым находя места, на которых тратятся ресурсы для разрешения вероятных deadlock-ов. А для рилиза ставить стандартное значение таймаута — для автоматического разрешения дедлоков, которые ещё не нашел.
Плюс бывает полезно самому контролировать алгоритм разрешения дедлоков (графы или таймауты) и размер таймаута. Стандарт позволяет разным реализациям компиляторов использовать разные алгоритмы разрешения дедлоков в void std::lock() / int std::try_lock().
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4606.pdf
Внутри safe_ptr<> имеется константная переменная-член класса , которая неявно удаляет operator=().
http://coliru.stacked-crooked.com/a/e892d7d56bddbc1b
Атомарная смена указателя — относительно быстрая операция. То, что вы описали — это оптимистическая блокировка, она может быть медленной. Основная проблема 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 кластерах.
Посмотрим, что будет интересно мне и читателям.
Даже если другой поток в другом месте делает так:
Но все они не настолько ускорят, насколько усложнят понимание статьи читателями.