realloc和memcpy如何工作？

Question

我有两个问题.

1. 不要realloc()和memcpy()阵列中的复制项目到另一个的方式更快的不仅仅是遍历每个元素O(N)？如果答案是肯定的,那么您认为它的复杂性是什么？

2. 如果分配的大小小于原始大小,是否realloc()将条目复制到其他位置,或者只是将它们保留,因为它们会减小数组的大小？

Answer 1

1 - 否.他们一次复制一个块.请参阅http://www.embedded.com/design/configurable-systems/4024961/Optimizing-Memcpy-improves-speed以获得非常好的分析.

2 - 这取决于实现.有关glibc的详细信息,请参见http://www.gnu.org/software/libtool/manual/libc/Changing-Block-Size.html."在几个分配实现中,将块缩小有时需要复制它"

Answer 2

让我们仔细看看memcpy,虽然我们正处于"大O"或Landau符号.

首先,大O. 正如我多次谈到过其他地方,这是值得记住的大O字的定义,这是一些函数G(N)被认为是O(F(N))时存在一个常数ķ针对G(N) ≤ kf(n).常量的作用是让你忽略重要部分的小细节.大家都注意到,memcpy的ñ个字节将是O(n)的多数任何正常的架构,因为无论你有什么搬完ñ个字节,在一次一个数据块.因此,memcpy可以编写C中的第一个天真的实现

unsigned char *
memcpy(unsigned char * s1, unsigned char * s2, long size){
    long ix;
    for(ix=0; ix < size; ix++)
        s1[ix] = s2[ix];
    return s1;
}

这实际上是O(n),可能会让你想知道为什么我们甚至打扰库例程.然而,关于libc函数的事情是它们是特定于平台的实用程序被编写的地方; 如果你想优化架构,这是你可以做到的地方之一.因此,根据架构,可能会有更高效的实施选项; 例如,在IBM 360架构中,有一条MOVL指令可以使用非常高度优化的微码来移动数据.因此,代替那个循环,memcpy的360实现可能看起来像

LR 3,S1      LOAD S1 ADDR in Register 3
LR 4,S2      
MOVL 3,4,SIZE

(顺便说一下,不能保证完全正确的360代码,但它可以用于说明.)这个实现看起来不像C代码那样围绕循环执行n步骤,它只执行3条指令.

什么真的发生了,虽然是它的执行O(n)的微在幕后操作.两者之间有什么不同的是常数k ; 因为微码的速度要快得多,而且因为有只有三个指令解码步骤,这是显着高于幼稚的版本快,但它仍然为O(n) -它只是不断较小.

这就是为什么你可以很好地利用memcpy它 - 它不是渐近更快,但实现速度与某人可以在特定架构上实现的速度一样快.

Answer 3

1. 绝对没有办法比O(N)更快地复制N个项目.但是,它可能能够一次复制多个项目,或者使用特殊的处理器指令 - 因此它仍然可能比您自己做的更快.
2. 我不确定,但我认为内存已完全重新分配.这是最安全的假设,无论如何它可能都依赖于实现.

Answer 4

1. 性能memcpy不能真正优于O(N),但可以进行优化,使其优于手动复制; 例如,它可能能够在复制1个字节的时间内复制4个字节.许多memcpy实现都是使用优化指令在汇编中编写的,这些指令可以一次复制多个元素,这通常比一次一个字节复制数据更快.

2. 我不太明白这个问题,如果你使用realloc减少内存的大小并且它成功(返回非NULL),新位置将包含与旧位置相同的数据,直到新请求的大小.如果由于调用而改变了内存位置realloc(减小大小时通常不会),则会复制内容,否则不需要进行复制,因为内存未移动.