Open link in next tab
A Lock-Free Vector
https://ibraheem.ca/posts/a-lock-free-vector/
Designing a fast, lock-free vector.
https://ibraheem.ca/posts/a-lock-free-vector/
Designing a fast, lock-free vector.
@Arbitrary I did this a while ago, you might find it useful. It abandons the more traditional vector concept of sequential insert, so that remove() can be implemented. https://github.com/Alonely0/Lariv
chunks: [AtomicPtr>; 64], appears before the explanation of why 64 works, and was confusing at first glance since this is completely different than the previous use of 64, which was arbitrary. I was expecting a variable-size array of fixed-size arrays at first (using something like an rwlock you can copy/grow the internal vector without blocking - if there was a writer, the last reader of the old allocation frees it).
Instead of separate flags, what about a single (fixed-size, if chunks are) atomic bitset? This would increase contention slightly but that only happens briefly during growth, not accesses. Many architectures actually have dedicated atomic bit operations though sadly it's hard to get compilers to generate them.
The obvious API addition is for a single thread to push several elements at once, which can be done more efficiently.