数组/链表：性能取决于遍历的*方向*？[已关闭]

这篇文章分为两个主要部分。第一部分介绍了原始测试用例和结果，以及我对此的看法。第二部分详细介绍了修改后的测试用例及其结果。

本主题的原始标题是“对数组的完整迭代比使用链表快得多”。由于测试结果较新，标题已更改（在第二部分中介绍）。

第一部分：原始测试用例

对于完整的单向顺序遍历，已知链表和数组具有相似的性能，但由于连续数组的缓存友好性（引用位置），它可能（略微）更好。为了了解它在实践中是如何工作的（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;
    }
}

在第一个测量方案中，根本不会使用其字段。下面的代码创建一个包含 1，000，000 个实例的数组，然后在循环中循环访问该数组。它测量迭代所需的时间。nextMessage

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%。

我的（可能有缺陷的）思路和问题如下。我将欢迎（事实上，鼓励）任何更正。

好吧，我们通常可以读到数组是一个连续的内存块，因此按顺序访问其元素比在链表的情况下更有利于缓存。但在我们的例子中，数组的元素只是对象引用，而不是对象本身（在Java中，我们没有值类型，即像C#中那样的结构，我们可以嵌入到数组中）。因此，“引用的局部性”仅适用于数组元素本身，而这些元素仅指定对象的地址。因此，实例（通常）仍可能位于内存中的“任何位置”，因此“引用位置”不适用于实例本身。从这一点来看，看起来我们和链表的情况是一样的：实例本身可以驻留在内存中的“任何地方”：数组只保证它们的引用存储在连续的块中......MessageMessage

...这里出现了用例：完整的顺序遍历（迭代）。首先，让我们检查一下在每种情况下如何获取对实例的引用。对于数组，它非常有效，因为它们位于连续块中。但是对于链表，我们也很好，因为一旦我们访问了一个实例（这就是我们迭代的原因！），我们就会立即获得对下一个实例的引用。由于我们已经访问了 一个字段，因此缓存应该支持访问另一个字段（“next”）（同一对象的字段也具有引用 AFAIK 的位置，它们也位于连续的块中）。总而言之，它似乎分解为：MessageMessage

1. 该数组提供对引用的缓存友好型迭代。 实例本身可能在内存中的“任何地方”，我们也需要访问这些实例。Message
2. 链接列表提供在访问当前实例时获取对下一个元素的引用。这是“免费的”，因为无论如何都必须访问每个实例（就像数组情况一样）。MessageMessage

因此，基于上述内容，看起来数组并不比链表更好。唯一的例外是当数组是基元类型时（但在这种情况下，将其与链表进行比较是没有意义的）。所以我预计它们的表现相似，但他们没有，因为存在巨大的差异。事实上，如果我们假设数组索引需要在每次访问元素时进行范围检查，那么链表（理论上）可能会更快，甚至。（数组访问的范围检查可能已通过 JIT 进行了优化，因此我知道这不是一个有效的观点。

我的猜测如下：

1. 可能不是阵列的缓存友好性导致了 100% 的差异。相反，JIT 执行在链接列表遍历时无法完成的优化。如果消除了范围检查和（VM级）空值检查，那么我猜“array-get”字节码指令可能比我在链接列表情况下的“field-get”（或它叫什么）指令更快（？）。

2. 尽管这些实例可能位于内存中的“任何位置”，但它们可能彼此非常接近，因为它们是“同时”分配的。但是无法缓存 1000000 个实例，只能缓存其中的一部分。在这种情况下，顺序访问在数组和链接列表情况下都是缓存友好的，因此这并不能解释差异。Message

3. 我将访问的实例的一些智能“预测”（预取）？也就是说，以某种方式，实例本身仍然具有缓存友好性，但仅在数组访问的情况下。MessageMessage

更新：由于收到了几条评论，我想在下面对它们做出反应。

@irreputable：

