>一个数组,从大小开始,每次后续添加,都有一个realloc()调用来扩展内存,然后将新的(malloced)元素追加到n-1位置.
>链表,我跟踪头部,尾部和大小.另外还涉及mallocing一个新元素并更新尾指针和大小.
不要担心这些数据结构的任何其他细节.这是我对此测试唯一关注的功能.
理论上,LL应该表现得更好.然而,它们在涉及10,100,1000 ……多达5,000,000个元素的时间测试中几乎相同.
我的直觉是堆很大.我认为Redhat上的数据段默认为10 MB？我错了.无论如何,realloc()首先检查在已分配的连续内存位置(0- [n-1])的末尾是否有空间可用.如果第n个位置可用,则不会重新定位元素.相反,realloc()只是将旧空间保留在紧随其后的空间中.我很难找到这方面的证据,而且我很难证明这个阵列在实践中应该比LL更差.
以下是阅读以下帖子后的进一步分析：
[更新#1]
我已经修改了代码,以便为LL和数组提供一个单独的列表,每隔50次迭代就会显示malloc内存.对阵列增加了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
这与求和序列非常接近.我发现这很有意思 – 以为我会发布它.
在这两种情况下,您都在调用内存分配函数.通常,内存分配函数从操作系统中获取一块内存(可能是一页),然后根据应用程序的需要将其分成更小的部分.
另一个假设是,realloc()会不时吐出虚拟对象并在其他地方分配大块内存,因为它无法在当前分配的页面中获得连续的块.如果您没有在列表扩展之间对内存分配功能进行任何其他调用,则不会发生这种情况.也许您的操作系统使用虚拟内存意味着无论物理页面来自何处,您的程序堆都会连续扩展.在这种情况下,性能将与一堆malloc()调用相同.
期望在混合malloc()和realloc()调用的地方改变性能.