Java 性能 : Search and removal speed on removeAll()

Question

比较 removeAll(Collection<?> c) 的速度我觉得很有趣在 Collection 中声明的调用.现在我知道微基准测试很难正确执行，我不会考虑几毫秒的差异，但我相信我的结果是有效的，因为我反复运行它们并且它们非常可重现。

假设我有两个不太小的集合，比如说 100,000 个连续的整数元素，而且它们大部分重叠，例如左边有 5,000 个，右边没有。现在我只需调用:

left.removeAll(right);

当然这一切都取决于左右集合的类型。如果正确的集合是 HashMap ，速度会非常快，因为这是完成查找的地方。但仔细观察，我注意到两个无法解释的结果。我用 ArrayList 尝试了所有测试这是排序的，另一个是洗牌的(使用 Collections.shuffle() ，如果这很重要的话)。

---

第一个奇怪的结果是:

00293  025%   shuffled ArrayList, HashSet
00090  008%     sorted ArrayList, HashSet

现在要么从排序的 ArrayList 中删除元素比从随机列表中删除或从 HashSet 中查找连续值更快比查找随机值更快。

---

现在是另一个:

02311  011%     sorted ArrayList, shuffled ArrayList
01401  006%     sorted ArrayList,   sorted ArrayList

现在这表明在排序的 ArrayList 中查找(对左侧列表的每个元素使用 contains() 调用)比随机列表更快。现在，如果我们可以利用它已排序的事实并使用二进制搜索，那将非常容易，但我不这样做。

---

这两个结果对我来说都很神秘。我无法通过查看代码或我的数据结构知识来解释它们。它与处理器缓存访问模式有什么关系吗？ JIT 编译器是否优化了一些东西？但如果是这样，哪个？我进行了热身并连续运行了几次测试，但也许我的基准测试存在根本问题？

Answer 1

性能差异的原因是内存访问模式:访问内存中连续的元素比进行随机内存访问更快(由于内存预取、cpu 缓存等)

当您最初填充集合时，您会在内存中按顺序创建所有元素，因此当您遍历它(foreach、removeAll 等)时，您正在访问缓存友好的连续内存区域。当你打乱集合时——元素在内存中保持相同的顺序，但指向这些元素的指针不再是相同的顺序，所以当你遍历集合时，你将访问例如第 10 个、第 1 个、然后是第 5 个元素，它对缓存非常不友好并且会破坏性能。

您可以查看此问题，其中更详细地显示了此效果: Why filtering an unsorted list is faster than filtering a sorted list