pebal

A similar example is posted there, just read it. It's best to read about the problems of concurrent containers, because you clearly don't understand the topic.

From the document you linked:

  int lfstack_pop(_Atomic lfstack_t \*lfstack)
  {
      lfstack_t next;
      lfstack_t orig = atomic_load(lfstack);
      do 
      {
          if (orig.head == NULL)  // undefined behavior !!!
          {
              return -1;
          }
          next.head = orig.head->next;
      } while (!atomic_compare_exchange_weak(lfstack,&orig,next));
      free(orig.head);
      return 0;
  }

If the first thread is preempted before the if(...) is executed, and then the second thread executes the entire method, then you will use data after freeing when the first thread resumes. Consider why the boost container doesn't free memory.

In the link I pointed you have an example given and an explanation of why you need to have specific memory management for concurrent containers. It cannot be explained any clearer.

You need to implement some form of GC when you want to free memory in a lock-free container. Read the thread and the employee's statements from Intel: https://community.intel.com/t5/Intel-oneAPI-Threading-Buildi...

New processors use 56 bits of virtual address. It doesn't matter if you have that much memory, because addresses are virtual. Also, newer versions of Android do not allow the use of unused address bits.

Described algorithms ignore the ABA problem. The boost implementation avoids the ABA problem, but does not free up memory at all and stores pointers on 48 bits which is not enough on new architectures.

Show an implementation of a concurrent lock-free stack without delayed freeing.

I am writing about shared_ptr because C++ is one of a top language. Read about the ABA problem.

I see you just don't want to see the problem. Look at this document: https://www.open-std.org/jtc1/sc22/WG21/docs/papers/2014/n41...

Did you know that the counter is stored in a different place than the pointer? All current atomic<shared_ptr> implementations use a lock. Stack overflow is not unique to a shared_ptr, but GC pointers don't have this problem. The reference counting has advantages, but it cannot fully replace GC pointers.

Can't atomically assign a pointer and increment a counter, need to use a lock. If make a long list using shared_ptr will overflow the stack when the head destructor executes.

Reference counting has limitations. It does not release cyclic structures, not suitable for lock-free algorithms and may overflow the stack.

You can look at this one: https://github.com/pebal/sgcl

There are pauseless real-time GCs: https://github.com/pebal/sgcl

SGCL never stops the threads.

You can watch Herb Sutter talk about deferred_ptr: https://youtu.be/JfmTagWcqoE

Mutators are threads that allocate memory and manipulate pointers, they can work completely independently of the GC. A mutator needs only to tag an object when copies or moves a pointer to this object. The GC detects this tag and marks the object as alive. Here is a working implementation for C++: https://github.com/pebal/sgcl

By analyzing mutators activity. Only the compacting GCs have to stop the world.

You can have GC engine without stopping the world. Completely pauseless.

- Some graph structures. The shared_ptr does not release circular data structures and has a lot of memory overhead.

- Memory managing of concurrent containers. Lock-free algorithms requires GC or the hazard pointers and these are basically based on GC.

- You often need the GC engine when you implementing or integrating another language.

It is not a solution for all cases.

GC can be faster and allocate less memory.

tracked_ptr: 279.95ms (151MB)

shared_ptr: 1035.07ms (480MB)

source: https://godbolt.org/z/jP7ohPehY

Disruption is a lower cost than the cost of executing the destructor by the mutator.

SGCL executes the destructors in a separate thread, so there is no cost to the mutator.

The intention of creating this project was the opposite. You only use the tracked pointer when it is beneficial.

This introduces the tracked smart pointer. This pointer has less overhead than shared_ptr and releases circular data structures.

Version 3 is more liberal.

Herb Sutter pointed out the need to add a tracked pointer to C++. He proposed the concept of deferred_ptr a few years ago. I implemented the tracked_ptr concept with one tracked heap. Advantages: - Thread safe - Does not use reference counters - Easy to use like shared_ptr - Less memory overhead than shared_ptr - Faster than shared_ptr in many scenarios - Automatic roots registration - Never stop the world - Cyclic data structures friendly - CoW friendly - Executing destructors in a separate thread - Atomic pointers always lock-free - Only one header file

Here is a working implementation: https://github.com/pebal/sgcl

The hazard pointer is basically a proposal to implement GC to solve one implementing problem in C++26.

> See also this answer: > https://stackoverflow.com/a/48046118/1593077 > to the question of why C++ doesn't have a garbage collector.

The shared_ptr is an optional garbage collection based on reference counting. Slow, leaky, deterministic (that's an advantage and a disadvantage). C++ needs optional garbage collection if needs shared_ptr.