4 ms·

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

by pebal 4y ago

CyberDildonics 4y ago
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.
- pebal 4y ago
  Show an implementation of a concurrent lock-free stack without delayed freeing.
  - CyberDildonics 4y ago
    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.pdf https://people.csail.mit.edu/shanir/publications/Lock_Free.p... https://www.boost.org/doc/libs/1_55_0/boost/lockfree/stack.hpp https://www.boost.org/doc/libs/1_55_0/boost/lockfree/stack.h... https://lumian2015.github.io/lockFreeProgramming/lock-free-stack.html 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.
  - pebal 4y ago
    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.
    - CyberDildonics 4y ago
      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?
      - pebal 4y ago
        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-Building/Concurrent-stack/td-p/900745 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.
        CyberDildonics 4y ago
        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.

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

by pebal 4y ago

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.

pebal 4y ago
Show an implementation of a concurrent lock-free stack without delayed freeing.
- CyberDildonics 4y ago
  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.pdf https://people.csail.mit.edu/shanir/publications/Lock_Free.p... https://www.boost.org/doc/libs/1_55_0/boost/lockfree/stack.hpp https://www.boost.org/doc/libs/1_55_0/boost/lockfree/stack.h... https://lumian2015.github.io/lockFreeProgramming/lock-free-stack.html 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.
- pebal 4y ago
  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.
  - CyberDildonics 4y ago
    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?
    - pebal 4y ago
      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-Building/Concurrent-stack/td-p/900745 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.
      - CyberDildonics 4y ago
        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.