Распараллеливание выполнения без блокировок

Wound, Qraizer, косяк с утечкой всеж был.
И Киля, спасибо за наводку!

Я зачекал, изменил вот так:

template <typename T>
struct Node {
    std::shared_ptr<T> Data;
    Node* Next;
    Node(T const& iData):   Data(std::make_shared<T>(iData)) {
        std::cout << "Node start" << std:: endl;
    }
    ~Node() {
        std::cout << "Node stop" << std:: endl;
    }
};

Освобождений не было. Изменил код:

template <typename T>
class FreeStack {
        std::atomic<Node<T>*> Head;
    public:
        void Push(T const& iData) {
            Node<T>* const NewNode = new Node<T>(iData);
            NewNode->Next = Head.load();
            while (!Head.compare_exchange_weak(NewNode->Next, NewNode));
        }
        std::shared_ptr<T> Pop() {
            Node<T>* OldHead = Head.load();
            while (OldHead && !Head.compare_exchange_weak(OldHead, OldHead->Next));
            if (OldHead) {
                auto Ret = OldHead->Data;
                delete OldHead; // <---------------------- тут
                return Ret;
            } else
                return std::shared_ptr<T>();
        }
};

А вот теперь все ровно! Что выделяется, то потом и освобождается.

Добавлено 20.02.20, 18:43
Хотя, странно push() и pop() я взял из книжки чисто почти копипастой.
Неужели не проверяют, что пишут ...

Добавлено 20.02.20, 19:19
И кстати, да - вопрос к автору книжки, этому Уильямсу ... Если есть такой
жесткий косяк с утечкой памяти, то что остального полезного можно получить
из раздела о lock-free структурах, кроме как упоминания полезного метода
std::atomic::compare_exchange_weak?

И нахрена тогда std::shared_ptr раз память все равно течет? Вопросов больше чем ответов.
Может из стека снимать ноду нужно как-то иначе? А-ля в стиле std::move?

Скрытый текст

Цитата JoeUser @ 20.02.20, 17:06

А нафига? У меня же тривиальнейший случай.

Собственно, чтд - ты просто не читаешь, что тебе пишут "Нафига" и я, и Киля, и Qraizer объясняли уже несколько раз.
Да и "тривиальнейший случай", который разбирается тут уже пять страниц (три, если вычесть срач) это отдельный прикол. Сам-то не видишь тут противоречия?

Цитата JoeUser @ 21.02.20, 03:35

Может из стека снимать ноду нужно как-то иначе? А-ля в стиле std::move?

Нет. Все эти compare_exchange и прочие атомарные операции в силу своей природы работают только с выровненными данными, и размер этих данных у тебя не будет больше 8 байт, так что мувить атомарно у тебя получится только указатели. Возможно, это означает, что его можно заставить работать с каким-нибудь unique_ptr (без кастомного deleter-а, разумеется), но на практике я не слышал, чтобы так делали, поэтому просто работают с голыми указателями и обеспечивают невозможность их утечки исключительно внимательной медитацией над кодом.

Цитата JoeUser @ 20.02.20, 18:40

Освобождений не было. Изменил код:

Я если честно так и не увидел - где ты изменил код? У тебя как было AV, так оно и осталось ровно в том же месте.
Если первый поток успел вызвать Pop раньше, чем второй Push то во второй строке будет AV:

Node<T>* OldHead = Head.load();
            while (OldHead && !Head.compare_exchange_weak(OldHead, OldHead->Next)); //! <<<<< Тут бьудет Access Violation, конкретно на вот этой конструкции - OldHead->Next

Пропустил или забыл что ли?

На всякий случай просто приведу пример.
Ради понимания, попробуй создать консольное приложение и набери там, ну либо просто внимательно взгляни на этот код:

    template <typename T>
    struct Node {
        std::shared_ptr<T> Data;
        Node* Next;
        Node(T const& iData):   Data(std::make_shared<T>(iData)) {
            std::cout << "Node start" << std:: endl;
        }
        ~Node() {
            std::cout << "Node stop" << std:: endl;
        }
    };
 
int main()
{
     std::atomic<Node<T>*> Head;
     Node<T>* OldHead = Head.load();
 
     std::cout << OldHead->Next->Data; //! <<< Вот тут ошибка, и у тебя ровно такая же.
}

Цитата OpenGL @ 21.02.20, 06:06

Сам-то не видишь тут противоречия?

