比较Collection中声明的removeAll(Collection<?> c)调用的速度时，我玩得很开心。现在我知道微基准测试很难做对，我不会看几毫秒的差异，但我相信我的结果是有效的，因为我反复运行它们并且它们非常可重复。
假设我有两个不太小的集合，比如 100,000 个连续的整数元素，而且它们大部分重叠，例如 5,000 个在左边，而不是右边。现在我只是打电话：
left.removeAll(right);
当然，这一切都取决于左集合和右集合的类型。如果正确的集合是哈希图，则速度非常快，因为这是完成查找的地方。但仔细观察，我注意到两个我无法解释的结果。我尝试了所有测试，包括一个排序的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 编译器是否在优化内容？但如果是这样，哪一个？我进行了热身并连续运行了几次测试，但也许我的基准测试存在根本问题？
性能差异的原因是内存访问模式：访问内存中连续的元素比执行随机内存访问更快(由于内存预取、CPU 缓存等)。
当您最初填充集合时，您会在内存中按顺序创建所有元素，因此当您遍历它(foreach，removeAll等)时，您正在访问缓存友好的连续内存区域。当你洗牌集合时 - 元素在内存中保持相同的顺序，但指向这些元素的指针不再以相同的顺序，所以当你遍历集合时，你将访问例如第 10 个、第 1 个和第 5 个元素，这非常不友好缓存并破坏性能。
你可以更详细地查看这个问题，其中可以看到这种效果： 为什么筛选未排序列表比筛选排序列表更快
由于提问者没有提供任何示例代码，并且对注释和答案中提到的基准存在疑问，因此我创建了一个小测试，以查看当参数是随机列表(而不是排序列表)时，removeAll方法是否更慢。我证实了提问者的观察：测试的输出大致为
100000 elements, sortedList and sortedList, 5023,090 ms, size 5000
100000 elements, shuffledList and sortedList, 5062,293 ms, size 5000
100000 elements, sortedList and shuffledList, 10657,438 ms, size 5000
100000 elements, shuffledList and shuffledList, 10700,145 ms, size 5000
我将在这里省略此特定测试的代码，因为它也受到了质疑(顺便说一下，这是完全合理的！很多BS都发布在网上...
所以我做了进一步的测试，我将在这里提供代码。
这也不能被视为一个明确的答案。但我试图调整测试，以便它们至少提供一些强有力的证据，证明性能降低的原因确实是 Svetlin Zarev 在他的回答中提到的(+1，如果它说服你，请接受这一点)。也就是说，速度变慢的原因在于分散访问的缓存效应。
首先：我知道在编写微基准测试时可能存在的许多陷阱(根据他的陈述，提问者也是如此)。但是，我知道没有人会相信谎言基准，即使它是完全合理的，除非使用适当的微基准测试工具执行。因此，为了表明随机列表的性能低于排序列表的性能，我创建了这个简单的JMH基准测试：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.infra.Blackhole;
@State(Scope.Thread)
public class RemoveAllBenchmarkJMH
{
@Param({"sorted", "shuffled"})
public String method;
@Param({"1000", "10000", "100000" })
public int numElements;
private List<Integer> left;
private List<Integer> right;
@Setup
public void initList()
{
left = new ArrayList<Integer>();
right = new ArrayList<Integer>();
for (int i=0; i<numElements; i++)
{
left.add(i);
}
int n = (int)(numElements * 0.95);
for (int i=0; i<n; i++)
{
right.add(i);
}
if (method.equals("shuffled"))
{
Collections.shuffle(right);
}
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public void testMethod(Blackhole bh)
{
left.removeAll(right);
bh.consume(left.size());
}
}
这个的输出如下：
(method) (numElements) Mode Cnt Score Error Units
sorted 1000 avgt 50 52,055 ± 0,507 us/op
shuffled 1000 avgt 50 55,720 ± 0,466 us/op
sorted 10000 avgt 50 5341,917 ± 28,630 us/op
shuffled 10000 avgt 50 7108,845 ± 45,869 us/op
sorted 100000 avgt 50 621714,569 ± 19040,964 us/op
shuffled 100000 avgt 50 1110301,876 ± 22935,976 us/op
我希望这有助于解决对声明本身的疑虑。
虽然我承认我不是JMH专家。如果这个基准有问题，请告诉我
现在，这些结果与我的另一个手动(非JMH)微基准大致一致。为了证明洗牌是问题的事实，我创建了一个小测试，使用不同程度洗牌的列表来比较性能。通过提供介于 0.0 和 1.0 之间的值，可以限制交换元素的数量，从而限制列表的随机性。(当然，这是相当"务实的"，因为考虑到"洗牌性"的不同可能(统计)措施，如何实施这一点有不同的选择)。
代码如下所示：
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.function.Function;
public class RemoveAllBenchmarkExt
{
public static void main(String[] args)
{
for (int n=10000; n<=100000; n+=10000)
{
runTest(n, sortedList() , sortedList());
runTest(n, sortedList() , shuffledList(0.00));
runTest(n, sortedList() , shuffledList(0.25));
runTest(n, sortedList() , shuffledList(0.50));
runTest(n, sortedList() , shuffledList(0.75));
runTest(n, sortedList() , shuffledList(1.00));
runTest(n, sortedList() , reversedList());
System.out.println();
}
}
private static Function<Integer, Collection<Integer>> sortedList()
{
return new Function<Integer, Collection<Integer>>()
{
@Override
public Collection<Integer> apply(Integer t)
{
List<Integer> list = new ArrayList<Integer>(t);
for (int i=0; i<t; i++)
{
list.add(i);
}
return list;
}
@Override
public String toString()
{
return "sorted";
}
};
}
private static Function<Integer, Collection<Integer>> shuffledList(
final double degree)
{
return new Function<Integer, Collection<Integer>>()
{
@Override
public Collection<Integer> apply(Integer t)
{
List<Integer> list = new ArrayList<Integer>(t);
for (int i=0; i<t; i++)
{
list.add(i);
}
shuffle(list, degree);
return list;
}
@Override
public String toString()
{
return String.format("shuffled(%4.2f)", degree);
}
};
}
private static void shuffle(List<Integer> list, double degree)
{
Random random = new Random(0);
int n = (int)(degree * list.size());
for (int i=n; i>1; i--)
{
swap(list, i-1, random.nextInt(i));
}
}
private static void swap(List<Integer> list, int i, int j)
{
list.set(i, list.set(j, list.get(i)));
}
private static Function<Integer, Collection<Integer>> reversedList()
{
return new Function<Integer, Collection<Integer>>()
{
@Override
public Collection<Integer> apply(Integer t)
{
List<Integer> list = new ArrayList<Integer>(t);
for (int i=0; i<t; i++)
{
list.add(i);
}
Collections.reverse(list);
return list;
}
@Override
public String toString()
{
return "reversed";
}
};
}
private static void runTest(int n,
Function<Integer, ? extends Collection<Integer>> leftFunction,
Function<Integer, ? extends Collection<Integer>> rightFunction)
{
Collection<Integer> left = leftFunction.apply(n);
Collection<Integer> right = rightFunction.apply((int)(n*0.95));
long before = System.nanoTime();
left.removeAll(right);
long after = System.nanoTime();
double durationMs = (after - before) / 1e6;
System.out.printf(
"%8d elements, %15s, duration %10.3f ms, size %dn",
n, rightFunction, durationMs, left.size());
}
}
(是的，这很简单。但是，如果您认为时间完全没用，请将它们与 JMH 运行进行比较，几个小时后，您会发现它们是合理的)
最后一遍的时间如下：
100000 elements, sorted, duration 6016,354 ms, size 5000
100000 elements, shuffled(0,00), duration 5849,537 ms, size 5000
100000 elements, shuffled(0,25), duration 7319,948 ms, size 5000
100000 elements, shuffled(0,50), duration 9344,408 ms, size 5000
100000 elements, shuffled(0,75), duration 10657,021 ms, size 5000
100000 elements, shuffled(1,00), duration 11295,808 ms, size 5000
100000 elements, reversed, duration 5830,695 ms, size 5000
可以清楚地看到，时间基本上是随着洗牌而线性增加的。
当然，这一切仍然不是证据，但至少证明斯韦特林·扎列夫的答案是正确的。
查看ArrayList.removeAll()(OpenJDK7-b147)的源代码，似乎IT委托给一个名为batchRemove()的私有方法，如下所示：
663 private boolean batchRemove(Collection<?> c, boolean complement) {
664 final Object[] elementData = this.elementData;
665 int r = 0, w = 0;
666 boolean modified = false;
667 try {
668 for (; r < size; r++)
669 if (c.contains(elementData[r]) == complement)
670 elementData[w++] = elementData[r];
671 } finally {
672 // Preserve behavioral compatibility with AbstractCollection,
673 // even if c.contains() throws.
674 if (r != size) {
675 System.arraycopy(elementData, r,
676 elementData, w,
677 size - r);
678 w += size - r;
679 }
680 if (w != size) {
681 for (int i = w; i < size; i++)
682 elementData[i] = null;
683 modCount += size - w;
684 size = w;
685 modified = true;
686 }
687 }
688 return modified;
689 }
它实际上遍历数组并具有一堆c.contains()调用。基本上，对于排序数组，此迭代没有理由会更快。
我支持StephenC对基准测试的怀疑，并相信在深入研究缓存访问模式等之前，仔细检查基准代码会更有成效。
此外，如果基准代码不是罪魁祸首，那么了解java版本和OS/arch等会很有趣。
现在我知道微基准测试很难做对，我不会看几毫秒的差异，但我相信我的结果是有效的，因为我反复运行它们并且它们非常可重复。
这并不能说服我。 有缺陷的基准测试的行为可以 100% 重现。
我怀疑...事实上。。。基准测试中的一个或多个缺陷>>是<<导致奇怪结果的原因。 经常是这样。
。但也许我的基准存在根本问题？
是的(海事组织)。
如果您想要更详细的答案，请向我们展示基准代码。