C++有std :: vector,Java有ArrayList,许多其他语言都有自己的动态分配数组.当动态数组空间不足时,它会重新分配到更大的区域,旧值将被复制到新数组中.这种阵列性能的核心问题是阵列的大小增长速度.如果你总是只能变得足够大以适应当前的推动,那么你每次都会重新分配.因此,将数组大小加倍,或将其乘以1.5倍是有意义的.
有理想的生长因子吗？2倍？1.5倍？理想上,我的意思是数学上合理,最佳平衡性能和浪费的记忆.理论上,我认识到,鉴于您的应用程序可能具有任何可能的推送分布,这在某种程度上取决于应用程序.但我很想知道是否有一个"通常"最好的值,或者在一些严格的约束条件下被认为是最好的.
我听说有一篇关于这个的文章,但我一直都找不到.
Windows具有VirtualAlloc,它允许您保留连续的地址空间区域,但实际上不使用任何物理内存.稍后当您想要使用它(或其中的一部分)时,再次调用VirtualAlloc以提交先前保留页面的区域.
这实际上非常有用,但我想最终将我的应用程序移植到linux - 所以如果我以后无法移植它,我不想使用它.linux有办法做到这一点吗？
编辑 - 用例
我正在考虑分配4 GB或一些这样的虚拟地址空间,但一次只能提交64K.这将为我提供一种零拷贝方式来生成高达4 GB的阵列.这一点很重要,因为典型的两倍数组大小和副本会为非常大的数组引入看似随机的不可接受的延迟.
我需要使用VirtualAlloc/VirtualAllocEx？
一个例子,我发现的一个案例 - 如果我分配了4 GB的虚拟内存,那么如果我不使用所有这些,那么我不会花费物理内存,如果我调整我的数组,我不需要做新的分配旧数据并将其复制到新数组.
struct T_custom_allocator; // which using VirtualAllocEx()
std::vector<int, T_custom_allocator> vec;
vec.reserve(4*1024*1024*1024); // allocated virtual memory (physical memory is not used)
vec.resize(16384); // allocated 16KB of physical memory
// ...
vec.resize(32768); // allocated 32KB of physical memory
// (no need to copy of first 16 KB of data)
如果我使用标准分配器,我需要在调整大小时复制数据:
std::vector<int> vec;
vec.resize(16384); // allocated 16KB of physical memory
// ...
vec.resize(32768); // allocated 32KB of physical memory
// and need to …