Противоречие одно - эти механизмы нечасто были использованы. А ведь кода совсем мало.
Поэтому и столько обсуждений. А не потому, что тут что-то из ряда вон громоздкое и
сложное. ИМХО.

А вообще по-моему у тебя тут есть риск вытащить один и тот же элемент дважды, если звёзды не сошлись, из-за aba проблемы. Да, вероятность мала, но тем не менее

Цитата Qraizer @ 20.02.20, 12:49

Цитата Pavia @ 19.02.20, 22:35

По поводу QT проблемы с глобальными сиглтонами из-за параллельной сборки он в исполняемые файлы пихает несколько штук. Пришлось через разделяемую память делать свой синглтон и на основе него мьютексы для блокировок.

Цитата Pavia @ 20.02.20, 01:22

Я вам рассказал про подводные камни. А что с ними делать это вам решать.

Этих фраз даже я не понял. Набор слов. Pavia, попрошу быть конкретнее, чтобы тебя можно было понимать по-русски. Так что, увы, не рассказал.

Это отдельная тема для разговора. Одно описание проблемы займет несколько листов. Только потому что Вы не подготовлены, а терминология в данной области оставляет желать лучшего.И ещё столько же описание корня проблемы.

Тест я год назад делал вот выложен:
https://www.programmersforum.ru/showthread.php?t=328066

Сейчас я в командировке и сделать скриншоты с бинарником и отладчиком не получится... Судя по коду это вариант с 1 Юнитом. А так для полной демонстрации нужно сделать 2-х агентов для наглядности.

PS. Постараюсь на следующей неделе сделать.

Сообщение отредактировано: Pavia - 21.02.20, 10:17

Цитата Wound @ 21.02.20, 06:15

Ради понимания, попробуй создать консольное приложение и набери там, ну либо просто внимательно взгляни на этот код:

Ты привел дичь, которая не компилируется.

Я твой код немного исправил, чтобы был как-то похож на мой и чтобы компилировался и исполнялся:

#include <iostream>
#include <memory>
#include <atomic>
 
using namespace std;
 
template <typename T>
struct Node {
    std::shared_ptr<T> Data;
    Node* Next;
    Node(T const& iData):   Data(std::make_shared<T>(iData)) {
        std::cout << "Node start" << std:: endl;
    }
    ~Node() {
        std::cout << "Node stop" << std:: endl;
    }
};
 
int main() {
  std::atomic<Node<std::string>*> Head;
  Node<std::string>* OldHead = Head.load();
  if (OldHead) std::cout << OldHead->Next;  
}

Все работает.
А в моем коде есть строчка:

return OldHead ? OldHead->Data : std::shared_ptr<T>();

Т.е., как видишь, указатель сперва валидируется, и только если норм берется его значение поля OldHead->Data.
А это ты почему-то проигнорил

Хотя, все равно, код не одинаковый. Мою прогу сколько раз не запускал - сбоя ни разу (вообще ни разу) не было.
Буду разбираться, где же и почему "мне повезло".

Добавлено 22.02.20, 08:53

Цитата OpenGL @ 21.02.20, 06:22

если звёзды не сошлись, из-за aba проблемы

Можно подробнее, а что это за "aba проблема"?

