本帖分为两个主要部分。第一部分介绍原始的测试用例和结果，以及我的思考。第二部分详细介绍了修改后的测试用例及其结果。
这个话题的原始标题是“完整遍历数组比链表快得多”。由于新的测试结果（在第二部分中呈现），标题被更改。
第一部分：原始测试用例
对于完整的单向顺序遍历，已知链表和数组具有类似的性能，但由于连续数组的缓存友好性（引用局部性），它可能会表现得（稍微）更好。为了看到它在实践中的工作情况（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毫秒，而第二个测试则给出80-85毫秒。 链表迭代似乎要慢100％。
我的（可能有缺陷的）思路和问题如下。 我欢迎（事实上，鼓励）任何更正。
好吧，我们经常可以读到数组是一个连续的内存块，因此按顺序访问其元素比链表更加缓存友好。 但是，在我们的情况下，数组的元素仅为对象引用，而不是Java中的Message对象本身（在C#中没有嵌入在数组中的结构体可以存储）。 因此，“参考位置”仅适用于数组元素本身，这些元素仅指定对象的地址。 因此，Message实例（一般情况下）仍然可以“任意”存储在内存中，因此“参考位置”不适用于实例本身。 从这一点出发，看起来我们和链表的情况相同：实例本身可能在内存中的“任何位置”：数组仅保证其引用存储在连续的块中...
...这就是使用案例：完全顺序遍历（迭代）。 首先，让我们检查每种情况下如何获得实例的引用。 在数组的情况下，这非常有效，因为它们在连续的块中。 但是，在链表的情况下，我们也很好，因为一旦我们访问了Message实例（这就是我们迭代的原因！），我们立即拥有了对下一个实例的引用。 而且，由于我们已经访问了Message的一个字段，访问另一个字段（“下一个”）应该受到缓存的支持（同一对象的字段也具有参考位置的局部性 AFAIK，它们也在一个连续的块中）。 总之，它似乎可以分解为以下几点：
- 数组提供了对引用的缓存友好迭代。
Message实例本身可能在内存中的“任何位置”，而我们也需要访问这些实例。 - 链表提供了当访问当前的
Message实例时获得下一个元素的引用。 这是“免费”的，因为每个Message实例都必须被访问（就像在数组情况下一样）。
基于上述内容，看起来数组并不比链表更好。唯一的例外是当数组是原始类型时（但在这种情况下，将其与链表进行比较是没有意义的）。因此，我预计它们的性能会相似，但实际上它们之间存在巨大的差异。实际上，如果我们假设每次访问元素时需要进行范围检查，则链表（理论上）可能会更快，因为数组访问的范围检查可能已被JIT优化掉了，所以我明白这不是一个有效的观点。
我的猜测如下：
- 这100%差异可能不是由数组的缓存友好性造成的。相反，JIT执行了无法在链表遍历时完成的优化。如果范围检查和（VM级别的）空检查被消除，那么我猜“array-get”字节码指令在链表情况下可能比我的“field-get”（或叫其他名字）指令快（？）。
- 即使Message实例可能位于内存中的任何位置，它们很可能非常接近，因为它们是“同时”分配的。但是，无法缓存1,000,000个实例，只能缓存其中的一部分。在这种情况下，在数组和链表情况下都是连续访问缓存友好的，因此这不能解释差异。
- 一些智能“预测”（预取）我将访问的Message实例？也就是说，某种方式仍然存在Message实例的缓存友好性，但仅在数组访问的情况下。
更新：由于收到了几条评论，我想在下面做出回应。
@irreputable：
链表从高地址访问到低地址。如果它是另一种方式，即next指向一个新对象而不是前一个对象
非常好的发现！我没有考虑到布局可能会影响测试的这个小细节。我今天会进行测试，并带着结果回来。 （编辑：结果在这里，我已经更新了本帖的“第二部分”）。
@Torben的评论：
我认为整个练习似乎毫无意义。您正在谈论100,000次迭代中的4ms改进。看起来像是过早的优化。如果您有一个这样的情况，那么请描述一下，我们可以研究一下它（因为它肯定比这个更有趣）。
如果这对您来说不感兴趣，那么您可以忽略此主题（而不是发布4次）。关于您毫无根据的“过早优化”的假设--恐怕您读了太多的SO并进行了太少的工业级开发。具体情况是在一个与模拟相关的软件中，可能需要每秒遍历这些列表多次。确实，超过120毫秒的延迟可能会影响应用程序的响应性。
我很感谢你的想法，但我真的找不到你的帖子中的问题。 :) 编辑：数组迭代速度快50％。 增加100％的速度意味着消耗零时间。
我相信从我的帖子中很明显，我想知道为什么存在非常显著的差异，当参数表明否则时。谢谢更正：确实，我想写链接列表案例比其他方式慢100%。
第二部分：修改后的测试案例
irreputable 给我提供了一个非常有趣的观察：
链表从高地址到低地址访问。 如果换个方向，即下一个指向一个新的对象而不是先前的对象呢？
我更改了链接列表结构，使其下一个指针的方向等于其节点的实例化顺序：
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;
}
然后我也进行了类似的原始数组测试：我将数组遍历改为相反的方向（倒计时循环）：
for (int i = cnt - 1; i >= 0; i--) {
Message msg = messages[i];
if (msg.value1 > 564645) {
val++;
}
}
结果一直是85-90毫秒！原始测试用例产生了40-41毫秒。
现在似乎有两个新结论（和一个问题）：
原来的说法似乎是正确的，即数组的“引用局部性”（由于连续的内存块）在“引用类型”（即对象）数组的情况下不提供优势，当它们与链表比较时。这是因为对象数组只保存对对象实例的引用，而不是对象实例本身（理论上可以在内存中的“任何地方”，就像链表的情况一样）。
在我的测试用例中，结果似乎取决于遍历的方向，即使在数组场景下也是如此！这怎么可能？
总结我的测试结果：
在“前向”遍历中，链表略优于数组遍历（与预期完全相同：获得
Message实例时我们立即拥有next引用，即无需访问数组元素以获取其地址）。在“反向”遍历中，两者性能都弱100%左右（并且链表也略胜一筹）。
有什么想法吗？
更新1：dlthorpe发表了非常有价值的评论。我将在此处粘贴它们，因为它们可能有助于找到这个“谜题”的答案。
是否有任何迹象表明硬件在内存高速缓存控制器中实现了向前预取页？除了仅加载所需的内存页外，还加载下一个更高页，以期望前进式读取？这样可以消除对内存的前进式进展的页面加载等待，但无法消除通过内存进行反向进展的页面加载等待。
[...]
我建议在完全不同的硬件上进行测试。大多数移动设备都运行某种形式的ARM SoC。请看看测试用例是否显示出类似于PC或Mac等Intel硬件的偏差。如果您能挖出旧的PowerPC Mac，那就更好了。如果这些显示出不同的结果，则说明ARM平台或其Java实现中存在某些独特的东西。
[...]
是的，您的访问模式大多是顺序的，但是方向不同。如果底层执行预取但仅在一个方向上（预先获取更高地址块），那么这将使得朝着该方向运行的测试结果偏向于有利。
更新2: 我在一台PC上运行了测试(Core i7 Nehalem架构, 8 GB RAM, Windows 7)。我在.NET 2.0源代码项目中使用C#.NET(但机器上安装了.NET 4)。我的结果，使用2500万个Message实例：
- 链表: 57-60毫秒
- 数组: 60-63毫秒
读取方向似乎不会影响结果。