Fast, Shared, Upgradeable Mutex
Mutex operations are generally expensive on modern architectures and impose harsh limits on the concurrent throughput and scalability of an algorithm or system. Nonetheless mutual exclusion is easy to understand, widely applicable and is a prevailing method of solving resource sharing in concurrent systems.
Concurrent, lock-free vector
While a concurrent alternative to an std::vector is generally not as useful as, for example, a queue or hash-map, it is still an interesting data structure to develop.
This post describes the design choices that were made when designing a lock-free data structure, and hopefully will be of interest to some. By no means does it aim to be the most performant or “the best” way to write a lock-free vector or otherwise.
Designing a Lock-Free, Wait-Free Hash Map
Wait-free algorithms attract vast interest and are an area of intense research, the motivation being that true lock-free algorithms and data structures provide great benefits in terms of performance and scalability over lock-based variants. However designing lock-free systems isn’t a simple matter.