Добавлено 22.02.20, 09:10
Немного исправил код Run()

 void Run() {
  Node<std::string>* Tmp = Stack.Head.load();
  std::cout << Tmp << std::endl;

И прогнал под отладкой - Tmp получает nullptr
А как я уже писал выше, у меня Pop() работает с проверкой

 return OldHead ? OldHead->Data : std::shared_ptr<T>();

Так что программа не валится. Но "да", с явной инициализацией вершины будет точнее.

Добавлено 22.02.20, 09:22

Цитата Qraizer @ 20.02.20, 18:27

Ещё мне не нравится, что твой Pop() может вернуть ошибку посредством пустого shared_ptr. Придётся везде проверки пихать. Но с фрилуком иначе, боюсь, и не получится.

Вечером попробую тест поставить - вообще ничего не ложить в стек, а в цикле пробовать все время брать из пустого. Ну и запущу под Линухом под Valgrind'ом.

Цитата Wound @ 21.02.20, 06:15

Если первый поток успел вызвать Pop раньше, чем второй Push то во второй строке будет AV:

Похоже что оч редко (именно в момент переключения потоков), но потенциально может.
Буду это изучать - по идее должно как-то помочь в данной ситуации

Простая задача, он говорил А ведь ты ещё даже не учитываешь барьеры, не слышал про ABA (которая, кстати, может и не проявится - хз, думать надо) и вообще у тебя пока ещё один читатель и один писатель, что жизнь сильно упрощает

OpenGL, прочёл про ABA - это ясно не мой случай. В этой проблеме предполагается возможность прерывания и продолжения операций. У меня же операции атомарные. И я манипулирую адресами, а одинаковое значение указателя не может ссылаться на разные ячейки памяти.

Цитата JoeUser @ 22.02.20, 11:18

В этой проблеме предполагается возможность прерывания и продолжения операций.

Нет, не предполагается. ABA это про ситуацию, когда менеджер памяти выдал указатель на ячейку памяти, которая юзалась ранее, но уже была освобождена. Тогда у тебя появляется шанс на успешный compare_exchange в то время, когда он не должен быть таковым.
И кстати, я только сейчас заметил, что добавление второго читателя или писателя у тебя всё сломает даже безотносительно ABA.

Цитата JoeUser @ 21.02.20, 03:35

И нахрена тогда std::shared_ptr раз память все равно течет? Вопросов больше чем ответов.

Потому что у тебя не shared_ptr, а указатель на shared_ptr. Точнее, на Node, внутри которого shared_ptr, неважно.

Добавлено 22.02.20, 13:27

Цитата Pavia @ 21.02.20, 09:33

Это отдельная тема для разговора. Одно описание проблемы займет несколько листов.

Зачем оно нам? Тебе было сложно написать два предложения по-русски, а не тарабарски?

Цитата JoeUser @ 22.02.20, 08:38

Ты привел дичь, которая не компилируется.

Это не дичь, а псевдокод, чтоб показать проблему.

Цитата JoeUser @ 22.02.20, 08:38

Все работает.
А в моем коде есть строчка:

И судя по всему ты не увидел в этом коде проблемы. И это пичально.
Не знаю как тебе еще пояснить, тебе и Qraizer и я писал. Но ты не увидел проблемы. Ты вообще в дебаге наверно запускал, вот у тебя и работало все, или так звезды сошлись, что неинициализированный указатель у тебя оказался 0. Короче ладно, пофигу. Когда AV выхватишь в проде, тогда до тебя дойдет в чем у тебя ошибка заключается, а ты ее выхватишь в любом случае рано или поздно.

Цитата JoeUser @ 22.02.20, 08:38

Т.е., как видишь, указатель сперва валидируется, и только если норм берется его значение поля OldHead->Data.
А это ты почему-то проигнорил

На что валидируется? На то что если он не нулевой, то вызвать член через указатель? А расскажи ка, когда он у тебя будет нулевым? В каком месте он у тебя нулевой? Там мусор будет содержатся, и соответственно твоя валидация сработает не так, как ты ожидаешь.

Цитата JoeUser @ 22.02.20, 08:38

Так что программа не валится. Но "да", с явной инициализацией вершины будет точнее.

То что она у тебя не валиться еще ни о чем совершенно не говорит.

Цитата Wound @ 22.02.20, 21:38

Ты вообще в дебаге наверно запускал, вот у тебя и работало все, или так звезды сошлись, что неинициализированный указатель у тебя оказался 0.

Скорее всего так сошлись звезды Но это полный песец, и объяснения у меня этому нет.
Да, я с тобой сейчас согласен. Да и ранее, в принципе, с твоей наводки увидел не инициализируемое
поле класса. Но ведь работало - и это меня смущало, что программа должна падать, а она никак и не
падает! И вот утром пришла мысль поэксперементировать с режимами сборки, и вот какая любопытная
табличка у меня вышла:

Сборка	с++11	с++14	с++17
MSVS 2017 Debug x32	-	-	+
MSVS 2017 Release x32	-	-	-
MinGW 7.3.0 Debug x32	-	-	-
MinGW 7.3.0 Release x32	-	-	-

где вылет '-', а норм работа '+'

А у меня как раз все сборки и тесты были под MSVS 2017 Debug x32 с++17

Да, сейчас изменил - добавил инициализацию nullptr

template <typename T>
class FreeStack {
    std::atomic<Node<T>*> Head = nullptr; // <---------------- вот тут
  public:

И во всех вариантах работа стала нормальной. Получается с MSVS 2017 Debug x32 с++17
какая-то мистика.