- 现代操作系统(Linux - 最让我感兴趣的; FreeBSD、OSX、Windows)和它们的realloc实现是否真正能够使用虚拟到物理映射的重排而无需逐字节复制来重新分配数据页?
- 用于实现此内存移动的系统调用是什么?(我认为它可以使用SPLICE_F_MOVE和splice,但它已经有缺陷并且现在是无操作的(?))
请参见thejh的答案。
谁是演员?
在您的Qt示例中,至少有三个演员。
- Qt向量类
- glibc的
realloc()
- Linux的
mremap
QVector::capacity()
显示Qt分配了比所需更多的元素。这意味着添加一个元素通常不会realloc()
任何东西。 glibc分配器基于Doug Lea的分配器。这是一个binning分配器,支持使用Linux的mremap
。 binning分配器将类似大小的分配分组到bins中,因此典型的随机大小分配仍将具有一些增长空间,而无需调用系统。 即,自由池或松弛位于已分配内存的末尾。
一个答案
- 在多核多线程的世界中,使用这种页面重排而不是逐字节复制是否有益处,每次更改虚拟到物理映射都需要在所有数十个CPU核心中刷新(使无效)更改的页表项,其中包括IPI? (在Linux中,这就像flush_tlb_range或flush_tlb_page)
首先,比mremap还快的方法误用了mremap()
,如R在那里所指出的。
有几个因素使mremap()
作为realloc()
的基本要素具有价值。
- 降低内存消耗。
- 保留页面映射。
- 避免移动数据。
本答案中的所有内容都基于Linux的实现,但语义可以转移到其他操作系统。
减少内存消耗
考虑一个naiverealloc()
。
void *realloc(void *ptr, size_t size)
{
size_t old_size = get_sz(ptr);
if(size <= old_size) {
resize(ptr);
return ptr;
}
void * new_p = malloc(size);
if(new_p) {
memcpy(new_p, ptr, old_size);
free(ptr);
}
return new_p;
}
为了支持这一点,您可能需要在进行交换或仅仅无法重新分配之前,将realloc()
的内存加倍。
保留页面映射
Linux默认会将新的分配映射到一个零页面;一个4k的全零数据页面。这对于稀疏映射的数据结构很有用。如果没有人写入数据页面,则除了可能的PTE
表之外,不会分配任何物理内存。这些是写时复制Copy-On-Write或COW。但是,使用naive(幼稚的)realloc()
将不会保留这些映射,并为所有零页分配完整的物理内存。
如果任务涉及fork()
,则初始realloc()
数据可能在父进程和子进程之间共享。同样,COW会导致页面的物理分配。naive(幼稚的)实现会忽略这一点,并要求每个进程单独分配物理内存。
如果系统承受着内存压力,则现有的realloc()
页面可能不在物理内存中,而在交换空间中。naive(幼稚的)realloc()
将导致将交换页面从磁盘读入内存,复制到更新位置,然后可能将数据写回磁盘。
避免数据移动
您考虑的更新TLBs的问题与数据相比很小。单个TLB通常为4字节,并表示4K的物理数据页。如果刷新整个TLB,对于4GB系统来说,需要恢复4MB的数据。复制大量数据将使L1和L2缓存失效。TLB获取自然比d-cache和i-cache更好地管道化。代码连续的情况下,很少会出现两个TLB未命中的情况。
CPU有两种变体,VIVT(非x86)和根据x86的VIPT。 VIVT版本通常具有使单个TLB项无效的机制。对于VIPT系统,不应该需要使缓存无效,因为它们具有物理标记。
在多核系统上,一般不会在
所有核心上运行一个进程。只有执行
mremap()
的进程需要更新页表。当进程迁移到另一个核心时(典型的上下文切换),它需要迁移页面表。
结论
您可以构造一些病态案例,其中
naive复制效果更好。由于Linux(以及大多数操作系统)是用于
多任务的,因此将运行多个进程。而且,最坏的情况是在交换和
naive实现始终更差(除非您拥有比内存更快的磁盘)。对于最小的
realloc()
大小,
dlmalloc或
QVector应该具有
空闲空间,以避免系统级
mremap()
。通常的
mremap()
只需通过从
free pool中使用随机页来扩展
虚拟地址范围即可。只有当必须移动
虚拟地址范围时,
mremap()
可能需要
tlb flush,并且以下所有内容都为真:
realloc()
内存不应与父进程或子进程共享。
- 内存不应为sparse(大多数为零或未触及)。
- 系统不应在使用交换时受到内存压力。
只有当同一进程在其他核心上时,才需要进行
tlb flush和IPI。不需要为
mremap()
进行L1缓存加载,但对于
naive版本需要。 L2通常在核心之间共享,并且在所有情况下都是当前的。
naive版本将强制重新加载L2。
mremap()
可能会将一些未使用的数据留在L2缓存外;这通常是一件好事,但在某些工作负载下可能是一个缺点。可能有更好的方法来执行此操作,例如
预取数据。
realloc()
是在C库中实现的。在Linux上,libc通常是Doug Lea's malloc的eglibc/glibc版本。这是一个分配器,它具有特殊的HAVE_MREMAP,默认情况下为linux定义。splice()
是一个完全不同的概念。 TLB无效通常为4字节。因此,除非realloc
是1024*4k/10 cores或约512KB,否则mremap()
更好。它仍然可能比复制更好,因为复制将会使d-cache爆炸。 - artless noise