c - 数组性能与 LinkedList 非常相似 - 给出了什么？

Question

所以标题有点误导......我会保持简单:我正在比较这两种数据结构:

1. 一个数组，它从大小 1 开始，对于后续的每次添加，都会调用 realloc() 来扩展内存，然后将新的(malloced)元素追加到 n-1 位置。
2. 一个链表，我通过它跟踪头部、尾部和大小。添加涉及新元素的分配和更新尾指针和大小。

不要担心这些数据结构的任何其他细节。这是我对此测试唯一关心的功能。

理论上，LL 应该表现得更好。但是，它们在涉及 10、100、1000... 多达 5,000,000 个元素的时间测试中几乎相同。

我的直觉是堆很大。我认为数据段在 Redhat 上默认为 10 MB？我可能是错的。无论如何，realloc() 首先检查在已分配的连续内存位置 (0-[n-1]) 的末尾是否有可用空间。如果第 n 个位置可用，则不会重新定位元素。相反，realloc() 只是保留旧空间 + 紧随其后的空间。我很难找到这方面的证据，而且我也很难证明这个阵列在实践中应该比 LL 表现更差。

阅读以下帖子后，这里有一些进一步的分析:

[更新#1] 我已经修改了代码以具有一个单独的列表，该列表每 50 次迭代为 LL 和数组分配内存。对于数组的 100 万次添加，几乎始终有 18 次移动。没有为 LL 搬家的概念。我做了时间比较，它们仍然几乎相同。这是 1000 万次添加的一些输出:

(Array)
time ./a.out a 10,000,000
real    0m31.266s
user    0m4.482s
sys     0m1.493s
(LL)
time ./a.out l 10,000,000
real    0m31.057s
user    0m4.696s
sys     0m1.297s

我预计 18 步的时间会大不相同。数组添加需要 1 次以上的赋值和 1 次比较以获取和检查 realloc 的返回值以确保发生移动。

[更新#2] 我对上面发布的测试运行了一个 ltrace，我认为这是一个有趣的结果……看起来 realloc(或某些内存管理器)正在根据当前大小抢先将数组移动到更大的连续位置。 对于 500 次迭代，在迭代中触发内存移动: 1, 2, 4, 7, 11, 18, 28, 43, 66, 101, 154, 235, 358 这非常接近求和序列。我发现这非常有趣 - 我想我会发布它。

Answer 1

你是对的，realloc 只会增加分配 block 的大小，除非它被阻止这样做。在现实世界的场景中，您很可能会在后续添加到列表之间的堆上分配其他对象？在那种情况下，realloc 将不得不分配一个全新的内存块并复制列表中已有的元素。

每十次左右的插入尝试使用 malloc 在堆上分配另一个对象，看看它们是否仍然执行相同的操作。