Рубрика «lock-free»

в 7:05, , рубрики: c++, c++11, lock-free, Блог компании Яндекс, Программирование, Процессоры

ARM и программирование без блокировок - 1

Выпуск ARM-процессора Apple M1 вдохновил меня на то, чтобы написать в Твиттер про опасности программирования без блокировок (lock-free). Этот твит вызвал бурную дискуссию. Обсуждение прошло довольно неплохо, учитывая то, что попытки втиснуть в рамки Твиттера обсуждениие такой сложной темы, как модели памяти центрального процессора, — в принципе бессмысленны. Но у меня осталось желание немного раскрыть тему.

Этот пост задуман не только как обычная вводная статья про опасности программирования без блокировок (о которых я в последний раз писал около 15 лет назад), но и как объяснение, почему слабая модель памяти ARM ломает некоторый код, и почему этот код, вероятно, не работал изначально. Я также хочу объяснить, почему стандарт C++11 значительно улучшил ситуацию в программировании без блокировок (несмотря на возражения против противоположной точки зрения).
Читать полностью »

в 21:44, , рубрики: c++, c++11, C++14, high performance, lock, lock-free, locks, low-latency, высокая производительность, параллельное программирование, Программирование

Примеры использования и тестирование потоко-безопасного указателя и contention-free shared-mutex

В этой статье мы покажем: дополнительные оптимизации, примеры использования и тестирование разработанного нами потоко-безопасного указателя с оптимизированным разделяемым мьютексом contfree_safe_ptr<T> – это эквивалентно safe_ptr<T, contention_free_shared_mutex<>>
В конце покажем сравнительные графики тестов нашего thread-safe указателя и одних из лучших lock-free алгоритмов из libCDS на процессорах Intel Core i5/i7, Xeon, 2 x Xeon.
Читать полностью »

в 13:22, , рубрики: algorithms, lock-free, multithreading, parallel programming, wunderfund, Алгоритмы, Блог компании Wunder Fund, параллельное программирование, Программирование

В одном из прежних постов я рассказывал, как реализовать «простейшую в мире lock-free хеш-таблицу» на C++. Она была настолько проста, что было невозможно удалять из нее записи или менять ее размерность. С тех пор прошло несколько лет, и не так давно я написал несколько многопоточных ассоциативных массивов без таких ограничений. Их можно найти в моем проекте Junction на GitHub.

Junction содержит несколько многопоточных реализаций интерфейса map – даже «самая простая в мире» среди них, под названием ConcurrentMap_Crude. Для краткости будем называть ее Crude map. В этом посте я объясню разницу между Crude map и Linear map из библиотеки Junction. Linear — самый простой map в Junction, поддерживающий и изменение размера, и удаление.

Можете ознакомиться с объяснением того, как работает Crude map, в первоначальном посте. Если коротко, то она основана на открытой адресации и линейном пробировании. Это значит, что она по сути является большим массивом ключей и значений, использующим линейный поиск. Во время добавления или поиска заданного ключа мы вычисляем хеш от ключа, чтобы определить, с какого места начать поиск. Добавление и поиск данных возможны в многопоточном режиме.

Что такое Resizable Concurrent Map - 1
Читать полностью »

в 15:07, , рубрики: algorithms, lock-free, multithreading, parallel programming, wunderfund, Алгоритмы, Блог компании Wunder Fund, параллельное программирование, Программирование

image

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

в 13:02, , рубрики: algorithms, lock-free, multithreading, parallel programming, wunderfund, Алгоритмы, Блог компании Wunder Fund, параллельное программирование, Программирование

image

В этом посте мы хотели бы еще раз поднять тему программирования без блокировок, сперва дав ему определение, а затем выделить из всего многообразия информации несколько ключевых положений. Мы покажем, как эти положения соотносятся между собой, с помощью блок-схем, а потом мы немного коснемся деталей. Минимальное требование к разработчику, постигающему lock-free, — умение писать правильный многопоточный код, используя мьютексы или другие высокоуровневые объекты синхронизации, например, семафоры или события.
Читать полностью »

в 6:01, , рубрики: c++, iterator, libcds, lock-free, map, Алгоритмы, параллельное программирование, Программирование

Lock-free структуры данных. Iterable list - 1 Lock-free list является основой многих интересных структур данных, — простейшего hash map, где lock-free list используется как список коллизий, split-ordered list, построенный целиком на списке с оригинальным алгоритмом расщепления bucket'а, многоуровневого skip list, являющегося по сути иерархическим списком списков. В предыдущей статье мы убедились, что можно придать такую внутреннюю структуру конкурентному контейнеру, чтобы он поддерживал thread-safe итераторы в динамичном мире lock-free контейнеров. Как мы выяснили, основным условием для того, чтобы lock-free контейнер стал итерабельным, является стабильность внутренней структуры: ноды не должны физически удаляться (delete). В этом случае итератор суть просто (быть может, составной) указатель на ноду с возможностью перехода к следующей (оператор инкремента).
Можно ли такой подход распространить на lock-free list?.. Посмотрим…
Читать полностью »

