c++ - Atomic shared_ptr for lock-free singly linked list -

i'm wondering if possible create lock-free, thread-safe shared pointer of "common" architectures, x64 or armv7 / armv8.

in talk lock-free programming @ cppcon2014, herb sutter presented (partial) implementation of lock-free singly linked list. implementation looks quite simple, relies on atomic shared_ptr implementation doesn't exist in standard library yet or on using specialized std::atomic... functions. important single push/pop calls potentially invoke multiple atomic loads/stores , compare_exchange operations.

the problem see (and think of questions in talk went same direction) actual lock-free data structure, atomic operations have lock-free themselves. don't know of standard library implementation std::atomic... functions lock-free , - @ least short google / search - didn't find suggestion of how implement lock-free specialization std::atomic<std::shared_ptr>.

now before i'm wasting time on wanted ask:

• do know, if possible write lockfree, atomic shared pointer @ all?
• are there implementations i've overlooked , - ideally - compatible expect std::atomic<std::shared_ptr>? mentioned queue require cas-operation.
• if there no way implement on current architectures, see other benefit in herb's implementation compared "normal" linked list protected lock?

---

for reference, here code herb sutter (might contain typos me):

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)) { ; }     } }; 

note, in implementation, single instances of shared_ptr can accessed / modified multiple different threads. can read/copied, reset , deleted (as part of node). not whether multiple different shared_ptr objects (that manage same object) can used multiple threads without race condition - true current implementations , required standard - concurrent access single pointer instance, - standard shared pointers - no more threadsafe same operations on raw pointers be.

---

to explain motivation:
academic question. i've no intention of implementing own lock free list in production code, find topic interesting , @ first glance, herb's presentation seemed introduction. however, while thinking this question , @sehe's comment on answer, remembered talk, had @ , realized doesn't make sense call herb's implementation lock-free, if it's primitive operations require locks (which do). wondering, whether limitation of current implementations or fundamental flaw in design.

i'm adding answer since it's long fit in comment:

something consider. lock-free shared_ptr not needed implement lock-free/wait-free data structures.

the reason sutter uses shared_ptr in presentation because complicated part of writing lock-free data structures not synchronization, memory reclamation: cannot delete nodes while they're potentially accessed other threads, have leak them , reclaim later. lock-free shared_ptr implementation provides "free" memory reclamation , makes examples of lock-free code palatable, in context of time-limited presentation.

of course, having lock-free atomic_shared_ptr part of standard huge help. it's not way of doing memory reclamation lock-free data structures, there's naive implementation of maintaining list of nodes deleted @ quiescent points in execution (works in low-contention scenarios only), hazard pointers, roll-your-own atomic reference counting using split counts.

as performance, @mksteve correct, lock-free code in not guaranteed outperform lock-based alternatives unless maybe runs on highly parallel system offering true concurrency. it's goal enable maximum concurrency , because of typically threads doing less waiting @ the cost of performing more work.

ps if interests you, should consider taking @ c++ concurrency in action anthony williams. dedicates whole chapter writing lock-free/wait-free code, offers starting place, walking through implementations of lock-free stack , queue.