27

我有两个问题。

  1. realloc()以比仅迭代每个元素更快的方式将数组中的memcpy()条目复制到另一个数组中吗O(N)？如果答案是肯定的，那么您认为它的复杂性是什么？

  2. 如果分配的大小小于原始大小，是否realloc()将条目复制到其他地方，或者在它们减小数组大小时将它们保留？

4

8 回答 8

21

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。“在几种分配实现中，有时需要将块变小以复制它”

于 2008-12-12T14:28:33.123 回答
21

让我们更仔细地看一下memcpy“大 O”或朗道符号。

首先，大O。正如我在别处谈到的，值得记住大 O 的定义，即当存在一个常数k时，某个函数g(n)被称为O(f(n))，其中g(n) ≤ kf(n)。常量的作用是让您忽略小细节，转而关注重要部分。正如每个人都注意到的那样，在大多数正常架构中，n字节的 O(n) 将是O(n)，因为无论你必须移动这些n字节，一次一个块。因此，可以编写 C 中的第一个简单的实现memcpymemcpy

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——它并不是渐进地更快，但实现速度与某人在该特定架构上实现的速度一样快。

于 2008-12-27T04:19:34.363 回答
5
  1. 绝对没有办法比 O(N) 更快地复制 N 个项目。但是，它可能能够一次复制多个项目，或者使用特殊的处理器指令——所以它仍然可能比你自己做的要快。
  2. 我不确定，但我假设内存已完全重新分配。这是最安全的假设，无论如何它可能取决于实现。
于 2008-12-12T14:02:16.390 回答
5

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

  2. 我不太明白这个问题，如果你realloc用来减少内存大小并且它成功（返回非NULL），新位置将包含与旧位置相同的数据，直到新请求的大小。如果由于调用而更改了内存位置realloc（在减小大小时不常见），则将复制内容，否则由于内存没有移动，因此不需要进行复制。

于 2008-12-12T14:04:23.733 回答
2
  1. 可以推测，memcpy 可以这样写，它会移动大量的位。例如，如果有利的话，完全可以使用 SSE 指令复制数据。

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

于 2008-12-17T19:35:38.177 回答
0

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

malloc.c

memcpy.c

我读它的方式，答案是：

  1. O(N) --- 没有办法比线性时间更好地复制项目。
  2. 当使用 realloc() 缩小它们时，有时会复制大的项目。
于 2008-12-27T02:21:34.960 回答
0

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

用于 mem 复制的是 movsb/movsw 与 rep 指令的组合。

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

使用 src/trg 地址和 int 计数设置寄存器，然后就可以了。

于 2008-12-27T05:51:37.720 回答
0

与 realloc 相关的一些要点（检查 dev c++）： void *realloc(void *ptr, size_t size);

  1. realloc() 函数应将 ptr 指向的内存对象的大小更改为 size 指定的大小。

  2. 对象的内容应保持不变，直至新旧尺寸中的较小者。

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

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

  5. 如果 ptr 是空指针，realloc() 应等效于指定大小的 malloc()。

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

于 2012-02-18T03:13:00.487 回答