Tho*_*alc 13 java arrays iteration android linked-list
这篇文章分为两个主要部分.第一部分介绍了原始测试用例和结果,以及我对它的看法.第二部分详细介绍了修改后的测试用例及其结果.
该主题的原始标题是"对阵列的完全迭代明显快于链接列表".由于更新的测试结果(见第二部分),标题发生了变化.
对于完整的单向顺序遍历,已知链表和数组具有相似的性能,但由于连续数组的缓存友好性(引用局部性),它可以(稍微)更好地执行.为了了解它在实践中是如何工作的(Android,Java),我检查了上述说法,并进行了一些测量.
首先,我天真的假设.我们来看看下面的课程:
private static class Message {
public int value1;
public Message next;
public Message(java.util.Random r, Message nextmsg) {
value1 = r.nextInt();
next = nextmsg;
}
}
在第一个测量场景中,next根本不会使用其字段.下面的代码创建了一个包含1,000,000个Message实例的数组,然后在循环中遍历数组.它测量迭代花费的时间.
Log.i("TEST", "Preparing...");
final int cnt = 1000000;
int val = 0;
java.util.Random r = new java.util.Random();
Message[] messages = new Message[cnt];
for (int i = 0; i < cnt; i++) {
messages[i] = new Message(r, null);
}
Log.i("TEST", "Starting iterating...");
long start = SystemClock.uptimeMillis();
for (int i = 0; i < cnt; i++) {
Message msg = messages[i];
if (msg.value1 > 564645) {
val++;
}
}
Log.w("TEST", "Time: " + (SystemClock.uptimeMillis() - start) + ", result: " + val);
第二个测量建立并测量链接的Message对象列表:
Log.i("TEST", "Preparing...");
final int cnt = 1000000;
int val = 0;
java.util.Random r = new java.util.Random();
Message current = null;
Message previous = null;
for (int i = 0; i < cnt; i++) {
current = new Message(r, previous);
previous = current;
}
previous = null;
Log.i("TEST", "Starting iterating...");
long start = SystemClock.uptimeMillis();
while (current != null) {
if (current.value1 > 564645) {
val++;
}
current = current.next;
}
Log.w("TEST","Time: " + (SystemClock.uptimeMillis() - start) + ", result: " + val);
第一次测试不断产生41-44 ms,而第二次测试产生80-85 ms.链表迭代似乎慢了100%.
我(可能存在缺陷)的思路和问题如下.我会欢迎(事实上,鼓励)任何更正.
好吧,我们经常可以读到一个数组是一个连续的内存块,因此顺序访问它的元素比链接列表更容易缓存.但在我们的例子中,数组的元素只是对象引用,而不是Message对象本身(在Java中,我们没有值类型,即C#中的结构,我们可以存储在数组中).因此,"引用位置"仅适用于数组元素本身,而这些仅指定对象的地址.因此,Message实例(通常)仍然可以在存储器中"任何地方",因此"引用位置"不适用于实例本身.从这一点来看,它看起来像链表一样:实例本身可以驻留在内存中的"任何地方":数组只保证它们的引用存储在一个连续的块中......
......以及用例:完整的顺序遍历(迭代).首先,让我们来看看我们如何在每种情况下获得对实例的引用.在数组的情况下,它非常有效,因为它们在一个连续的块中.但是在链表的情况下,我们也很好,因为一旦我们访问了一个Message实例(这就是我们迭代的原因!),我们立即引用了下一个实例.由于我们已经访问了一个已经存在的字段,Message因此缓存应该支持访问另一个字段("下一个")(同一个对象的字段也有一个引用AFAIK的位置,它们也在一个连续的块中) ).总而言之,它似乎可以分解为:
Message实例本身可能在内存中"任何地方",我们也需要访问它们.Message访问当前实例时获得对下一个元素的引用.这是"免费的",因为Message无论如何都必须访问每个实例(就像在数组中一样).因此,基于以上所述,看起来数组并不比链表更好.唯一的例外是当数组是基本类型时(但在这种情况下,将它与链表进行比较是没有意义的).所以我希望它们表现相似,但它们没有,因为存在巨大的差异.实际上,如果我们假设每次访问元素时数组索引都需要进行范围检查,那么链表(理论上)可能更快,甚至更快.(数组访问的范围检查可能是由JIT优化的,所以我知道这不是一个有效的点.)
我的猜测如下:
这可能不是数组的缓存友好性导致的100%差异.相反,JIT执行在链表遍历的情况下无法完成的优化.如果消除了范围检查和(VM级别)空检查,那么我猜"array-get"字节码指令可能比链表中的"field-get"(或其所谓的)指令更快(？ ).
尽管Message实例可能在内存中"任何地方",但它们可能彼此非常接近,因为它们是"同时"分配的.但是1,000,000个实例不能被缓存,只有一部分被缓存.在这种情况下,顺序访问在数组和链表情况下都是缓存友好的,因此这并不能解释差异.
Message我将访问的实例的一些智能"预测"(预取)？即以某种方式,Message实例本身仍然具有缓存友好性,但仅限于阵列访问的情况.
更新:由于收到了几条评论,我想在下面做出反应.
@irreputable:
从高地址到低地址访问链表.如果是另一种方式,即下一个指向较新的对象,而不是先前的对象,该怎么办？
非常好的地方!我没有想到布局可能影响测试的这个小细节.我今天将测试它,并将返回结果.(编辑:结果在这里,我已经用"第2节"更新了这篇文章).
@Torben评论:
另外我会说这整个练习似乎没用.你说的是超过100000次迭代的4ms改进.似乎过早优化.如果您遇到这种情况,那么请描述一下,我们可以对其进行调查(因为它肯定会比这更有趣).
如果它对您不感兴趣,那么您可以忽略此主题(而不是发布4次).关于你的"过早优化"的毫无根据的假设 - 我担心你读得太多SO并且工业级开发太少.具体情况是在与仿真相关的软件中,可能必须每秒多次遍历这些列表.实际上,120毫秒的延迟可能会影响应用程序的响应能力.
我很欣赏你对此的想法,但我真的找不到你帖子中的问题.:)编辑:数组迭代速度提高50%.快100%意味着零消耗时间.
我确信从我的帖子中可以明显看出,我想知道为什么存在非常显着的差异,当论证意味着其他情况时.感谢您的纠正:事实上,我想写一下链表案例慢100%.
irreputable有一个非常有趣的现象对我来说:
从高地址到低地址访问链表.如果是另一种方式,即下一个指向较新的对象,而不是先前的对象,该怎么办？
我更改了链表结构,使其next指针的方向等于其节点的实例化顺序:
Message current = null;
Message previous = new Message(r, null);
Message first = previous;
for (int i = 0; i < cnt; i++) {
current = new Message(r, null);
previous.next = current;
previous = current;
}
previous = current = null;
(请注意,创建算法可能不是最紧凑的算法,我认为我知道一种稍微好一点的方法.)迭代这个链表的代码:
while (first != null) {
if (first.value1 > 564645) {
val++;
}
first = first.next;
}
现在我得到的结果是37-39毫秒(好吧,我们可以说它正是数组的性能,但实际上,它在每个测试用例中都会稍微快一点.)而不是80毫秒的"反向"链表,它的速度快了两倍!
然后我也用原始数组测试用例进行了类似的测试:我将数组遍历更改为相反的方向(到倒计时循环):
for (int i = cnt - 1; i >= 0; i--) {
Message msg = messages[i];
if (msg.value1 > 564645) {
val++;
}
}
结果一直是85-90毫秒!原始测试用例产生40-41毫秒.
现在似乎有两个新的结论(和一个问题):
最初的声明似乎是真的,当数组与链表相比时,数组的"引用位置"(由于连续的内存块)在"引用类型"(即对象)数组的情况下不提供优势.这是因为对象数组只保存对象实例的引用,而不是对象实例本身(理论上,它可以在内存中的"任何地方",就像链表一样).
在我的测试用例中,结果似乎依赖于遍历的方向,即使在数组场景(!)的情况下也是如此.这怎么可能？
总结我的测试结果:
在"向前"方向遍历中,链表略微优于数组遍历(完全符合预期:当获得实例时,我们立即有下一个引用Message,即使不需要访问数组元素来获取其地址).
在"向后"方向遍历中,两者都具有大约100%的较弱性能(并且链表也略微优于阵列).
有任何想法吗？
更新1: dlthorpe发表了非常有价值的评论.我会在这里复制它们,因为它们可能有助于找到这个"谜语"的答案.
是否有任何迹象表明硬件在内存缓存控制器中实现了前瞻页面预取？不是仅加载内存引用所需的内存页面,而是加载下一个更高的页面以预期前向逐行读取？这将消除页面加载等待通过内存的正向进程,但不会消除页面加载等待通过内存的反向进程.
[..]
我建议测试完全不同的硬件.大多数移动设备都运行某种形式的ARM SoC.查看测试用例是否在英特尔硬件上显示类似的偏差,如PC或Mac.如果你能挖出旧的PowerPC Mac,那就更好了.如果这些没有显示出类似的结果,那么这将指向ARM平台或其Java实现上的独特内容.
[..]
是的,您的访问模式大多是顺序的,但方向不同.如果你下面的某些东西正在进行预取但只在一个方向上(预取下一个更高的地址块),那么这会使结果偏向于支持在该方向上运行的测试.
更新2:我在PC(Core i7 Nehalem架构从2009年2月,8 GB RAM,Windows 7)上运行测试.我在.NET 2.0源代码项目中使用了C#.NET(但是在机器上安装了.NET 4).我的结果有2500万个Message实例:
阅读方向似乎没有影响结果.
谈到 PC 硬件，早期的硬件预取器（例如 2005 年左右）更擅长检测和预取前向访问，但较新的硬件应该擅长检测两个方向。如果您对移动硬件感兴趣，它完全有可能仍然实现基本的仅向前预取。
除了在 MMU 中实现的正确预取（实际检测访问模式）之外，当发生高速缓存未命中时，硬件获取多个高速缓存行是很常见的。通常，当发生未命中时，除了所需的高速缓存行之外，还采取简单地获取下一个高速缓存行的形式。在这种情况下，这种实现方式可以有效地将缓存未命中率减半（假设预取无效），从而为前向提供很大的优势。
在本地，在 Core i7 上，我得到的链表版本的结果稍好一些，整个迭代的结果约为 3.3 毫秒，而数组版本的结果为 3.5 毫秒 - 使用原始程序时（以与创建相反的顺序迭代链表） 。所以我没有看到你所做的同样的效果。
检查 val 值的测试内循环有很大影响。当前的循环会导致很多错误预测，除非 JIT 编译器足够聪明，可以使用 CMOV 或类似的东西。在我的测试中，似乎是 - 因为对于适合 L1 的小迭代计数，我得到了大约 1 ns/迭代。1 ns（大约 3 个周期）与完整分支错误预测不一致。当我将其更改为执行无条件 val += msg.value1 时，数组版本得到了显着提升，即使在 1,000,000 次迭代的情况下（可能甚至不适合 L3）。
有趣的是，相同的转换 (val += msg.value1) 使链表版本稍微慢一些。通过转换，数组版本在小迭代次数下速度明显更快（在 L2 内部，两种方法在外部相当）。从卡尺：
length method ns linear runtime
100 ARRAY 63.7 =
100 LINKED 190.1 =
1000 ARRAY 725.7 =
1000 LINKED 1788.5 =
1000000 ARRAY 2904083.2 ===
1000000 LINKED 3043820.4 ===
10000000 ARRAY 23160128.5 ==========================
10000000 LINKED 25748352.0 ==============================
小迭代计数的行为更容易解释 - 必须使用指针追踪的链表在循环的每次迭代之间具有数据依赖性。也就是说，每次迭代都依赖于前一个迭代，因为要加载的地址来自前一个元素。该数组没有相同的数据依赖性 - 只有 i 的增量是相关的，而且速度非常快（i 肯定在此处的寄存器中）。因此在数组情况下循环可以更好地流水线化。
| 归档时间： |
|
| 查看次数： |
1628 次 |
| 最近记录： |