利用页表重映射避免数组扩容时的数据拷贝

可行性结论 #

这种利用虚拟内存页重映射避免数据拷贝的扩容技术，在支持虚拟内存且提供对应用户态API的操作系统（如Linux、Windows）中是可行的，但存在诸多限制条件。

实现方式（以Linux/Windows为例） #

Linux平台 #

• 预留连续虚拟地址范围：使用mmap(MAP_ANONYMOUS | MAP_PRIVATE, ...)调用，仅预留虚拟地址空间（不分配物理页），大小为扩容后的容器总容量。
• 重映射旧内存页到新地址：通过mremap系统调用，将原容器的内存区域直接重映射到新预留地址范围的前N页（N为原容器占用的页数），此操作无需拷贝数据。
• 解除旧地址映射：若mremap未自动释放旧地址，调用munmap解除原容器地址的映射关系。
• 提交新空间物理页：新地址中超出原容器大小的部分，会在首次访问时触发内核缺页机制自动分配物理页，也可通过madvise提前预分配。

Windows平台 #

• 预留连续虚拟地址范围：调用VirtualAlloc(..., MEM_RESERVE, ...)，预留足够大的虚拟地址空间。
• 映射旧内存到新地址：先通过CreateFileMapping将原容器内存转为共享内存对象，再用MapViewOfFile将其映射到新预留地址的前N页；之后调用VirtualFree解除原容器地址的映射。
• 提交新空间物理页：对新地址的额外空间调用VirtualAlloc(..., MEM_COMMIT, ...)分配物理页，或依赖首次访问时的缺页分配。

注意：实现这类容器时不能依赖标准库的malloc/free，必须全程用内存映射API管理内存，避免破坏堆的内部管理结构。

限制与阻碍因素 #

• 操作系统兼容性：仅支持提供虚拟内存操作API的系统，如Linux、Windows；macOS、部分嵌入式系统或无虚拟内存的平台无法实现。
• 数据类型约束：容器存储的数据不能包含指向原数组内部的绝对指针（相对偏移或索引不受影响），否则地址变更后指针会失效。仅适用于基本类型、无内部指针的结构体等类型。
• 虚拟地址空间限制：32位系统中虚拟地址空间紧张，难以预留大段连续地址；64位系统此问题大幅缓解，但仍需确保地址空间可用。
• 内存管理复杂度：需要手动处理内存映射的创建、销毁、异常回滚，以及多线程环境下的同步，实现成本远高于标准容器。
• 堆管理冲突：若使用标准堆分配的内存，无法直接对其进行重映射操作，会破坏堆的元数据结构，导致内存损坏。

内容的提问来源于stack exchange，提问作者Jeremy Friesner