Atomic shared_ptr для одиночного списка без блокировки

Мне интересно, можно ли создать безопасный, потокобезопасный общий указатель для любой из "общих" архитектур, таких как x64 или ARMv7/ARMv8.

Говоря о программировании без блокировки на cppcon2014, Херб Саттер представил (частичную) реализацию блокировки без привязки к списку, Реализация выглядит довольно просто, но она опирается на атомную реализацию shared_ptr, которая еще не существует в стандартной библиотеке, или на использование специализированных функций std::atomic.... Это особенно важно, поскольку одиночные push/pop-вызовы потенциально вызывают множественные атомные нагрузки/хранилища и операции compare_exchange.

Проблема, которую я вижу (и я думаю, что некоторые из вопросов в разговоре идут в одном направлении) заключается в том, что для того, чтобы это была фактическая структура данных без блокировки, эти атомные операции должны были бы быть заблокированы сами. Я не знаю никакой стандартной реализации библиотеки для std::atomic... функций, которые не блокируются и, по крайней мере, с коротким поиском google/SO, я также не нашел предложения о том, как реализовать специальную функцию блокировки для std::atomic<std::shared_ptr>.

Теперь, прежде чем я трачу свое время на это, я хотел спросить:

Знаете ли вы, если можно вообще написать бездепозитный, атомный общий указатель?
Есть ли уже какие-либо реализации, которые я забыл и, в идеале, даже совместимы с тем, что вы ожидаете от std::atomic<std::shared_ptr>? Для указанной очереди особенно требуется CAS -операция.
Если нет способа реализовать это на существующих архитектурах, вы видите какое-либо другое преимущество в реализации Herb по сравнению с "нормальным" связанным списком, который защищен блокировкой?

Для справки, вот код от Herb Sutter (может содержать опечатки от меня):

template<class T> 
class slist {
    struct Node { T t;  std::shared_ptr<Node> next; };
    std::atomic<std::shared_ptr<Node>> head;        
public:
    class reference{
        std::shared_ptr<Node> p;
    public:
        reference(std::shared_ptr<Node> p_){}
        T& operator*(){ return p->t; }
        T* operator->(){ return &p->t; }
    };
    auto find(T t) const {
        auto p = head.load();
        while (p && p-> != t) {
            p = p - next;
        }
        return reference(move(p));
    }
    void push_front(T t) {
        auto p = std::make_shared<Node>();
        p->t = t;
        p->next = head;
        while (!head.compare_exchange_weak(p->next, p)) {}
    }
    void pop_front() {
        auto p = head.load();
        while (p && !head.compare_exchange_weak(p, p - next)) { ; }
    }
};

Обратите внимание, что в этой реализации отдельные экземпляры shared_ptr могут быть доступны/изменены несколькими различными потоками. Его можно прочитать/скопировать, reset и даже удалить (как часть node). Таким образом, это не связано с тем, что несколько разных объектов shared_ptr (которые управляют одним и тем же объектом) могут использоваться несколькими потоками без условия гонки - это уже верно для текущих реализаций и требуется стандартом, но речь идет о одновременном доступе к один экземпляр указателя, который является - для стандартных общих указателей - не более поточным, чем те же операции над необработанными указателями.

Чтобы объяснить мою мотивацию:
Это в основном академический вопрос. Я не собираюсь реализовывать свой собственный список блокировки в производственном коде, но я нахожу тему интересной и на первый взгляд, презентация Herb показалась хорошим введением. Однако, думая о этом вопросе и @sehe комментировать мой ответ, я вспомнил этот разговор, посмотрел на него и понял, что не имеет смысла вызовите реализацию Herb lock-free, если для примитивных операций требуются блокировки (которые они в настоящее время делают). Поэтому мне было интересно, является ли это лишь ограничением существующих реализаций или фундаментальным недостатком дизайна.

Ответы

Ответ 1

Я добавляю это как ответ, так как он слишком длинный, чтобы вписаться в комментарий:

Что-то, что нужно учитывать. Блокировать shared_ptr не требуется, чтобы реализовать блокировки данных без блокировки.

Причина, по которой Sutter использует shared_ptr в своей презентации, состоит в том, что самая сложная часть написания незакрепленных структур данных - это не синхронизация, а исправление памяти: мы не можем удалять узлы, пока они потенциально доступны другим потокам, поэтому мы должны пропустить их и вернуть позже. Непрерывная реализация shared_ptr по существу обеспечивает "бесплатную" рекультивацию памяти и делает примеры кода без блокировки приемлемыми, особенно в контексте ограниченной по времени презентации.

Конечно, наличие блокировки atom_shared_ptr как части Стандарта будет огромной помощью. Но это не единственный способ сделать восстановление памяти для незакрепленных структур данных, но наивная реализация поддержки списка узлов, которые нужно удалить в момент покоя (работает только в сценариях с низкой конкуренцией), указатели опасности, ваш собственный подсчет ссылок на атом с использованием расчётов.

Что касается производительности, @mksteve является правильным, код без блокировки не гарантирует превышения альтернатив на основе блокировок, если, возможно, он работает на высокопараллельной системе, предлагающей true concurrency. Цель состоит в том, чтобы включить максимум concurrency, и из-за этого мы обычно получаем потоки, которые меньше ожидают затрат на выполнение большей работы.

PS Если это вас интересует, вы должны рассмотреть возможность взглянуть на С++ concurrency в действии Энтони Уильямса. Он посвящает целую главу написанию кода без блокировки/безжизненного кода, который предлагает хорошее начальное место, проходя через реализации стека блокировки и очереди.

Ответ 2

