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.

It is quite common to have to compute a power-of-two: $2^p$, where $p\in\mathbb{Z}$. For IEEE-754 floating-points an expensive division (or power-instruction) can be avoided by exploiting the structure of the floating-point representation.

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.

The current (C++14) standard declares copy and move constructors as non-template constructors:

Microfacet BRDFs became very popular in real-time (and otherwise) rendering in recent years, with Epic and Disney jumping on the bandwagon as well, due to their physical-based origins, performance and plausibility.

A common problem in real time rendering is ordering draw/compute tasks (henceforth, tasks) in an optimal manner. Different order of execution can greatly affect performance, for example by influencing the amount of API calls. A lot of recent development of the OpenGL API has been focused on reducing draw calls and “Approaching Zero Driver Overhead” [1]. Likewise it is a common practice to group tasks by GLSL programs, FBOs and textures.

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.