realloc和memcpy如何工作？
我有两个问题。
-
realloc()和memcpy()以比迭代每个元素O(N)更快的方式将数组中的条目复制到另一个中？ 如果答案是肯定的，那么您认为它的复杂性是什么？ -
如果分配的大小小于原始大小，
realloc()是否realloc()条目复制到其他位置，或者只是保留它们，因为它们会减小数组的大小？
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 。 “在几个分配实现中，将块缩小有时需要复制它”
让我们仔细看看memcpy ，当我们在它的时候，在“大O”或Landau表示法。
首先，大O. 正如我在其他地方所谈到的，值得记住大O的定义，即当存在g（n） ≤的常数k时，某些函数g（n）被称为O（f（n）） 。 kf（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步，它只执行3条指令。
然而， 真正发生的是它正在执行O（n）微指令 。 两者之间有什么不同的是常数k ; 因为微码更快，并且由于指令上只有三个解码步骤，它比天真版本快得多，但它仍然是O（n） - 它只是常数更小。
这就是为什么你可以充分利用memcpy - 它不是渐近更快，但实现速度与某人可以在特定架构上实现的速度一样快。
- 绝对没有办法比O（N）更快地复制N个项目。 但是，它可能能够一次复制多个项目，或者使用特殊的处理器指令 – 因此它仍然可能比您自己做的更快。
- 我不确定，但我认为内存已完全重新分配。 这是最安全的假设，无论如何它可能依赖于实现。
-
memcpy的性能实际上并不比O（N）好，但它可以进行优化，使其优于手动复制; 例如，它可能能够在复制1个字节的时间内复制4个字节。 许多memcpy实现是使用优化指令在汇编中编写的，这些指令可以一次复制多个元素，这通常比一次复制一个字节的数据更快。 -
我不太明白这个问题，如果你使用
realloc来减少内存的大小并且它成功（返回非NULL），新位置将包含与旧位置相同的数据，直到新请求的大小。 如果由于调用realloc而更改了内存位置（减小大小时通常不会），则会复制内容，否则不需要进行复制，因为内存未移动。
- 可以推测，memcpy可以写入，以便它可以移动大量的位。 例如，如果有利的话，完全可以使用SSE指令复制数据。
正如其他人所说，它不会比O（n）快，但是存储器系统通常具有优选的块大小，并且还可以，例如，一次写入高速缓存行的大小。
假设你在谈论glibc，并且因为你的问题是依赖于实现的，所以最好只检查源代码：
malloc.c
memcpy.c
我读它的方式，答案是：
- O（N）—无法以比线性时间更好的方式复制项目。
- 当使用realloc（）缩小它们时，偶尔会复制大型项目。
x86具有扫描和匹配内存块中的字节/字的特殊指令，以及可用于复制内存块的指令（毕竟它是一个CISC cpu）。 许多实现内联汇编语言的C编译器和一个用于内联整个函数的编译器已经多年在其库函数中利用了这一点。
用于mem copy的那些是movsb / movsw与rep指令的组合。
CMPS/MOVS/SCAS/STOS REP, REPE, REPNE, REPNZ, REPZ
安装程序使用src / trg地址和int计数寄存器然后离开。
与realloc相关的一些要点（检查dev c ++）：void * realloc（void * ptr，size_t size）;
-
realloc（）函数应将ptr指向的内存对象的大小更改为size指定的大小。
-
对象的内容应保持不变，直至新旧尺寸中的较小者。
-
如果新大小较大，则未指定新分配的对象部分的内容。
-
如果size为0且ptr不是空指针，则释放指向的对象。
-
如果ptr是空指针，则realloc（）应等于指定大小的malloc（）。
-
如果ptr与之前由calloc（），malloc（）或realloc（）返回的指针不匹配，或者如果先前已通过调用free（）或realloc（）释放空间，则行为未定义。