realloc() 的性能消耗

Question

我想知道 realloc() 到底要花多少性能：我经常这样做是为了通过一个元素（=特定结构）扩展可用内存区域。多亏了 MMU，这样的 realloc() 只是保留内存区域的扩展，还是在某些条件下可以想象到所有数据的完整复制？

据我所知，当 std::vector 的大小增加并且预定义的内存量太小时，它通常必须复制内存区域......

Answer 1

realloc复制所有数据。假设其他任何事情都只会带来性能问题。可以避免复制的情况realloc很少，你绝对不应该指望它们。我见过不止一种实现，realloc甚至不需要实现代码来避免复制，因为它不值得付出努力。

MMU 与此无关，因为重新映射支持分配的内存页面的成本在您命中两个以上页面之前不会得到回报。这是基于我 15 年前读到的研究，从那时起，内存复制变得更快，而内存管理由于 MP 系统而变得更加昂贵。这也仅适用于内核内部的零复制方案，而不会传递系统调用开销，这很重要并且会减慢速度。它还要求您的分配完全一致和大小，进一步降低了实施realloc这种方式的有用性。

realloc如果未分配数据要扩展到的内存块，最多可以避免复制数据。如果realloc这是您的应用程序所做的唯一事情，您可能会很幸运，但是只要有一点碎片或其他事情分配，您就不走运了。始终假设 realloc 是malloc(new_size); memcpy(new, old, old_size); free(old);。

处理调整数组大小时的一个好习惯realloc是跟踪数组中有多少元素并具有单独的容量。realloc仅当元素数量达到容量时才增加容量。每次重新分配时将容量增加 1.5 倍（大多数人都会增加 2 倍，这在文献中经常推荐，但研究表明 2 倍会导致非常严重的内存碎片问题，而 1.5 倍的效率几乎相同，并且对内存来说要好得多）。像这样的东西：

if (a->sz == a->cap) {
    size_t ncap = a->cap ? a->cap + a->cap / 2 : INITIAL_CAP;
    void *n = realloc(a->a, ncap * sizeof(*a->a)); 
    if (n == NULL)
         deal_with_the_error();
    a->a = n;
    a->cap = ncap;
}
a->a[a->sz++] = new_element;

如果包含数组的结构被零初始化，这甚至适用于初始分配。