Я бы тоже хотел lock-free std::vector… Пока не представляю, как его сделать.
random-access assign/get — это позволяет сделать Multi-level array «из коробки» (у меня пока такой коробки нет).
push_back() / pop_back() — с этим сложнее, как я писал: пока вижу решение только с 2-CAS, иначе возможны кратковременные дыры в векторе. Алгоритм 2-CAS (MCAS) сам по себе довольно тяжел и требует довольно нетривиальной инфраструктуры (внутренних дескрипторов), непонятно, будет ли выигрыш по сравнению с std::vector под мьютексом.
Resize()/reserve() — не покатит, это все же lock-free vector, единой непрерывной области памяти там не будет (кстати, часто это основное требование к вектору, — чтобы его данные можно было бы взять как непрерывный буфер и передать куда-нибудь в сишную либу).
В общем, запрос я услышал, тем более что сам периодически подумываю о векторах, но пока… увы
Да, есть, мягко говоря, сложности…
Первая из них — а что такое lock-free vector? Каков его интерфейс?.. Если std::vector, — сложности экспоненциально увеличиваются.
Если lock-free vector — это push_back() / pop_back() + итераторы — это чуть проще. Но что-то это стек напоминает…
Напишите, pls, что Вы ожидаете от lock-free vector!
В общем, просмотрел статью по диагонали, по-моему, это развитие Multi-level array первого анонса 2013 года. Подход весьма многообещающий, но опять я вижу perfect hashing и fixed-sized keys! О май гот (facepalm)!..
Им бы чуть-чуть ещё подумать за два года — и они бы получили полноценный map для ключей переменной длины (например, для std::string) без всякого perfect hashing.
Хотя это пока только мои задумки без доказательства в виде кода.
Теперь понял, — речь именно про разблокировку. Вы правы, сразу вот так пример дедлока на разблокировке привести не смогу (на ум приходят рекурсивные мьютексы).
Но, сугубо ИМХО, нарушение порядка разблокировки без веских на то оснований говорит, по крайней мере, о некой неряшливости кода. Для меня такое было бы сигналом «внимание, возможны мины».
Конечно может, когда доступ к некому ресурсу требует более одного мьютекса. Такое часто случается в fine-grained blocking схемах, например, в алгоритмах конкурентных деревьев. Правильно выбранная стратегия блокирования нескольких мьютексов/спинлоков (например, для дерева — сверху вниз) гарантирует отсутствие дедлоков.
Про фальшивые фунты производства Германии — там вообще блок-бастер, читал в свое время. Запомнилось, как обнаружили, что эти фунты фальшивые (качество было высочайшее). На заводах по выпуску фальшивых фунтов работали и заключенные (французы/голландцы и прочие западноевропейцы), которые в том числе «старили» банкноты. И придумали, как маркировать фальш. Дело в том, что многие англичане носили банкноты, пришпиленные булавкой к внутреннему карману пиджака. На банкнотах — портрет короля. Ни один англичанин не позволит себе проткнуть короля булавкой. Так вот заключенные как раз и протыкали фунты там, где был король.
Сделать это не сложно, сложно сделать это быстро. Ведь не хочется же, чтобы наша программа занималась только самообслуживанием ;-)
Epoch-based reclamation (EBR), по большому счету, не связана с RCU. Классический RCU — это отдельная парадигма построения конкурентных контейнеров, вообще говоря, блокируемая. То, что я называю RCU (точнее, user-space RCU, uRCU), появилось как объединение lock-free подхода (под lock-free я здесь понимаю широкое толкование — атомарные операции и прочий изврат) и метода определения RCU quiescent state, то есть момента, когда данные можно безопасно физически освободить. Результирующая схема, как она вырисовывалась в libcds, концептуально похожа на EBR.
Наоборот, хорошие аллокаторы именно так и поступают — имеют per-thread cache. Но это уже не относится к C++, это уровень run-time (libc) и/или ОС.
Вообще, я считаю, что эксперименты с аллокаторами полезны для собственного развития, но в 90% случаев бесполезны для дела. Хороший аллокатор — это хардкор, основанный на знании тонкостей конкретной операционки.
Прочитал вышеприведенную статью — отличнейший пример оптимизации известного алгоритма! В результате перформанс алгоритма преобразился до неузнаваемости.
Рекомендуется студентам старших курсов профильных вузов и инженерам/исследователям в области оптимизации структур данных, а также всем, кто не ленится применять что-то более чем std::unordered_map
К сожалению, в полной мере — нет, но вот уже собираюсь ;-)
Почему до сих пор нет:
Причина 1 — банальная: надо перестраивать билд-систему тестов, чтобы было удобно добавлять всякие инструменты (= флаги компиляции). Для этой задачи я уже созрел.
Причина 2: очень большая работа. Собирал отзывы тех, кто пробовал tsan именно для проверки race/memory ordering. Боюсь погрязнуть в false positive (или false negative? в общем, в сообщениях об ошибках там, где их нет). На C++ 2015 Russia говорил с одним из разработчиков санитайзеров, Дмитрием Вьюковым. Он подтвердил, что tsan — инструмент более тупой (не в смысле «тупой», а в смысле особо не заточенный под memory ordering), чем его же relacy race detector, и может давать false positive. Применять relacy, — это перелопатить весь код libcds, над этим я думаю…
Причина 3 — всепобеждающая: всегда находится более интересная задача
В общем — нет, не правы.
Во-первых, рассуждения «по факту» неявно подразумевают наличие этого самого «факта» — то есть железа и задачи. Для своего железа и своей задачи вы вольны выбирать то, что будет наиболее оптимальным.
Во-вторых, wait-free — более сильное требование, чем lock-free, следовательно, более тяжелое, в том числе по производительности, как это ни странно. И уж тем более странно рассуждать о wait-free для глобального и поячеечных локов.
В третьих, про геморрой с HP/RCU. Я, видимо, был недостаточно точен в своих статьях. Повторюсь: с точки зрения использования lock-free алгоритмов, «геморрой» с HP и RCU начинается с инициализации, на ней же и заканчивается, то есть речь идет о нескольких строках кода в начале программы/потока. С точки зрения разработки lock-free структуры, — да, геморроя много, но он весь спрятан внутри методов lock-free контейнера.
Кроме того, как я теперь понимаю, порог входа в мир lock-free достаточно высок, нужно не только знать, как оно работает внутри, но и иметь готовые инструменты, — HP, uRCU, transactional memory, схемы версионности и пр. Создать их с нуля — действительно геморрой. Хотелось бы найти готовые, чтобы поиграться. Поэтому я и начал писать про это и про libcds, — вот инструменты, вот реализация, берите, пробуйте, рапортуйте об ошибках, предлагайте более оптимальные решения.
В следующей статье будет график производительности для сферического коня в вакууме (то есть синтетического теста) для всех рассмотренных concurrent map по сравнению с std::map/std::unordered_map с блокировкой std::mutex'ом.
На статью это не тянет, ну разве что на статью только с графиками.
При чтении ваших статей меня не покидает ощущение, что это все настолько сложно и запутанно, что просто обязано работать медленнее, чем простые блокирующие алгоритмы
Оно и работает медленнее для одного потока, — кодильник-то нехилый. Но для множества потоков, то есть при большой конкуренции, возможен выигрыш, — на это и делается ставка в такого типа контейнерах.
особенно если блокировать не все, а на уровне ячеек структуры данных
Если я правильно понял, то это обычное заблуждение: блокировка на уровне ячеек структуры данных (fine-grained locking) не освобождает от необходимости поддерживать структуру данных в консистентном состоянии, то есть применять те же атомарные инструкции, схему управления памятью и пр. методы. Более того, описанные мною lock-free структуры не дают каких-либо гарантий по поводу данных в элементах контейнера, а только гарантируют корректное состояние контейнера в любое время. Это значит, что если вы хотите изменить какое-то неключевое поле в данных map'а, то во избежание гонок доступ к этому полю вы должны обеспечивать сами — атомиками, спин-локом, мьютексом, монитором и т.п. Конкурентный map обеспечит только поиск по ключу и гарантию, что, пока вы изменяете это поле в данных найденного элемента, этот элемент не будет физически удален (delete).
random-access assign/get — это позволяет сделать Multi-level array «из коробки» (у меня пока такой коробки нет).
push_back() / pop_back() — с этим сложнее, как я писал: пока вижу решение только с 2-CAS, иначе возможны кратковременные дыры в векторе. Алгоритм 2-CAS (MCAS) сам по себе довольно тяжел и требует довольно нетривиальной инфраструктуры (внутренних дескрипторов), непонятно, будет ли выигрыш по сравнению с std::vector под мьютексом.
Resize()/reserve() — не покатит, это все же lock-free vector, единой непрерывной области памяти там не будет (кстати, часто это основное требование к вектору, — чтобы его данные можно было бы взять как непрерывный буфер и передать куда-нибудь в сишную либу).
В общем, запрос я услышал, тем более что сам периодически подумываю о векторах, но пока… увы
Первая из них — а что такое lock-free vector? Каков его интерфейс?.. Если std::vector, — сложности экспоненциально увеличиваются.
Если lock-free vector — это
push_back()/pop_back()+ итераторы — это чуть проще. Но что-то это стек напоминает…Напишите, pls, что Вы ожидаете от lock-free vector!
Им бы чуть-чуть ещё подумать за два года — и они бы получили полноценный map для ключей переменной длины (например, для std::string) без всякого perfect hashing.
Хотя это пока только мои задумки без доказательства в виде кода.
Но, сугубо ИМХО, нарушение порядка разблокировки без веских на то оснований говорит, по крайней мере, о некой неряшливости кода. Для меня такое было бы сигналом «внимание, возможны мины».
Epoch-based reclamation (EBR), по большому счету, не связана с RCU. Классический RCU — это отдельная парадигма построения конкурентных контейнеров, вообще говоря, блокируемая. То, что я называю RCU (точнее, user-space RCU, uRCU), появилось как объединение lock-free подхода (под lock-free я здесь понимаю широкое толкование — атомарные операции и прочий изврат) и метода определения RCU quiescent state, то есть момента, когда данные можно безопасно физически освободить. Результирующая схема, как она вырисовывалась в libcds, концептуально похожа на EBR.
Вообще, я считаю, что эксперименты с аллокаторами полезны для собственного развития, но в 90% случаев бесполезны для дела. Хороший аллокатор — это хардкор, основанный на знании тонкостей конкретной операционки.
И эта ссылка есть в статье
Хотя это подтверждает тезис о том, что не существует единого «хорошего для всех» map'а. Каждой задаче — свой map.
Почему до сих пор нет:
Причина 1 — банальная: надо перестраивать билд-систему тестов, чтобы было удобно добавлять всякие инструменты (= флаги компиляции). Для этой задачи я уже созрел.
Причина 2: очень большая работа. Собирал отзывы тех, кто пробовал tsan именно для проверки race/memory ordering. Боюсь погрязнуть в false positive (или false negative? в общем, в сообщениях об ошибках там, где их нет). На C++ 2015 Russia говорил с одним из разработчиков санитайзеров, Дмитрием Вьюковым. Он подтвердил, что tsan — инструмент более тупой (не в смысле «тупой», а в смысле особо не заточенный под memory ordering), чем его же relacy race detector, и может давать false positive. Применять relacy, — это перелопатить весь код libcds, над этим я думаю…
Причина 3 — всепобеждающая: всегда находится более интересная задача
В общем — нет, не правы.
Во-первых, рассуждения «по факту» неявно подразумевают наличие этого самого «факта» — то есть железа и задачи. Для своего железа и своей задачи вы вольны выбирать то, что будет наиболее оптимальным.
Во-вторых, wait-free — более сильное требование, чем lock-free, следовательно, более тяжелое, в том числе по производительности, как это ни странно. И уж тем более странно рассуждать о wait-free для глобального и поячеечных локов.
В третьих, про геморрой с HP/RCU. Я, видимо, был недостаточно точен в своих статьях. Повторюсь: с точки зрения использования lock-free алгоритмов, «геморрой» с HP и RCU начинается с инициализации, на ней же и заканчивается, то есть речь идет о нескольких строках кода в начале программы/потока. С точки зрения разработки lock-free структуры, — да, геморроя много, но он весь спрятан внутри методов lock-free контейнера.
Кроме того, как я теперь понимаю, порог входа в мир lock-free достаточно высок, нужно не только знать, как оно работает внутри, но и иметь готовые инструменты, — HP, uRCU, transactional memory, схемы версионности и пр. Создать их с нуля — действительно геморрой. Хотелось бы найти готовые, чтобы поиграться. Поэтому я и начал писать про это и про libcds, — вот инструменты, вот реализация, берите, пробуйте, рапортуйте об ошибках, предлагайте более оптимальные решения.
На статью это не тянет, ну разве что на статью только с графиками.
Оно и работает медленнее для одного потока, — кодильник-то нехилый. Но для множества потоков, то есть при большой конкуренции, возможен выигрыш, — на это и делается ставка в такого типа контейнерах.
Если я правильно понял, то это обычное заблуждение: блокировка на уровне ячеек структуры данных (fine-grained locking) не освобождает от необходимости поддерживать структуру данных в консистентном состоянии, то есть применять те же атомарные инструкции, схему управления памятью и пр. методы. Более того, описанные мною lock-free структуры не дают каких-либо гарантий по поводу данных в элементах контейнера, а только гарантируют корректное состояние контейнера в любое время. Это значит, что если вы хотите изменить какое-то неключевое поле в данных map'а, то во избежание гонок доступ к этому полю вы должны обеспечивать сами — атомиками, спин-локом, мьютексом, монитором и т.п. Конкурентный map обеспечит только поиск по ключу и гарантию, что, пока вы изменяете это поле в данных найденного элемента, этот элемент не будет физически удален (delete).