stos bez blokad

Question

ostatnia linia w funkcji push powoduje błąd nr. C2665

plik main.cpp

#include <iostream>
#include <thread>
//#include "lock_free_stack.h"
#include "shared_ptr_stack20.h"
//#include "hazard_pointers_stack.h"

using namespace std;

shared_ptr_stack20<int> temp;

void add_function() {
    for (int i = 0; i < 500000; i++) {
        temp.push(i);
    }
}

void pop_function() {
    for (int i = 0; i < 500000; i++) {
        temp.pop();
    }
}

int main()
{
    thread t1(add_function);
    thread t2(add_function);
    t1.join();
    t2.join();
    thread t3(pop_function);
    thread t4(pop_function);
    t3.join();
    t4.join();
    shared_ptr<int> t;
    if (!temp.pop())
        cout << "udalo_sie" << endl;
    else
        cout << "nie udalo sie" << endl;
}

plik shared_ptr_stack20.h

#pragma once
#include <atomic>
#include <memory>

template <typename T>
class shared_ptr_stack20 {
private:
	struct node {
		std::shared_ptr<T> data;
		std::atomic<std::shared_ptr<node>> next;
		node(const T& data_) :data(std::make_shared<T>(data_)) {
		}
	};
	std::atomic<std::shared_ptr<node>> head;
public:
	std::shared_ptr<T> pop() {
		std::shared_ptr<node> old_head = head.load();
		while (old_head && !head.compare_exchange_weak(old_head, old_head->next.load()));
		if (old_head) {
			old_head->next.store(std::shared_ptr<node>());
			return old_head->data;
		}
		return std::shared_ptr<T>();
	}
	void push(const T& value) {
		std::shared_ptr<node> temp = std::make_shared<node>(value);
		temp->next = head.load();
		while (!head.compare_exchange_weak(temp->next, temp);
	}
	~shared_ptr_stack20() {
		while (pop());
	}
};

 

Comments

Czemu w ogóle w funkncji push jest pętla, to powinno być O(n)?

---

Ta pętla to element synchronizacji.

---

@Ru­finB, u mnie w Linuksie jest następujący błąd:

In file included from main.c++:4:
In file included from ./shared_ptr_stack20.h:2:
/usr/lib/gcc/x86_64-pc-linux-gnu/12.2.0/include/g++-v12/atomic:211:7: error: static assertion failed due to requirement '__is_trivially_copyable(std::shared_ptr<shared_ptr_stack20<int>::node>)': std::atomic requires a trivially copyable type
      static_assert(__is_trivially_copyable(_Tp),
      ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./shared_ptr_stack20.h:14:40: note: in instantiation of template class 'std::atomic<std::shared_ptr<shared_ptr_stack20<int>::node>>' requested here
    std::atomic<std::shared_ptr<node>> head;
                                       ^
main.c++:9:25: note: in instantiation of template class 'shared_ptr_stack20<int>' requested here
shared_ptr_stack20<int> temp;
                        ^
1 error generated.

Może to coś wyjaśni. std::atomic wymaga trywialnie kopiowalnego typu. Nie wiem, czy na Windowsie nie jest tak samo.

---

Ale chyba node jest trywialnie kopiowanym trybem skoro shared_ptr<> i atomic<shared_ptr<>> są trywialnie kopiowane

---

taki podobny kod kompiluje się bez problemu jeżeli to pomoże 

#pragma once
#include <atomic>
#include <memory>

template <typename T>
class shared_ptr_stack {
private:
	struct node {
		std::shared_ptr<T> data;
		std::shared_ptr<node> next;
		node(const T& value):data(std::make_shared<T>(value)) {
		}
	};
	std::shared_ptr<node> head;

public:
std::shared_ptr<T> pop() {
		std::shared_ptr<node> old_head = std::atomic_load(&head);
		while (old_head && !std::atomic_compare_exchange_weak(&head, &old_head, std::atomic_load(&old_head->next)));
		if (old_head) {
			std::atomic_store(&old_head->next,std::shared_ptr<node>());
			return old_head->data;
		}
		return std::shared_ptr<T>();
	}

void push(const T& _data) {
	std::shared_ptr<node> const new_node = std::make_shared<node>(_data);
	new_node->next = std::atomic_load(&head);
	while (!std::atomic_compare_exchange_weak(&head, &new_node->next, new_node));
}
~shared_ptr_stack() {
	while (pop());
}
};

tylko że standard c++20 wyklucza użycie go

---

A, faktycznie nie włączyłem standardu 20. Teraz jest konkretniejszy komunikat błędu:

In file included from main.c++:4:
./shared_ptr_stack20.h:28:22: error: no matching member function for call to 'compare_exchange_weak'
        while (!head.compare_exchange_weak(temp->next, temp));
                ~~~~~^~~~~~~~~~~~~~~~~~~~~
main.c++:13:14: note: in instantiation of member function 'shared_ptr_stack20<int>::push' requested here
        temp.push(i);
             ^
/usr/lib/gcc/x86_64-pc-linux-gnu/12.2.0/include/g++-v12/bits/shared_ptr_atomic.h:648:7: note: candidate function not viable: no known conversion from 'std::atomic<std::shared_ptr<node>>' to 'std::atomic<std::shared_ptr<shared_ptr_stack20<int>::node>>::value_type &' (aka 'shared_ptr<shared_ptr_stack20<int>::node> &') for 1st argument
      compare_exchange_weak(value_type& __expected, value_type __desired,
      ^
/usr/lib/gcc/x86_64-pc-linux-gnu/12.2.0/include/g++-v12/bits/shared_ptr_atomic.h:640:7: note: candidate function not viable: requires 4 arguments, but 2 were provided
      compare_exchange_weak(value_type& __expected, value_type __desired,
      ^
1 error generated.

 

Answer 1

Nawiasu ) brakuje.

Comments

przy próbach naprawy zapomniałem dodać ale nawet po dodaniu powoduje błąd: C2665   "std::atomic<std::shared_ptr<shared_ptr_stack20<int>::node>>::compare_exchange_weak": żadne z przeciążeń 2 nie może konwertować wszystkich typów argumentów

---

Nie rozumiem, po co w ogóle bawisz się tutaj z tymi inteligentnymi wskaźnikami? To jakiś odgórny wymóg.

---

Taki sposób poznałem w książce i chciałem go zaimplementować sam, sprawdziłem z książką i jest identycznie a dalej się nie kompiluje, czy radzisz abym odpuścił te sposoby, w końcu są inne

---

Jeśli robisz to w celach doświadczalnych, to oczywiście nie ma tu nic złego. Ja po prostu nie widzę tu korzyści z użycia  shared_ptr. Wadą jest to, że taki stos wymusza trzymanie obiektu oddzielnie na stercie, a nie jako część węzła.

Dodatkowo, jeśli dobrze rozumiem to, co czytam w dokumentacji, specjalizacja std::atomic dla std::shared_ptr używa muteksów, więc nie taki bez blokad jest ten stos.

---

shared_ptr w tym kontekście ma zalety (no i wady także).

Jeśli nie zwracać shared_ptr, to można w pop(...) zwrócić wartość przez referencję przekazaną do wywołania (czyli stack.pop(value) ). W konsekwencji będzie wykonywana alokacja danych typu z argumentu value, będzie problem dla konstruktorów parametryzowalnych tego typu (bo nie ma jak przekazać argumentów lub nie wiadomo jakie) no i typ danych powinien być przypisywalny. A bywa że nie jest.

Można zwrócić przez wartość. No ale wtedy kupujesz problem konstruktora przenoszącego/kopiującego no i zabezpieczenie przed rzucanymi ew. wyjątkami. Wydajność także może być dyskusyjna.

Jeśli przez shared_ptr, to będzie bezpieczne bo obiekt oryginalny "nie jest dotykany", licznik referencji zabezpieczy problem ew. braku pamięci w wywołującym kodzie i kończonym w pop(), problem zwijania stosu obsłużony zadowalająco. Minus to wydajność dla prostych typów. Żonglowanie pamięcią/stosem/stertą w trakcie kreacji shared_ptr, dla POD'a, może być dużym narzutem na wydajność.

Produkcyjnie w takich przypadkach robiłem tych kilka sposobów i dawałem wybór dla konkretnego zastosowania. Ktoś kto programuje świadomie, samy wybierał "styl API w zależności od przypadku i potrzeb" :)

A co do atomowości shared_ptr: https://eel.is/c++draft/util.smartptr.atomic

---

już  działa musiałem zmienić parę linii

Dzięki za pomoc