pinned_vector: A Contiguous Container without Pointer Invalidation

Speaker: Miro Knejp, Jakob SchweiƟhelm

Audience level: Intermediate | Advanced

category

std::vector is the most popular container in the Standard Library, and for good reasons. It has the best performance characteristics for iteration-heavy workloads and is commonly understood as the recommended go-to container. However users have to be careful about the iterator-invalidating side-effects many of its operations have. In general this means it cannot be used for algorithms that require stable pointers to a vector's elements, as those pointers can be invalidated even by a simple push_back. Consequently, many containers have been invented to circumvent this issue. These usually involve the allocation of individual blocks of memory (like std::deque) or extra levels of indirection (like boost::stable_vector). But in doing so, they sacrifice vector's most cherished property: contiguous storage.

This talk presents pinned_vector, a container which has all the benefits of std::vector (namely contiguous storage of its elements) but does not reallocate its memory when growing or shrinking, and therefore does not suffer from pointer and iterator invalidation, which additionally makes it compatible with types neither copyable nor movable. The underlying mechanism of pinned_vector is virtual memory mapping, a technique supported by practically every operating system and hardware, barring the most restricted embedded devices, but does not seem to get much attention in the C++ community. It explains what virtual memory mapping is, and how it enables pinned_vector to provide the aforementioned guarantees. Beyond that it presents some benchmarks of typical workloads, what the benefits and drawbacks of such a container are, and what kind of applications it enables.