I was hoping that this article would be about C++'s terrible allocator interface and how to fix it. In particular C++ containers can only allocate and release memory, not grow existing allocations --- at least while using the standard allocator interface [1]. So when vector needs to grow, it always needs to copy all elements.
Why is this limitation important? Doesn't realloc copy anyway? Well, not always. Linux has this neat system call called mremap [2] that in theory allows an allocation to move in virtual address space but not in physical memory. (To be precise, mremap moves PTEs directly.) Realloc-via-mremap is much more efficient than relloc-via-copying, and it's a shame that limitations in C++ language design prevent our using it, at least with standard containers.
Yes, yes, a move constructor requires both source and destination addresses to be simultaneously valid, so we can't use mremap [3] in the general case. But lots of C++ objects (like, e.g., int) are trivially movable [4], and these objects would work just fine in an mremap-based vector.
for memory remapping hacks to be worthwhile, the vector needs to be huge, so I doubt it is often enough a win to be suitable for a general purpose library.
The reason for realloc is that often an allocator can extend an existing allocation in place if the next block is free (and this can be done without syscalls). As you described, except for trivially copyable objects though, realloc doesn't really work in C++, so a better allocator interface for C++ would be a try_realloc that would attempt to reallocate in place but do nothing on failure. Unfortunately most system allocators do not provide it [1] so it is kind of a catch-22 and most proposals never made it into the standard.
[1] jmalloc does provide xallocx that only reallocates in place though.
Copying large objects is significantly more expensive than copying small objects, and the cost is exacerbated due to cache effects. The C++ language contains a lot of optimizations for trivially copyable objects, e.g. std::copy, so having a realloc optimization for vectors would seem to be natural.
glibc malloc switches to mmap for allocations above ~128KB by default, which could be reached by vectors with just a few thousand elements (or a few very large objects). glibc does use mremap to reallocate mmap’d chunks - so in that sense the memory remapping hacks are already present in a general purpose library.
Why is this limitation important? Doesn't realloc copy anyway? Well, not always. Linux has this neat system call called mremap [2] that in theory allows an allocation to move in virtual address space but not in physical memory. (To be precise, mremap moves PTEs directly.) Realloc-via-mremap is much more efficient than relloc-via-copying, and it's a shame that limitations in C++ language design prevent our using it, at least with standard containers.
Yes, yes, a move constructor requires both source and destination addresses to be simultaneously valid, so we can't use mremap [3] in the general case. But lots of C++ objects (like, e.g., int) are trivially movable [4], and these objects would work just fine in an mremap-based vector.
[1] https://en.cppreference.com/w/cpp/memory/allocator [2] https://man7.org/linux/man-pages/man2/mremap.2.html [3] well, without the shared mapping dup hack, but that's specialized [4] https://quuxplusone.github.io/blog/2018/05/02/trivial-abi-10...