в 6:12, , рубрики: c++, iterator, libcds, lock-free, map, Алгоритмы, параллельное программирование, Программирование

Lock-free структуры данных. Итераторы: multi-level array - 1
В предыдущих частях опуса (1, 2, 3) мы рассмотрели внутреннее строение lock-free map и убедились, что все основные операции — поиск, добавление и удаление ключа — могут быть выполнены без глобальных блокировок и даже в lock-free манере. Но стандартный std::map поддерживает ещё одну очень полезную абстракцию — итераторы. Возможно ли реализовать итерабельный lock-free map?
Ответ на этот вопрос — под катом.
Читать полностью »

в 23:53, , рубрики: c++, lock-free, Алгоритмы, многопоточность, Программирование, умные указатели

Разделяемые указатели и многопоточность. И снова о них, в который раз - 1

Глава из книги "Современное программирование на C++" называется "В сто первый раз об интеллектуальных указателях". Все бы ничего, но книга была издана в 2001 году, так стоит ли в очередной раз возвращаться к этой теме? Мне кажется что как раз сейчас и стоит. За эти пятнадцать лет поменялась сама точка зрения, тот угол под которым мы смотрим на проблему. В те далекие времена только-только вышла первая де-факто стандартная реализация — boost::shared_ptr<>, до этого каждый писал себе реализацию по потребности и как минимум представлял себе детали, сильные и слабые стороны своего кода. Все книги по C++ в то время обязательно описывали одну из вариаций умных указателей в мельчайших деталях.
Сейчас нам дан стандарт, и это хорошо. Но с другой стороны, уже не требуется понимать что там внутри, вместо этого достаточно три раза повторить мантру "используйте умные указатели везде где вы бы использовали обычные указатели", и это уже не так хорошо. Я подозреваю что далеко не все отдают себе отчет что данный стандарт — лишь один из возможных вариантов интерфейса, не говоря уже о разнице между реализациями различных вендоров. При выборе стандарта был сделан выбор между различными возможностями учитывающий разные факторы, но, оптимальный или нет, этот выбор очевидно не единственен.
А еще на stackoverflow например снова и снова задается вопрос — "потокобезопасны ли умные указатели из стандартной библиотеки?". Ответы даются обычно категоричные, но какие-то мало информативные. Если бы я например не знал о чем идет речь, то наверное бы не понял. И кстати, все сравнительно новые книги описывающие новый стандарт C++ этому вопросу тоже уделяют мало внимания.
Так давайте же попробуем сорвать покровы и разберемся с деталями.

Читать полностью »

в 5:55, , рубрики: c++, libcds, lock-free, map, tree, Алгоритмы, параллельное программирование, Программирование

Lock-free структуры данных. Concurrent maps: деревья - 1 Это последняя, на сегодняшний день, статья из цикла про внутреннее устройство конкурентных ассоциативных контейнеров. В предыдущих статьях рассматривались hash map, был построен алгоритм lock-free ordered list и контейнеры на его основе. За бортом остался один важный тип структур данных — деревья. Пришло время немного рассказать и о них.

Исследования, посвященные алгоритмам конкурентных деревьев, не требующих внешней синхронизации доступа к ним, начались довольно давно — в 70-х годах прошлого века, — и были инициированы развитием СУБД, поэтому касались в основном оптимизации страничных деревьев (B-tree и его модификации).

Развитие lock-free подхода в начале 2000-х не прошло мимо алгоритмов деревьев, но лишь недавно, в 2010-х годах, появилось множество действительно интересных работ по конкурентным деревьям. Алгоритмы деревьев довольно сложны, поэтому исследователям потребовалось время — порядка 10 лет — на их lock-free/non-blocking адаптацию. В данной статье мы рассмотрим самый простой случай — обычное бинарное дерево, даже не самобалансирующееся.
Читать полностью »

в 6:00, , рубрики: c++, libcds, lock-free, map, skip list, Алгоритмы, параллельное программирование, Программирование

Lock-free структуры данных. Concurrent maps: skip list - 1
В предыдущих статьях (раз, два) мы рассматривали классический hash map с хеш-таблицей и списком коллизий. Был построен lock-free ordered list, который послужил нам основой для lock-free hash map.
К сожалению, списки характеризуются линейной сложностью поиска O(N), где N — число элементов в списке, так что наш алгоритм lock-free ordered list сам по себе представляет небольшой интерес при больших N.
Или все же представляет?..
Читать полностью »

123
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js