• Lock-free структуры данных. Внутри. RCU
    0
    Честно говоря, я из кода не понял, каким образом он что-либо защищает и что он гарантирует…
  • Lock-free структуры данных. Внутри. RCU
    0
    del
  • Lock-free структуры данных. Эволюция стека
    0
    Я просто поясню, что взрывает мозг — то, что в обоих случаях мы _пишем_ (и читаем) в top

    Да, и не только у вас. RMW-операции могут обладать как acquire, так и release семантикой. К сожалению, стандарт довольно подробно описывает атомарные чтение/запись, и только вскользь — атомарные RMW, типа, «они могут обладать как acquire, так и release семантикой». А ведь это — самое главное, ИМХО: без RMW atomic'и довольно бесполезны. Мы сами наделяем RMW-операции нужной семантикой: одни становятся «операциями acquire-чтения», другие — «операциями release-записи», хотя на самом деле они операции и чтения, и записи.
    С точки зрения записи в top, парой к release мог бы быть guard.protect( m_Top ), если бы он использовал acquire семантику (но это, вероятно, не так, и он использует relaxed).

    Мог бы, но здесь как раз и проявляется семантика: операции с контейнером и с Hazard Pointer'ом — это разные семантические уровни (HP на уровень глубже и играет вспомогательную роль). На самом деле в глубине HP есть m_Top.load( acquire ). Но я не уверен, что этот acquire-load обеспечит нам синхронизацию push и pop.
    Верно я понимаю, что рассматривая семантику мы как бы говорим, что если происходит push/pop, то менять их местами нельзя (ведь стек может быть пуст), а pop/push — пожалуйста (ну вытолкнем мы 2й элемент, а не 1й, ну бывает).

    Да, можно сказать и так.
  • Lock-free структуры данных. Эволюция стека
    0
    На самом деле, вопрос далеко не глупый. На него есть два ответа.
    Первый — чисто технический: release/acquire всегда идут парами. Если в push() мы делаем release-CAS, то в pop — acquire-CAS.
    Второй — точнее. Memory order задают семантику атомарных RMW-операций. Метод push() — это метод записи данных в стек, а раз запись — значит, из пары «acquire или release» мы можем выбрать только release. Метод pop() — это чтение данных из стека, а для чтения подходящим memory order является acquire.
  • Асинхронность 3: Субъекторная модель
    +2
    Замечательная статья!
    В защиту автора (хотя, мне кажется, он не нуждается в защите) выражу свое мнение: подход, основанный на истинных stackful сопрограммах, который на протяжении уже нескольких лет разрабатывает автор, мне кажется очень перспективным. И намного более глубоким и красивым, чем то, что предлагают ввести в стандарт C++. Стандарты всегда запаздывают, так как описывают вещи для всех уже привычные и тысячу раз испробованные.
    Недостатками этого подхода мне видится две вещи:
    1. Отдельный стек для каждой сопрограммы. На самом деле, это достоинство (все данные — на стеке, всегда под рукой, сколько бы нас не прерывали), но за которым надо внимательно следить, иначе при чрезмерном увлечении можно всю память сожрать. Быть может, стоит ограничить размер стека сопрограмм, но это уже детали.
    2. Необычность. Этот «недостаток» лечится только опытом. Во-первых, надо попробовать все другие методы асинхронного/многопоточного программирования, начиная от тривиальных mutex/condvar, наплодить 100500 потоков на 4-ядерной машинке, удивиться «а чё оно так медленно работает и падает/лочится», затем пройти через callback hell, попробовать переписать callback на stackless сопрограммах, понять, что просто это не удастся, надо много переписывать. Во-вторых, надо научиться думать в терминах модели stackful сопрограмм; это бывает весьма нелегко, — заставить свой мозг работать по-другому, в терминах новой модели. Например, синхронизировать вовсе без примитивов синхронизации. Или: сделать многопоточную программу, в которой многопоточная логика не вылезает наверх, не затеняет логику самой программы, так что, читая код, вы видите, что делает программа, а не потроха взаимодействия потоков, future, callback и прочую машинерию, за которой леса не видно.

    Вообще, трудность введения новых моделей взаимодействия компонентов программы всегда одна и та же: программу приходится переписывать практически с нуля. И вторая трудность — выбор правильной модели.

    PS: сам я модель stackful сопрограмм не применял по причинам, описанным выше, — негде было. Но искренне завидую тем, кто это попробовал на реальных задачах.
  • Потокобезопасный std::map с производительностью lock-free map
    +5
    Замечательные статьи, автору респект!
    У меня вопрос: почему вы выбрали BronsonAVLTree и SkipList для сравнения? Только потому, что это стандартные map, не-hash map?..

    Я спрашиваю потому, что ваша техника прямо ложится на простой hash-map: хеш-таблица, доступ к каждому элементу таблицы — под вашим легким shared mutex; у Shavit & Herlihy подобная техника называется striping. Не пробовали?..
    ИМХО, подход надо развивать, попробовать на каких-то lock-based конкурентных алгоритмах — тот же cuckoo-hashing, hopscotch hashing и пр.
  • Новые возможности продукта СКАТ DPI 6.0 «Севастополь» от VAS Experts
    0
    Спасибо за ценный совет! Накопление способов использования очень важно для нас.
    В принципе, это возможно сделать. Но здесь может быть другая засада — некоторые радиусы не имеют возможности различать источник запроса — отвечают на любой Access-Request как будто он приходит из одного места (хм… получилось как-то двусмысленно, но в данном контексте даже хорошо ;). В этом случае такой радиус может послать циске такое, что она долго будет плеваться…
    Можно также сделать на стороне fastDPI настраиваемый vendor-specific атрибут, в котором должна находиться строка определенного формата, и выкусывать из этой строки regexp'ами то, что нам нужно.
  • Новые возможности продукта СКАТ DPI 6.0 «Севастополь» от VAS Experts
    0
    del
  • Lock-free структуры данных. Итераторы: multi-level array
    0
    Спасибо!
    Народ, расчехляем загашники!
  • Lock-free структуры данных. Итераторы: multi-level array
    0
    Спасибо за ссылку!
  • Lock-free структуры данных. Итераторы: multi-level array
    +2
    Я бы тоже хотел 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 структуры данных. Итераторы: multi-level array
    0
    Да, есть, мягко говоря, сложности…
    Первая из них — а что такое lock-free vector? Каков его интерфейс?.. Если std::vector, — сложности экспоненциально увеличиваются.
    Если lock-free vector — это push_back() / pop_back() + итераторы — это чуть проще. Но что-то это стек напоминает…
    Напишите, pls, что Вы ожидаете от lock-free vector!
  • Lock-free структуры данных. Итераторы: multi-level array
    +1
    В общем, просмотрел статью по диагонали, по-моему, это развитие Multi-level array первого анонса 2013 года. Подход весьма многообещающий, но опять я вижу perfect hashing и fixed-sized keys! О май гот (facepalm)!..
    Им бы чуть-чуть ещё подумать за два года — и они бы получили полноценный map для ключей переменной длины (например, для std::string) без всякого perfect hashing.
    Хотя это пока только мои задумки без доказательства в виде кода.
  • Lock-free структуры данных. Итераторы: multi-level array
    0
    Скачано! Спасибо большое!!!
  • Lock-free структуры данных. Concurrent map: разминка
    0
    Теперь понял, — речь именно про разблокировку. Вы правы, сразу вот так пример дедлока на разблокировке привести не смогу (на ум приходят рекурсивные мьютексы).
    Но, сугубо ИМХО, нарушение порядка разблокировки без веских на то оснований говорит, по крайней мере, о некой неряшливости кода. Для меня такое было бы сигналом «внимание, возможны мины».
  • Lock-free структуры данных. Concurrent map: разминка
    0
    Конечно может, когда доступ к некому ресурсу требует более одного мьютекса. Такое часто случается в fine-grained blocking схемах, например, в алгоритмах конкурентных деревьев. Правильно выбранная стратегия блокирования нескольких мьютексов/спинлоков (например, для дерева — сверху вниз) гарантирует отсутствие дедлоков.
  • Lock-free структуры данных. Итераторы: multi-level array
    +3
    К сожалению, «тут» ничего не описано, — дана лишь вводная часть статьи. Доступа к платным ресурсам у меня нет. Если Вы имеете оригинал — поделитесь.
  • Как делают бумажные деньги
    +2
    Про фальшивые фунты производства Германии — там вообще блок-бастер, читал в свое время. Запомнилось, как обнаружили, что эти фунты фальшивые (качество было высочайшее). На заводах по выпуску фальшивых фунтов работали и заключенные (французы/голландцы и прочие западноевропейцы), которые в том числе «старили» банкноты. И придумали, как маркировать фальш. Дело в том, что многие англичане носили банкноты, пришпиленные булавкой к внутреннему карману пиджака. На банкнотах — портрет короля. Ни один англичанин не позволит себе проткнуть короля булавкой. Так вот заключенные как раз и протыкали фунты там, где был король.
  • Lock-free структуры данных. Внутри. Схемы управления памятью
    0
    Сделать это не сложно, сложно сделать это быстро. Ведь не хочется же, чтобы наша программа занималась только самообслуживанием ;-)

    Epoch-based reclamation (EBR), по большому счету, не связана с RCU. Классический RCU — это отдельная парадигма построения конкурентных контейнеров, вообще говоря, блокируемая. То, что я называю RCU (точнее, user-space RCU, uRCU), появилось как объединение lock-free подхода (под lock-free я здесь понимаю широкое толкование — атомарные операции и прочий изврат) и метода определения RCU quiescent state, то есть момента, когда данные можно безопасно физически освободить. Результирующая схема, как она вырисовывалась в libcds, концептуально похожа на EBR.
  • Lock-free структуры данных. Внутри. Схемы управления памятью
    +1
    Наоборот, хорошие аллокаторы именно так и поступают — имеют per-thread cache. Но это уже не относится к C++, это уровень run-time (libc) и/или ОС.
    Вообще, я считаю, что эксперименты с аллокаторами полезны для собственного развития, но в 90% случаев бесполезны для дела. Хороший аллокатор — это хардкор, основанный на знании тонкостей конкретной операционки.
  • Lock-free структуры данных. Внутри. Схемы управления памятью
    0
    Все, что вы описываете, называется Allocator, — шаблонный аргумент контейнера.
  • Как я написал компилятор C за 40 дней
    +1
    Не удержусь… здесь
    И эта ссылка есть в статье
  • Lock-free структуры данных. Concurrent maps: деревья
    0
    Прочитал вышеприведенную статьюотличнейший пример оптимизации известного алгоритма! В результате перформанс алгоритма преобразился до неузнаваемости.
    Рекомендуется студентам старших курсов профильных вузов и инженерам/исследователям в области оптимизации структур данных, а также всем, кто не ленится применять что-то более чем std::unordered_map
  • Lock-free структуры данных. Concurrent maps: деревья
    0
    Спасибо за ссылки!
  • Lock-free структуры данных. Concurrent maps: деревья
    0
    Для меня это несколько неожиданно.
    Хотя это подтверждает тезис о том, что не существует единого «хорошего для всех» map'а. Каждой задаче — свой map.
  • Lock-free структуры данных. Concurrent maps: деревья
    0
    К сожалению, в полной мере — нет, но вот уже собираюсь ;-)
    Почему до сих пор нет:
    Причина 1 — банальная: надо перестраивать билд-систему тестов, чтобы было удобно добавлять всякие инструменты (= флаги компиляции). Для этой задачи я уже созрел.
    Причина 2: очень большая работа. Собирал отзывы тех, кто пробовал tsan именно для проверки race/memory ordering. Боюсь погрязнуть в false positive (или false negative? в общем, в сообщениях об ошибках там, где их нет). На C++ 2015 Russia говорил с одним из разработчиков санитайзеров, Дмитрием Вьюковым. Он подтвердил, что tsan — инструмент более тупой (не в смысле «тупой», а в смысле особо не заточенный под memory ordering), чем его же relacy race detector, и может давать false positive. Применять relacy, — это перелопатить весь код libcds, над этим я думаю…
    Причина 3 — всепобеждающая: всегда находится более интересная задача
  • Lock-free структуры данных. Concurrent maps: деревья
    +1
    Спасибо! Значит, цель достигнута :-)
  • Lock-free структуры данных. Concurrent maps: skip list
    +2
    Или я не прав?

    В общем — нет, не правы.
    Во-первых, рассуждения «по факту» неявно подразумевают наличие этого самого «факта» — то есть железа и задачи. Для своего железа и своей задачи вы вольны выбирать то, что будет наиболее оптимальным.
    Во-вторых, wait-free — более сильное требование, чем lock-free, следовательно, более тяжелое, в том числе по производительности, как это ни странно. И уж тем более странно рассуждать о wait-free для глобального и поячеечных локов.
    В третьих, про геморрой с HP/RCU. Я, видимо, был недостаточно точен в своих статьях. Повторюсь: с точки зрения использования lock-free алгоритмов, «геморрой» с HP и RCU начинается с инициализации, на ней же и заканчивается, то есть речь идет о нескольких строках кода в начале программы/потока. С точки зрения разработки lock-free структуры, — да, геморроя много, но он весь спрятан внутри методов lock-free контейнера.
    Кроме того, как я теперь понимаю, порог входа в мир lock-free достаточно высок, нужно не только знать, как оно работает внутри, но и иметь готовые инструменты, — HP, uRCU, transactional memory, схемы версионности и пр. Создать их с нуля — действительно геморрой. Хотелось бы найти готовые, чтобы поиграться. Поэтому я и начал писать про это и про libcds, — вот инструменты, вот реализация, берите, пробуйте, рапортуйте об ошибках, предлагайте более оптимальные решения.
  • Lock-free структуры данных. Concurrent maps: skip list
    0
    В следующей статье будет график производительности для сферического коня в вакууме (то есть синтетического теста) для всех рассмотренных concurrent map по сравнению с std::map/std::unordered_map с блокировкой std::mutex'ом.
    На статью это не тянет, ну разве что на статью только с графиками.
    При чтении ваших статей меня не покидает ощущение, что это все настолько сложно и запутанно, что просто обязано работать медленнее, чем простые блокирующие алгоритмы

    Оно и работает медленнее для одного потока, — кодильник-то нехилый. Но для множества потоков, то есть при большой конкуренции, возможен выигрыш, — на это и делается ставка в такого типа контейнерах.
    особенно если блокировать не все, а на уровне ячеек структуры данных

    Если я правильно понял, то это обычное заблуждение: блокировка на уровне ячеек структуры данных (fine-grained locking) не освобождает от необходимости поддерживать структуру данных в консистентном состоянии, то есть применять те же атомарные инструкции, схему управления памятью и пр. методы. Более того, описанные мною lock-free структуры не дают каких-либо гарантий по поводу данных в элементах контейнера, а только гарантируют корректное состояние контейнера в любое время. Это значит, что если вы хотите изменить какое-то неключевое поле в данных map'а, то во избежание гонок доступ к этому полю вы должны обеспечивать сами — атомиками, спин-локом, мьютексом, монитором и т.п. Конкурентный map обеспечит только поиск по ключу и гарантию, что, пока вы изменяете это поле в данных найденного элемента, этот элемент не будет физически удален (delete).
  • Lock-free структуры данных. Concurrent maps: skip list
    0
    Спасибо :-)
  • Lock-free структуры данных. Concurrent maps: skip list
    0
    Чтобы не верить на слово, нужно попробовать самому для свое задачи. У меня цель несколько другая — показать, что решения lock-free существуют и как они выглядят изнутри.
    О размерностях. Думаю, здесь больше зависимость от числа писателей/читателей, то есть от степени конкурентности, чем от числа элементов. Конкретно skip-list разрабатывался для больших map'ов — от сотен тысяч элементов, ИМХО.
  • Lock-free структуры данных. Concurrent maps: rehash, no rebuild
    +1
    Мне кажется, что для обычных, необращенных хешей — most significant bit, и от endianness это не зависит:
    tmp1 := MSB( h1 ^ h2 ) — дает номер старшего бита, в котором h1 и h2 различаются.
    tmp2 := 1 << tmp1 — дает число с этим единственным битом = 1. Надеюсь, endianness не влияет на сдвиги.
    tmp3 := tmp2 & h2 — тестируем, у кого выставлен этот бит. Если у h2, то tmp3 != 0, то есть h2 > h1 и less() возвратит true. Если не у h2 (значит, у h1), то tmp3 == 0 и less() возвратит false.
    Вроде бы все правильно. Одно «но» — случай h1 == h2: MSB тогда не определена, и предикат less должен выглядеть так:
    return h1 != h2 && ((1 << MSB(h1 ^ h2)) & h2 ) != 0;
    

    Для обращенных хешей (shah) MSB превращается в LSB. То есть мы можем, не обращая порядок бит, сравнивать хеши.
    Остается вопрос — будет ли это быстрее, чем вычисление shah. По виду выражений — должно быть побыстрее, но учитывая, что shah мы храним, чтобы его не вычислять постоянно, — не факт, что быстрее.
    Идея интересная, надо проверить…
  • Lock-free структуры данных. Concurrent maps: rehash, no rebuild
    +1
    А вот этот вопрос — обязательна ли отсортированность — для меня до сих пор остается открытым.
    Во всех работах про hash map рассматриваются только отсортированные списки, — почему?
    У меня есть пока два аргумента «за» отсортированность:
    • если её не будет, то вставка будет происходить всегда в конец списка, и мы получим толкотню CAS'ов на конце, — то есть ту же самую ситуацию, что и в lock-free очередях/стеках, которые из-за этого плохо масштабируются. С другой стороны, вероятность contention для hash map весьма низка, если у нас «хорошо разбрасывающая» хеш-функция и заполненность hash map достаточно низка; к тому же основная операция в hash map — поиск
    • Поиск в отсортированном списке в среднем будет в два раза быстрее. Контраргумент: списки в hash map очень короткие, так что эти «два раза» вряд ли будут заметны

    Убийственного аргумента «за» отсортированность я пока что не придумал.
  • Lock-free структуры данных. Concurrent maps: rehash, no rebuild
    +1
    Имеется в виду:
    struct less {
        bool operator()( size_t h1, size_t h2) const
        {
             return ((1 << MSB(h1 ^ h2)) & h2 ) != 0;
        }
    };
    

    Так?
    Я не вижу, как эта формула обеспечит нам ненужность перестройки списка при рехешинге, см предыдущий комментарий. Не могли бы пояснить?
  • Lock-free структуры данных. Concurrent maps: rehash, no rebuild
    +1
    Список в целом у нас должен быть как-то отсортирован, иначе непонятно, как вставлять новый элемент (это относится только к конкурентным map'ам). Обычно в hash map сортируют по хешам и ключам (если хеши равны) или просто по ключам в списке коллизий. В split-ordered list сортировка по хешам или ключам не подходит, см. рисунки (для наглядности я полагаю, что хеш равен ключу), ведь нам надо обеспечить, чтобы список не надо было перестраивать при рехешинге. Если обратить хеш-значения, список становится отсортированным и при расщеплении bucket'а отсортированность сохраняется, — то, что надо. Это просто прием, трюк. Наконец, если хеши равны — сортируем по ключам, то есть критерий сортировки комбинированный.
  • Lock-free структуры данных. Concurrent map: разминка
    0
    Нет, рациональные дроби не проверял. Видимо, надо подумать и внедрить ещё одну стратегию в traits — стратегию оценки load factor. Тогда можно будет довольно легко проверять различные подходы.

    Кстати, в исходниках у вас вроде size_t load factor, не unsigned int.

    Да, size_t. В комменте я хотел отметить, что load factor в libcds — это целое число (точнее говоря — натуральное).
  • Lock-free структуры данных. Concurrent map: разминка
    +1
    Поднял сырые результаты тестов для статьи.
    Пожалуй, я с вами соглашусь:
    MichaelHashMap (это как раз hash map без rehashing'а) на HP, 16 потоков, 90% find, 5% insert, 5% erase:
    Load factor=1: Total ops=2131203280, speed=71040109 ops/sec
    Load factor=2: Total ops=1983375842, speed=66112528 ops/sec
    Load factor=4: Total ops=1582585813, speed=52752860 ops/sec

    Не разы, как видно, но десяток-другой процентов.
    Load factor меньше 1, как принято в цивилизованном мире, в libcds не поддерживается (пробовал — много жрет оценка, так что load factor у меня — unsigned int)
  • Lock-free структуры данных. Concurrent map: разминка
    0
    Да, не конкурентный, я хотел заметить, что есть некие идеи, которые наверняка можно совместить и с concurrentMap на локах, и lock-free.

    Действтельно, есть. Довольно известная работа об open addressing hash map. Стоит у меня в списке todo уже несколько лет, каждый раз читаю её и думаю — нет, попозже, есть более интересные алгоритмы с более предсказуемым результатом.
  • Lock-free структуры данных. Concurrent map: разминка
    0
    Я бы с большой осторожностью давал такие оценки

    Именно поэтому и пишу — «по результатам моих экспериментов».
  • Lock-free структуры данных. Concurrent map: разминка
    0
    Помешать сделать rehashing — это значит, что во время rehashing'а нельзя делать insert/erase, find — в принципе, можно, с приседаниями.
    Насчет Java я не силен, но о Doug Lea и java.util.concurrent.ConcurrentHashMap кое-что читал. Если мне не изменяет память, там внутри блокировки и довольно изощренный механизм их применения, а желаемый уровень конкуренции задается в конструкторе. Насчет расширния массива блокировок — см. ремарку о refinable hash map.
    PauselessHashMap — прочитал анонс, не понял, в чем там конкурентность. В том, что мы должны сами блокировать извне, если она необходима?.. Автор, как я понял, не заявляет о том, что его класс является concurrent hash map.
    Вообще, я уже не раз отмечал, что Java-алгоритмы иногда трудно переносить на C++ «с листа» — многое, чего нет в C++, в Java встроено, — например, GC, synchronized.