4 ms·

It was mentioned in the article and was not considered a candidate due to a specific API requirement: > Other mature programming languages with support for ref

It was mentioned in the article and was not considered a candidate due to a specific API requirement: > Other mature programming languages with support for reference counting include Objective-C, Swift, and Rust [50]. However, in its algorithm for duplicate marking, elPrep requires an atomic compare-and-swap operation on reference-counted pointers, which does not exist in those languages, but exists in C++17.

kinghajj 6y ago
So they need https://crates.io/crates/arc-swap https://crates.io/crates/arc-swap ?
zozbot234 6y ago
Except that this "atomic" operation over shared_ptr's in the C++ standard isn't actually required to be lock free, and is in fact not lock free in common stdlib implementations. So they're not actually gaining anything over, e.g. RwLock<Arc<RwLock<T>>> in Rust.
- gpderetta 6y ago
  They are atomic in the sense that it is not possible to observe the intermediate states and they are not data races. It is extremely hard though to implement them in a lock-free way without a true DCAS (which pretty much no architecture implements). I think all implementations use spinlock pools. I guess transactional hardware could be used. This is one of the reasons why GC does make it easier to implement some lock free algorithms as you do not have to worry about races during memory deallocation. Without GC, I I guess the next best thing is RCU or harzard pointers, but they are significantly more complex. From a cursory read I do not see any fancy lock free algorithm in the code though, so I'm not sure why they need atomic operations on shared_ptrs.
  - the8472 6y ago
    > without a true DCAS (which pretty much no architecture implements) Does x86-64's cmpxchg16b not qualify?
    - gpderetta 6y ago
      That's 2CAS. A true DCAS works on two arbitrary sized locations, cmpxchg16b acts on two contiguous pointer sized locations.
      - the8472 6y ago
        I am aware, but that restriction shouldn't affect its use for an atomic ref-counted pointer since you can place the count and the pointer next to each other.
        gpderetta 6y ago
        How would it work exactly? The layout of a generic shared ptr (but not specifically std::shared_ptr) is: ptr -> (count, payload) instead of: (count, ptr) -> payload As you can see, count is not alongside the pointer itself as distinct instances of ptrs need to share the count. Let's say you want to acquire an additional reference to ptr. You need to both copy the current value of ptr and increment count atomically to protect against concurrent modifications of ptr that might drop the last reference to payload. Delaying the deallocation of payload via hazard pointers, RCU or some other deferred reclamation scheme works, but it is significantly more complex. I believe this is what the rust arc-swap package does internally.
        the8472 6y ago
        Ah you are right, I was only considering the limited case of replacing the value when the reference count is 1.

kinghajj 6y ago

So they need https://crates.io/crates/arc-swap https://crates.io/crates/arc-swap ?

zozbot234 6y ago

Except that this "atomic" operation over shared_ptr's in the C++ standard isn't actually required to be lock free, and is in fact not lock free in common stdlib implementations. So they're not actually gaining anything over, e.g. RwLock<Arc<RwLock<T>>> in Rust.

gpderetta 6y ago
They are atomic in the sense that it is not possible to observe the intermediate states and they are not data races. It is extremely hard though to implement them in a lock-free way without a true DCAS (which pretty much no architecture implements). I think all implementations use spinlock pools. I guess transactional hardware could be used. This is one of the reasons why GC does make it easier to implement some lock free algorithms as you do not have to worry about races during memory deallocation. Without GC, I I guess the next best thing is RCU or harzard pointers, but they are significantly more complex. From a cursory read I do not see any fancy lock free algorithm in the code though, so I'm not sure why they need atomic operations on shared_ptrs.
- the8472 6y ago
  > without a true DCAS (which pretty much no architecture implements) Does x86-64's cmpxchg16b not qualify?
  - gpderetta 6y ago
    That's 2CAS. A true DCAS works on two arbitrary sized locations, cmpxchg16b acts on two contiguous pointer sized locations.
    - the8472 6y ago
      I am aware, but that restriction shouldn't affect its use for an atomic ref-counted pointer since you can place the count and the pointer next to each other.
      - gpderetta 6y ago
        How would it work exactly? The layout of a generic shared ptr (but not specifically std::shared_ptr) is: ptr -> (count, payload) instead of: (count, ptr) -> payload As you can see, count is not alongside the pointer itself as distinct instances of ptrs need to share the count. Let's say you want to acquire an additional reference to ptr. You need to both copy the current value of ptr and increment count atomically to protect against concurrent modifications of ptr that might drop the last reference to payload. Delaying the deallocation of payload via hazard pointers, RCU or some other deferred reclamation scheme works, but it is significantly more complex. I believe this is what the rust arc-swap package does internally.
        the8472 6y ago
        Ah you are right, I was only considering the limited case of replacing the value when the reference count is 1.