Hacker News Reader

Comment by CyberDildonics | Hacker News Reader

Can't atomically assign a pointer and increment a counter

You can do that in multiple ways.

First you can use the extra bits of a pointer for a counter to fit it all into 64 bits.

Second, you can use a 128 bit compare and swap which has been supported by CPUs for about 20 years now.

Third, you can not use pointers and use indices of whatever bit resolution you want, using the extra bits for a counter.

Finally, how does a garbage collector change this ?

If make a long list using shared_ptr will overflow the stack when the head destructor executes.

If we set aside for a second the insanity in making a linked list where every pointer destruction calls the next pointer in the list's destructor, how is this unique to a shared_ptr ?

View on HN

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.

I think you're confusing shared_ptr with reference counting as a technique in general. Can you answer the questions I have above without talking about shared_ptr?

Stack overflow is not unique to a shared_ptr, but GC pointers don't have this problem

No one should ever have this problem. It is a ridiculous way to make a linked list in the first place.

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...

You're still trying to compare one basic smart pointer implementation to garbage collection in general.

You told me something was impossible to do without garbage collection and I explained three different ways that I've already done it, then you just keep trying to talk about something that was never up for discussion in the first place. You hallucinated shared_ptr into the conversation from nowhere.

Without talking about smart pointers, what am I missing from the list above? Why do some lock free algorithms need garbage collection?

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

I'm talking about C++ too, but I write lock free algorithms and data structures all the time and they have nothing to do with with smart pointers in any way.

Why don't you answer my questions above? They confront the ABA problem directly since I explained three ways to keep counts paired with pointers or indices. What can't be done without a garbage collector? Why do you keep giving vague recommendations to read about general topics? Give me a specific deeply technical answer if you can.

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

I think you're mixing up allocation with a data structure. There are lots of implementations of lock free lists and stacks in C++ out there. One simple implementation is an array where every index holds the next index. A current variable holds the next index to deal with and a version number.

When you want to allocate an index you check the current index and version, and replace it with the index points to if the version is the same. Freeing is the reverse since you have an index to give the list.

These indices are used to coordinate to a second array where you can store whatever data you want.

Here are some other techniques.

https://people.csail.mit.edu/shanir/publications/Lock_Free.p... https://www.boost.org/doc/libs/1_55_0/boost/lockfree/stack.h... https://lumian2015.github.io/lockFreeProgramming/lock-free-s...

Still, I'm not sure what garbage collection changes about these techniques. Lock free lists have been studied for a long time, they have nothing to do with memory allocation.

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.

Once again, you haven't mentioned at all how garbage collection changes anything, even though that was what you originally said and never backed up with anything.

Described algorithms ignore the ABA problem.

I literally wrote a method for doing that, an index with a version that can be checked to make sure nothing changed.

Also if you're going to say that heavily tested implementations ignore the ABA problem you need to explain why you think that or why you think they won't work and again, why garbage collection changes anything.

stores pointers on 48 bits which is not enough on new architectures.

48 bits is the size of the memory controller on modern CPUs and exceeding that would need over 281 terabytes of memory.

Again, the original question is what lock free algorithm can be done with garbage collection that can't be done without it?

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.

You need to implement some form of GC when you want to free memory in a lock-free container.

This is again, your assertion, it isn't evidence or an explanation of any kind, you just keep saying the same thing. The link you have is people discussing a bunch of surrounding issues.

Fundamentally, allocation of arbitrary memory just doesn't have to be ingrained in the lock free data structure. As soon as you can deal with 64 bits at a time, you can store pointers. There are lock free heap allocators and lock free block allocators that can be combined with whatever you are using to deal lock free with integers/pointers.

Freeing memory is going to be a matter of ownership. If you pop a pointer, that thread should own it. Not only that, but a pointer combined with a reference count can always be used if necessary and again, 128 bit compare and swap has been around for 20 years.

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.

I've given you a lot of detailed explanations you haven't actually explained anything.

I didn't see what you're talking about in the 15 year old message board discussion and I think if there was something specific and clear you would have copied and pasted it.

I also think that if you had any understanding of what you're saying, you would have given an explanation yourself.

So go ahead and actually put something here that you can back up. It is a common scenario where someone has no real evidence to link something adjacent and then tell someone to 'go find it in this link'.

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.

I asked you about the specific of what you were trying to point out in your own link to the 15 year old message board and instead of answering that you moved on to something else.

Can you focus and nail down one claim with specifics before moving on to something else?

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.

If it's so similar, then copy and paste it or at least link directly to it. If you understand these things so well, why can't you explain them? Everything you are doing is the classic playbook of someone who can't really back up what they're saying. There is the 'I already gave evidence' phase and at some point the 'I would totally give real evidence, but I don't like the way you're asking' phase.

I've already done all the things you claim are impossible. That's how I know what you're saying is nonsense. Avoiding a double free on a pointer can always be done with atomic reference counting so that only one thread claims ownership. That's the whole story. You haven't given a shred of evidence to explain what garbage collection enables something that was previously impossible.

It is obvious that if you had something you could say that directly applies to what you claimed before (some algorithms can't be done without garbage collection), that you would have already said it a long time ago.

Reply on news.ycombinator.com