从高地址到低地址访问链表。如果它是相反的方式，即下一个指向较新的对象，而不是上一个对象，该怎么办？

非常好的地方！我没有想到这个小细节，布局可能会影响测试。我今天将对其进行测试，并将返回结果。（编辑：结果在这里，我已经用“第2节”更新了这篇文章）。

@Torben评论：

另外，我想说，整个练习似乎毫无用处。您正在谈论比100000次迭代提高4ms。似乎过早优化。如果您有一个瓶颈的情况，那么请描述它，我们可以研究它（因为它肯定会是一个比这更有趣的问题）。

如果您对此不感兴趣，则可以忽略此主题（而不是发布4次）。关于你对“过早优化”的毫无根据的假设——恐怕你读得太多了，工业级开发做得太少。具体情况是在模拟相关的软件中，该软件可能必须每秒遍历这些列表几次。实际上，120 毫秒以上的延迟可能会影响应用的响应能力。

我很欣赏你的想法，但我真的无法从你的帖子中找到一个问题 :)。编辑：数组迭代速度提高了 50%。100%的速度将意味着零耗时。

我敢肯定，从我的帖子中可以很明显地看出，我想知道为什么会出现非常显着的差异，而这些论点则意味着其他情况。感谢您的更正：确实，我想写链表的情况是100%慢。

第二部分：修改后的测试用例

无可辩驳的有一个非常有趣的观察对我来说：

从高地址到低地址访问链表。如果它是相反的方式，即下一个指向较新的对象，而不是上一个对象，该怎么办？

我更改了链表结构，使其指针的方向等于其节点的实例化顺序：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 ms。

现在似乎有两个新结论（和一个问题）：

1. 最初的说法似乎是正确的，即数组的“引用局部性”（由于连续的内存块）在与链接列表进行比较时，在“引用类型”（即对象）数组的情况下没有提供优势。这是因为对象数组只保存对对象实例的引用，而不保存对象实例本身（理论上，对象实例可以在内存中的“任何地方”，就像在链表的情况下一样）。

2. 在我的测试用例中，结果似乎取决于遍历的方向，即使在数组方案的情况下也是如此（！）。这怎么可能？

总结一下我的测试结果：

1. 在“正向”方向遍历中，链表的性能略优于数组遍历（完全符合预期：当获得实例时，我们立即有下一个引用，即即使不需要访问数组元素来获取其地址）。Message

2. 在“向后”方向遍历中，两者的性能都弱约100%（并且链表的性能也略优于数组）。

有什么想法吗？

更新1：Dlthorpe提出了非常有价值的意见。我将把它们复制到这里，因为它们可能有助于找到这个“谜语”的答案。

是否有任何迹象表明硬件在内存缓存控制器中实现了提前页面预取？与其只加载内存引用所需的内存页，不如加载下一个更高的页，以预期进行正向渐进读取？这将消除通过内存进行正向进度的页面加载等待，但不会消除通过内存反向进度的页面加载等待。

[..]

我建议在完全不同的硬件上进行测试。大多数移动设备都在运行某种形式的 ARM SoC。查看测试用例在英特尔硬件（如 PC 或 Mac）上是否显示类似的偏差。如果你能挖出一台旧的PowerPC Mac，那就更好了。如果这些没有显示类似的结果，那么这将表明ARM平台或其Java实现上的独特之处。

[..]

是的，您的访问模式大多是顺序的，但方向不同。如果下面的某些东西正在执行预取，但只在一个方向上进行（预取下一个较高的地址块），那么这将使结果偏向于在该方向上运行的测试。

更新 2：我在PC上运行了测试（2009年2月的Core i7 Nehalem架构，8 GB RAM，Windows 7）。我在 .NET 2.0 源代码项目中使用了 C#.NET（但 .NET 4 安装在计算机上）。我的结果，有 2500 万个实例：Message

• 链表： 57-60 ms
• 阵列： 60-63 ms

阅读的方向似乎并没有影响结果。