8

假设我曾经用字节ptr = malloc(old_size);分配内存块。old_size只有第一个header_size字节是有意义的。我要把尺寸增加到new_size.

new_size大于old_size并且old_size大于header_size。

前：

/- - - - - - - old_size - - - - - - - \
+===============+---------------------+
 \-header_size-/

后：

/- - - - - - - - - - - - - - - new_size - - - - - - - - - - - - - - - - - - -\
+===============+------------------------------------------------------------+
\- header_size-/

我不在乎之后存储了什么，ptr + header_size因为我会在那里读取一些数据。

方法一：直接去new_size

ptr = realloc(ptr, new_size);

方法2：收缩到header_size增长到new_size

ptr = realloc(ptr, header_size);
ptr = realloc(ptr, new_size);

方法3：分配一个新的内存块并复制第一个header_size字节

void *newptr = malloc(new_size);
memcpy(newptr, ptr, header_size);
free(ptr);
ptr = newptr;

哪个更快？

4

3 回答 3

3

malloc（对于整个块）和（对于增加大小时超出旧块大小的空间）都不能realloc保证您收到的内存将包含什么，因此，如果您希望将这些多余的字节设置为零（例如），您'必须自己做一些类似的事情：

// ptr contains current block.
void *saveptr = ptr;
ptr = realloc (ptr, new_size);
if (ptr == NULL) {
    // do something intelligent like recover saveptr and exit.
}
memset (ptr + header_size, 0, new_size - header_size);

但是，由于您已声明您不关心标题之外的内容，因此几乎可以肯定最快的是单个realloc，因为这可能会在幕后进行优化。

调用它两次进行收缩和扩展，或者调用malloc-new/memcpy/free-old不太可能像所有优化一样有效，你应该测量，不要猜测！

请记住，realloc不一定要复制您的记忆。如果扩展可以就地完成，那么智能堆管理器只会增加块的大小而不复制任何内容，例如：

+-----------+   ^        +-----------+ <- At same address,
| Old block |   | Need   | New block |      no copying
|           |   | this   |           |      involved.
+-----------+   | much   |           |
| Free      |   | now.   |           |
|           |   v        +-----------+
|           |            | Free      |
|           |            |           |
+-----------+            +-----------+
于 2012-11-06T09:00:11.247 回答
2

It almost certainly depends on the values of old_size, new_size and header_size, and also it depends on the implementation. You'd have to pick some values and measure.

1) is probably best in the case where header_size == old_size-1 && old_size == new_size-1, since it gives you the best chance of the single realloc being basically a no-op. (2) should be only very slightly slower in that case (2 almost-no-ops being marginally slower than 1).

3) is probably best in the case where header_size == 1 && old_size == 1024*1024 && new_size == 2048*1024, because the realloc would have to move the allocation, but you avoid copying 1MB of data you don't care about. (2) should be only very slightly slower in that case.

2) is probably best when header_size is much smaller than old_size, and new_size is in a range where it's reasonably likely that the realloc will relocate, but also reasonably likely that it won't. Then you can't predict which of (1) and (3) it is that will be very slightly faster than (2).

In analyzing (2), I have assumed that realloc downwards is approximately free and returns the same pointer. This is not guaranteed. I can think of two things that can mess you up:

  • realloc downwards copies to a new allocation
  • realloc downwards splits the buffer to create a new chunk of free memory, but then when you realloc back up again the allocator doesn't merge that new free chunk straight back onto your buffer again in order to return without copying.

Either of those could make (2) significantly more expensive than (1). So it's an implementation detail whether or not (2) is a good way of hedging your bets between the advantages of (1) (sometimes avoids copying anything) and the advantages of (3) (sometimes avoids copying too much).

Btw, this kind of idle speculation about performance is more effective in order to tentatively explain your observations, than it is to tentatively predict what observations we would make in the unlikely event that we actually cared enough about performance to test it.

Furthermore, I suspect that for large allocations, the implementation might be able to do even a relocating realloc without copying anything, by re-mapping the memory to a new address. In which case they would all be fast. I haven't looked into whether implementations actually do that, though.

于 2012-11-06T09:33:08.340 回答
1

这可能取决于大小以及是否需要复制。

方法 1 将复制旧块中包含的所有内容 - 但如果您不经常这样做，您将不会注意到。

方法 2 只会复制您需要保留的内容，因为您事先丢弃了其他所有内容。

方法 3 将无条件复制，而其他方法仅在内存块无法调整大小时复制。

就个人而言，如果您经常这样做，我更喜欢方法 2，如果您很少这样做，我更喜欢方法 1。分别地，我会介绍其中哪些会更快。

于 2012-11-06T09:04:43.960 回答