Java 性能：removeAll() 的搜索和删除速度
Java performance: Search and removal speed on removeAll()
比较 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 中查找连续值比查找 运行dom 值更快.
现在另一个：
02311 011% sorted ArrayList, shuffled ArrayList
01401 006% sorted ArrayList, sorted ArrayList
现在这表明排序后的 ArrayList 中的查找（对左侧列表的每个元素使用 contains() 调用）比打乱后的列表中的查找更快。现在，如果我们可以利用它已排序并使用二进制搜索这一事实，那将非常容易，但我不这样做。
这两个结果对我来说都很神秘。我无法通过查看代码或我的数据结构知识来解释它们。它与处理器缓存访问模式有什么关系吗？ JIT 编译器是否优化了一些东西？但如果是这样，哪个？我连续进行了几次热身和 运行 测试，但也许我的基准测试存在根本问题？
Now I know that micro-benchmarks are difficult to do right, and I won’t look at a few milliseconds difference, but I believe my results to be valid, since I ran them repeatedly and they are very reproducible.
这并不能说服我。有缺陷的基准测试的行为可以 100% 重现。
我怀疑......事实上......你的基准测试中的一个或多个缺陷>>是<<导致你奇怪结果的原因。经常是。
... but perhaps there is a fundamental problem with my benchmark?
是（海事组织）。
如果您需要更详细的答案，请向我们展示基准代码。
查看 ArrayList.removeAll() (OpenJDK7-b147) 的源代码，它似乎委托给了一个名为 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 等会很有趣
性能差异的原因是内存访问模式：访问内存中连续的元素比进行随机内存访问更快（由于内存预取、cpu 缓存等）
当您最初填充集合时，您会在内存中按顺序创建所有元素，因此当您遍历它（foreach、removeAll 等）时，您正在访问缓存友好的连续内存区域。当你打乱集合时——元素在内存中保持相同的顺序，但指向这些元素的指针不再是相同的顺序，所以当你遍历集合时，你将访问例如第 10 个、第 1 个、然后是第 5 个元素，它对缓存非常不友好并且会破坏性能。
您可以查看此问题，其中更详细地显示了此效果：
Why filtering an unsorted list is faster than filtering a sorted list
由于提问者没有提供任何示例代码，并且对评论和答案中提到的基准测试一直有疑问，我创建了一个小测试，看看 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
我将在这里省略 这个 特定测试的代码，因为它也受到质疑（顺便说一下，这是完全合理的！发布了很多废话在网上...）。
所以我做了进一步的测试，我将在此处提供代码。
这也不能被视为明确的答案。但我试图调整测试，以便它们至少提供一些强有力的 证据 证明性能下降的 原因 确实是 （+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 之间的值，可以限制交换元素的数量，从而限制列表的打乱程度。 （当然，这更像是 "pragmatic"，因为考虑到 "shuffledness" 的不同可能（统计）措施，有不同的实施方式可供选择）。
代码如下所示：
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 %d\n",
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
可以清楚地看到，时间基本上随着打乱线性增加。
当然，这一切仍然不是证明，但至少证据证明是正确的。
比较 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 中查找连续值比查找 运行dom 值更快.
现在另一个：
02311 011% sorted ArrayList, shuffled ArrayList
01401 006% sorted ArrayList, sorted ArrayList
现在这表明排序后的 ArrayList 中的查找（对左侧列表的每个元素使用 contains() 调用）比打乱后的列表中的查找更快。现在，如果我们可以利用它已排序并使用二进制搜索这一事实，那将非常容易，但我不这样做。
这两个结果对我来说都很神秘。我无法通过查看代码或我的数据结构知识来解释它们。它与处理器缓存访问模式有什么关系吗？ JIT 编译器是否优化了一些东西？但如果是这样，哪个？我连续进行了几次热身和 运行 测试，但也许我的基准测试存在根本问题？
Now I know that micro-benchmarks are difficult to do right, and I won’t look at a few milliseconds difference, but I believe my results to be valid, since I ran them repeatedly and they are very reproducible.
这并不能说服我。有缺陷的基准测试的行为可以 100% 重现。
我怀疑......事实上......你的基准测试中的一个或多个缺陷>>是<<导致你奇怪结果的原因。经常是。
... but perhaps there is a fundamental problem with my benchmark?
是（海事组织）。
如果您需要更详细的答案，请向我们展示基准代码。
查看 ArrayList.removeAll() (OpenJDK7-b147) 的源代码，它似乎委托给了一个名为 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 等会很有趣
性能差异的原因是内存访问模式：访问内存中连续的元素比进行随机内存访问更快（由于内存预取、cpu 缓存等）
当您最初填充集合时，您会在内存中按顺序创建所有元素，因此当您遍历它（foreach、removeAll 等）时，您正在访问缓存友好的连续内存区域。当你打乱集合时——元素在内存中保持相同的顺序，但指向这些元素的指针不再是相同的顺序，所以当你遍历集合时，你将访问例如第 10 个、第 1 个、然后是第 5 个元素，它对缓存非常不友好并且会破坏性能。
您可以查看此问题，其中更详细地显示了此效果： Why filtering an unsorted list is faster than filtering a sorted list
由于提问者没有提供任何示例代码，并且对评论和答案中提到的基准测试一直有疑问，我创建了一个小测试，看看 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
我将在这里省略 这个 特定测试的代码，因为它也受到质疑（顺便说一下，这是完全合理的！发布了很多废话在网上...）。
所以我做了进一步的测试，我将在此处提供代码。
这也不能被视为明确的答案。但我试图调整测试，以便它们至少提供一些强有力的 证据 证明性能下降的 原因 确实是
首先：我知道编写微基准测试时可能存在的许多陷阱（根据他的陈述，提问者也是如此）。但是，我知道没有人会相信 谎言 基准测试，即使它是完全合理的，除非它是使用适当的微基准测试工具执行的。因此，为了表明随机列表的性能低于排序列表的性能，我创建了这个简单的 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 之间的值，可以限制交换元素的数量，从而限制列表的打乱程度。 （当然，这更像是 "pragmatic"，因为考虑到 "shuffledness" 的不同可能（统计）措施，有不同的实施方式可供选择）。
代码如下所示：
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 %d\n",
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
可以清楚地看到，时间基本上随着打乱线性增加。
当然，这一切仍然不是证明，但至少证据证明