logo标签列表

realloc和memcpy是如何工作的？

cmemory-managementrealloc
30

我有两个问题。

  1. realloc() 和 memcpy() 是否以比逐个元素迭代更快的方式复制数组中的条目（ O(N)）？如果是，则你认为它的复杂度是什么？

  2. 如果分配的大小小于原始大小，realloc() 是否会将条目复制到其他位置，还是只是将它们保留在原地并减小数组的大小？

8个回答
26

让我们更仔细地看一下memcpy，同时也看看“大O”或者兰道符号。

首先，谈到大O。正如我在其他地方提到的那样，值得记住大O的定义，即当存在常数k使得某个函数g(n)≤kf(n)，则称函数g(n)是O(f(n))的。这个常数的作用是让你忽略细节，而只关注重要部分。正如每个人都已经注意到的那样，在大多数任何普通架构中，复制n字节的memcpy将是O(n)，因为无论如何，你都必须一次移动这些n个字节。因此，C语言中第一个天真的实现memcpy可以写成：

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 步，而只是执行了三个指令。

但实际上，它在底层执行了O(n)微指令。两者之间的区别在于常量 k；因为微码更快，并且指令只有三个解码步骤，所以它比原始版本快得多，但它仍然是 O(n) -- 只是常量更小而已。

这就是为什么你可以充分利用 memcpy -- 它并不是渐近意义上更快，但在那种特定的架构下实现是尽可能快的。

21
5
  1. 没有任何一种方式能比O(N)更快地复制N个项目。但是，可能可以同时复制多个项目，或使用特殊的处理器指令 - 因此它仍然可能比您自己做得更快。
  2. 我不确定，但我会假设内存完全重新分配。这是最安全的假设，而且可能取决于具体实现。
5

  1. memcpy的性能实际上不能比O(N)更好，但它可以进行优化，以使其优于手动复制；例如，它可能能够在您复制1个字节的时间内复制4个字节。许多memcpy实现都是使用优化指令的汇编语言编写的，可以一次复制多个元素，这通常比逐个字节地复制数据要快。

  2. 我不太理解这个问题，如果您使用realloc来减小内存大小并且它成功了（返回非NULL），则新位置将包含与旧位置相同的数据，直到新请求的大小为止。如果由于调用realloc而更改了内存位置（减小大小时通常不会发生），则内容将被复制，否则不需要复制，因为内存没有移动。

2
  1. 可以猜想，memcpy函数能够被编写成可以移动大量的比特位。例如，如果有优势的话，完全可以使用SSE指令来复制数据。

正如其他人所说，它不会比O(n)更快，但是内存系统通常有首选块大小，并且还可以一次写入缓存行大小。

0

假设您在谈论glibc，并且由于您的问题取决于实现，最好只是检查源代码：

malloc.c

memcpy.c

我的理解是，答案如下：

  1. O(N) --- 没有比线性时间更好的复制项目的方法。
  2. 当使用realloc()来缩小它们时，偶尔会复制大型项目。
0

x86有特殊指令用于扫描和匹配内存块中的字节/单词，还有一个可用于复制内存块的指令（毕竟它是CISC CPU）。许多实现内联汇编语言和使用#pragma进行整个函数内联的C编译器多年来一直利用这一点在其库函数中使用。

用于mem copy的指令是movsb/movsw，结合rep指令使用。

CMPS/MOVS/SCAS/STOS
REP, REPE, REPNE, REPNZ, REPZ

设置寄存器与源/目标地址和中断计数，然后就可以开始了。

0

关于realloc（请在dev c++上检查）的一些重要点：

  1. realloc()函数将更改由ptr指向的内存对象的大小，使其大小为size。

  2. 对象的内容保持不变，直到新旧大小中较小的那个。

  3. 如果新大小较大，则新分配部分对象的内容是未指定的。

  4. 如果size为0且ptr不是空指针，则释放所指向的对象。

  5. 如果ptr是空指针，则realloc()相当于为指定的大小分配内存。

  6. 如果ptr与之前由calloc()、malloc()或realloc()返回的指针不匹配，或者该空间以前已被free()或realloc()调用释放，则行为是未定义的。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接