I love the cheap chunk lookup by counting leading zeroes in the index! That’s a useful idea independently of the lock-free-ness. It can be useful to have a cheap-to-grow vector with stable item references; sometimes I use a std::deque for this in C++, but I don’t know if it uses the doubling chunk size trick.
I would move the “stored” flags out of the items, into a parallel bitmap, to save space.
This vector can support overwrites (set) as long as the value type doesn’t require freeing (isn’t Droppable, in Rust.) Or it could support moving an item out, I think.
Unfortunately, the value types would need to be atomically updateable to make overwrites sound, because threads reading in parallel could experience tearing. This can, alas, only be fixed with some form of locking (e.g. a “locked” flag that gets set before writing and unset afterwards, in combination with a spin lock on the reader side) to keep readers from examining the value until it’s completely written.
That’s true; I was thinking of values either being smallish or references, both of which can be updated atomically. (IIRC many current 64-bit CPUs can atomically store 128-bit values.)
You are correct: 128-bit atomic operations have been supported for many years. They are useful for tagging pointers in lock-free data structures to avoid the ABA problem.
Specifically you can’t CAS a pointer assuming it uniquely identifies a single object for all time. An object could have been freed, and a new object allocated with the same address. Instead you should CAS a (counter, pointer) pair or similar.
I think the article already deals with the same issue at initialization time:
Because of this, we can’t rely on the counter to determine which elements are initialized, so entries need an additional atomic flag.
So you’d just set this flag at the start of any update, and clear it at the end, and the readers would use the same logic they already use to safely handle the fact that initialization may be non-atomic. (Importantly, in this data structure the entries aren’t lock-free, but the vector-as-a-whole has no global lock that blocks all concurrent readers).
I think the headline should be “a growable concurrent vector with no global read lock”. It seems to me there technically might be occassional global write locks (for chunk allocation, which is hopefully fast, and is infrequent by construction, so on average not a huge deal, especially for vectors that are read and updated more times than inserted/pushed).
I love the cheap chunk lookup by counting leading zeroes in the index! That’s a useful idea independently of the lock-free-ness. It can be useful to have a cheap-to-grow vector with stable item references; sometimes I use a std::deque for this in C++, but I don’t know if it uses the doubling chunk size trick.
I would move the “stored” flags out of the items, into a parallel bitmap, to save space.
This vector can support overwrites (set) as long as the value type doesn’t require freeing (isn’t Droppable, in Rust.) Or it could support moving an item out, I think.
Unfortunately, the value types would need to be atomically updateable to make overwrites sound, because threads reading in parallel could experience tearing. This can, alas, only be fixed with some form of locking (e.g. a “locked” flag that gets set before writing and unset afterwards, in combination with a spin lock on the reader side) to keep readers from examining the value until it’s completely written.
That’s true; I was thinking of values either being smallish or references, both of which can be updated atomically. (IIRC many current 64-bit CPUs can atomically store 128-bit values.)
You are correct: 128-bit atomic operations have been supported for many years. They are useful for tagging pointers in lock-free data structures to avoid the ABA problem.
Specifically you can’t CAS a pointer assuming it uniquely identifies a single object for all time. An object could have been freed, and a new object allocated with the same address. Instead you should CAS a (counter, pointer) pair or similar.
I think the article already deals with the same issue at initialization time:
So you’d just set this flag at the start of any update, and clear it at the end, and the readers would use the same logic they already use to safely handle the fact that initialization may be non-atomic. (Importantly, in this data structure the entries aren’t lock-free, but the vector-as-a-whole has no global lock that blocks all concurrent readers).
As memory allocators use locks, this would not be a lock free approach.
I think the headline should be “a growable concurrent vector with no global read lock”. It seems to me there technically might be occassional global write locks (for chunk allocation, which is hopefully fast, and is infrequent by construction, so on average not a huge deal, especially for vectors that are read and updated more times than inserted/pushed).