Знаете ли вы, если можно написать lockfree, атомный общий указатель на всех?
Есть ли уже какие-либо реализации, которые я упускают из виду и - идеально - даже совместимы с тем, что вы ожидать от std:: atomic?

Я думаю, что std:: atomic _... предлагает форму реализации, где slist будет выполнять специальные атомарные запросы на shared_ptr. Проблема с этим разделяется на два класса (std:: atomic и std:: shared_ptr) состоит в том, что каждый из них имеет ограничения, которые необходимо соблюдать для того, чтобы функционировать. Разделение классов делает невозможным знание общих конфликтов.

В пределах slist, который знает оба элемента, он может помочь в ситуации, и, вероятно, будут работать функции atom_....

Если нет способа реализовать это на существующих архитектурах, см. любое другое преимущество в реализации Herb по сравнению с "нормальным" связанный список, который защищен блокировкой?

Из Википедия: неблокирующий алгоритм цель свободного от блокировки природы - гарантировать определенный прогресс выполняется по меньшей мере одним потоком.

Это не дает гарантии лучшей производительности, чем блокированная реализация, но дает гарантию того, что взаимоблокировки не произойдет.

Представьте, что T требуется блокировка для выполнения копии, это может также быть связано с некоторыми операциями за пределами списка. Тогда возможен тупик, если он будет принадлежать, и была вызвана реализация слайда на основе блокировки.

Я думаю, что CAS реализован в std::compare_exchange_weak, поэтому будет независимым от реализации.

Существующие алгоритмы блокировки для сложных структур (например, вектор, карта) имеют тенденцию быть значительно менее эффективными, чем блокирующие алгоритмы, Dr Dobbs: блокированные структуры данных, но предлагаемое преимущество (улучшенная производительность потоков) значительно улучшит производительность компьютеров, которые, как правило, имеют большое количество незанятых процессоров.

Дальнейшие исследования алгоритмов могут идентифицировать новые инструкции, которые могут быть реализованы в будущих процессорах, чтобы обеспечить нам безжизненную производительность и более эффективное использование вычислительных ресурсов.

Ответ 3

Можно написать незашифрованный общий ptr, поскольку единственное, что нужно изменить, - это счет. Сам ptr только копируется, поэтому никакой особой осторожности здесь не требуется. При удалении это должен быть последний экземпляр, поэтому в других потоках нет других копий, поэтому никто не будет увеличиваться в одно и то же время.
Но, сказав это, std:: atomic > wuold будет очень специализированной вещью, поскольку это не совсем примитивный тип.

Я видел несколько реализаций списков без блокировки, но ни один из них не имел общих указателей. Эти контейнеры обычно имеют особую цель, и поэтому существует соглашение об их использовании (когда/кто создает/удаляет), поэтому использование общих указателей не требуется.
Кроме того, общие указатели вводят накладные расходы, что противоречит нашим задачам с низкой задержкой, которые в первую очередь привели нас к незащищенному домену.

Итак, вернемся к вашему вопросу - я думаю, что это возможно, но я не понимаю, почему это так. Если вам действительно нужно что-то подобное, переменная-член refCount будет лучше.

Я не вижу особых преимуществ в специфической реализации Herb, возможно, кроме академической, но списки без блокировки имеют очевидную мотивацию не иметь блокировки. Они часто служат в качестве очередей или просто для обмена коллекцией узлов между потоками, которые имеют аллергию на блокировки.
Может быть, мы должны спросить Херба.. Херб? вы слушаете?

EDIT: Следуя всем приведенным ниже комментариям, я внедрил список без привязки к одиночному соединению. Список довольно сложный, чтобы предотвратить удаление общих ptrs во время их доступа. Здесь слишком много сообщений, но вот основные идеи:
- Основная идея заключается в том, чтобы удалить удаленные записи в отдельном месте - сборщик мусора - чтобы сделать их недоступными для последующих действий.
- Счетчик атомов увеличивается при входе в каждую функцию (push_front, pop_front и front) и автоматически уменьшается при выходе. При уменьшении до нуля счетчик версий увеличивается. Все в одной атомной инструкции.
- Когда необходимо удалить общие ptrs, в pop_front он помещается в GC. Там есть GC для номера версии. GC реализуется с использованием более простого списка без блокировки, который может только push_front или pop_all. Я создал круговой буфер из 256 GC, но может быть использована и другая схема.
- GC версии сбрасывается при добавлении версии, а затем общие птры удаляют держатели.
Итак, если вы вызываете pop_front, но ничего не запускаете, количество ссылок увеличивается до 1, передний общий ptr помещается в GC [0], ref возвращается к нулю, а версия - к 1, GC [0] очищается - это уменьшает общий ptr, который мы выскочили и, возможно, удалил объект, которому он владеет.

Теперь откройте блокировку shared_ptr. Я считаю, что это выполнимо. Вот идеи, которые я думал:
- У вас может быть сортировка спина, используя низкие биты указателя на держатель, так что вы можете разыменовать его только после того, как вы заблокировали его. Вы можете использовать другой бит для inc/dec и т.д. Это намного лучше, чем блокировка всей вещи.
Проблема здесь в том, что сам общий ptr может быть удален, так что все, что содержит его, должно было бы обеспечить некоторую защиту извне, например, связанный список.
- У вас может быть центральный реестр общих указателей. Это не страдает от проблемы, описанной выше, но было бы сложно увеличить время от времени при отсутствии латентных шипов.

Подводя итог, я сейчас думаю, что вся эта идея спорна. Если вы найдете другой подход, который не страдает от больших проблем - мне будет очень интересно узнать об этом:)
Спасибо!