Комментарии 52
В новом это в котором? Это не вот это?: /usr/include/c++/5.4.0/bits/shared_ptr_atomic.h
Но он к сожалкнию блокирующий, маленькое лукавство — atomic не обязательно подразумевает non blocking.
Если в системе много ядер, и куча потоков обращаются к атомарной переменной, то происходит блокировка на уровне инструкций процессора. Чуть более подробно в Современная операционная система: что надо знать разработчику
А в чём проблема с мьютексами? Почему нужно без них? Это требование ТЗ, или желание в многопоточном приложении иметь 100% неблокируемый код? Если второе, то это невозможно при разделяемых объектах, и скорее относится к религиозному чем к рациональному.
Постановку задачи я в самом начале описал, и проблема вполне реальная. Я уже измерял когда-то, каждая блокировка на мьютексе занимает 40 микросекунд. Вот в тех нечастых случаях когда это время критично и требуются неблокирующие алгоритмы.
Вот вы исследовали реализацию gcc, а что по поводу потокобезопасности разделенного указателя говорит стандарт?
И часто вы их расширяете? :)
Если ваши указатели действительно лучше стандартных указателей — напишите статью, интересно будет почитать. Только не забудьте привести доказательства преимуществ вашего решения по каким-нибудь метрикам (быстродействие, расход памяти, удобство использования, и т.д.).
Спасибо за настоятельную рекомендацию, только что вас заставляет думать что я ее не читал?
И, да, мне действительно было интересно и полезно, но уже довольно давно, поскольку книга вышла в 2012
Ну наверное вы в чем-то правы, но вообще пост не о lock-free — просто попытка разобраться из любопытства что именно мешает std::shared_ptr<> быть thread safe. Тема неблокирующих алгоритмов возникает фактически только потому что атомарные операции там уже присутствуют при работе со счетчиком.
К вопросу о thread-safe текущей реализации — думаю, в свете упомянутого, цена такого решения в виде громоподобно хрустящих compare_exchange под капотом не совсем соотносится с возможным выигрышем от всей этой кухни, поэтому комитету (и пользователям) было и будет проще пока что довольствоваться блокирующим доступом и специализациями std::atomic_xxx(shared_ptr<...>) или собственноручно добавленным мьютексом/спинлоком, благо в стандарте чётко оговаривается этот момент (мол, «шарьте, но не один указатель»).
compare_swap был и остается единственным условным атомарным оператором, без него вам ни одого нетривиального алгоритма не создать. Да, он сразу же переводит алгоритм в класс waiting, но как правило это не фатально, те же виртуальные функции вовсю используются в реализации.
Вообще, я препочитаю стандарты не обсуждать а понимать. В часности при создании std::shared_ptr был выбран очевидный баланс между тяжеловесностью реализации и универсальностью.
ошибся веткой
Я рад что вам хорошо, но радуетесь вы зря. Так или иначе, во всех языках есть подобные конструкции и под капотом они устроены примерно одинаково. Так что если вас полностью устраивает то что вы имеете, вам просто не нужно максимальной эффективности или вы просто не копали глубоко.
Правильно я понимаю, что проблема только в названии? Какой-нибудь Arc<Mutex<Box<_>>> будет (сильно) лучше?
Если что мне весьма нравится раст, но именно эта претензия не понятна.
Ничего не поделать, legacy всегда начинает убивать монстров. И это правильно.
Arc, Mutex и Box я могу использовать (или не использовать) в любом порядке с любой вложенностью.
Это удобно, не спорю.
Ну и не надо ждать 15 лет выхода очередного стандарта что бы что-то новое появилось в компиляторе.
У раста, конечно, частые релизы, но это ничего не гарантирует в плане добавления нужной фичи, если о ней не смогли договориться. А библиотеки и для плюсов имеются, так что не вижу никакой разницы.
М-да? А если будет придуман новый алгоритм, лучший во всех отношениях, и в расте он не появится? Это хорошо или наоборот плохо?
Да, нужно использовать atomic-операции для свапа: C++ 11 std::atomic_...<std::shared_ptr>
Вот так комбинация атомарного инкремента и атомарного декремента приводит к гонке между потоками и std::shared_ptr<> не является потокобезопасным, даже на уровне контрольного блока. Вот теперь действительно точка.
Когда говорят, что shared_ptr потокобезопасен на уровне контрольного блока, имеют в виду другой сценарий — а именно, два неразделяемых указателя, принадлежащие разным потокам, могут безопасно указывать на общий объект
Псевдо-код:
int main() {
uint32_t i = 10000;
while (i-- > 0) {
auto sp = std::make_shared<int>();
std::weak_ptr p = sp;
thread([p]{
if (auto sp = p.lock()) {
// pointer is valid, Cool, use sp
} else {
// pointer is already expired, ignore
}
}).detach();
}
return 0;
}
Пусть в разделяемой памяти находится некоторая информация упакованная в структуру и доступная через указатель. Есть один или множество независимых потоков, которые должны читать и использовать эти данные без модификации, как правило оказывается что для них критически важна скорость доступа. В то же время, пусть существует один или несколько потоков модифицирующих эти данные с нарушением целостности, на практике обычно оказывается что модификации случаются значительно реже и скорость доступа там не настолько важна.
…
Однако же я, прослышав что std::shared_ptr дает потокобезопасный доступ к контрольному блоку (и не очень понимая что это значит), а так же что операции над ним реализованы lock-free, хочу предложить свое изящное решение:
далее идет пример, того как делать не надо, а, как сказали выше, надо было просто дальше прочитать документацию. Хорошо, но как решить задачу без дополнительных финтов с блокировками?
Заметим, что читающий поток может пропустить часть данных, тогда это можно сделать, используя weak_ptr (считаем, что писатели могут синхронизироваться отдельно, тут задержка не важна). При этом, я считаю, что существует неблокирующий способ передачи этого самого weak_ptr в читающий поток.
Если же смотреть только на код примера, то то можно подумать, что речь идёт о том, что читающий поток живет все время и только и делает, что пытается прочитать данные, которые обновляются, но нечасто, и при этом все равно может пропустить часть данных. На мой взгляд тут проблема поважнее, и она не в деталях чтения памяти, а в подходе в целом. Это либо неэффективно, либо читающий поток захлебнется.
Вы не показали неблокирующего способа передачи изменяемого weak_ptr в поток.
Естественно я рассматривал случай weak_ptr, в пост добавлять не стал чтобы не загромождать ненужными деталями. Валится точно так же, и механизм тот же, даже lock() не требуется. Вообще-то могли бы и проверить перед тем как постить.
void read_data() {
for(;;)
std::weak_ptr<int> sp=data;
}
int main()
{
std::thread(read_data).detach();
for(;;)
data=std::make_shared<int>(0);
return 0;
}All member functions (including copy constructor and copy assignment) can be called by multiple threads on different instances of shared_ptr without additional synchronization even if these instances are copies and share ownership of the same object. If multiple threads of execution access the same shared_ptr without synchronization and any of those accesses uses a non-const member function of shared_ptr then a data race will occur; the shared_ptr overloads of atomic functions can be used to prevent the data race.http://en.cppreference.com/w/cpp/memory/shared_ptr
Как передать в другой тред? — использовать другие неблокирующие структуры данных, например, попробовать неблокирующие очереди, но это пахнет тем же мьютексом на спин-локах. Хотя производительность надо мерить в конкретном случае.
При любых операциях с собственно указателем, например присвоении, мы должны атомарно проверять счетчик и одновременно изменять указатель на контрольный блок, что невозможно используя существующие атомарные примитивы.Похоже, что так, если только кто-нибудь не придумает какой-нибудь трюк вроде tagged pointer, еще одного уровня вложенности или еще чего.
На самом деле я был бы рад ошибиться, возможно есть что-то, что я не знаю или понимаю неправильно?А не посмотрите реализацию std::experimental::atomic_shared_ptr?
А не посмотрите реализацию std::experimental::atomic_shared_ptr?
Ну, если то что я вижу это апдейтнутая версия, то там ничего нового не добавлено, просто враппер вокруг стандартных std::atomic_… свободных функций. Пока больше похоже на заготовку на будущее.
boostcon/cppnow 2016/implementing_a_lock_free_atomic_shared_ptr.pdf
И там дальше по ссылке литературы www.1024cores.net differential-reference-counting
Ссылки интерсные, спасибо. Отпишусь когда прочитаю.
Разделяемые указатели и многопоточность. И снова о них, в который раз