Java性能:removeAll()上的搜索和删除速度

Question

我在比较< code>removeAll(集合的速度时获得了一些乐趣

让我们假设我有两个不太小的集合，比如100000个连续的整数元素，而且它们大部分重叠，例如，5000个在左边，而不是右边。现在我只需打电话：

left.removeAll(right);

当然，这一切都取决于左集合和右集合的类型。如果正确的集合是一个哈希图，那么它会非常快，因为这就是查找的地方。但仔细一看，我发现了两个我无法解释的结果。我尝试了所有的测试，既有排序的＜code＞ArrayList＜/code＞，也有重新排序的（如果重要的话，使用＜code＞Collections.shuffle（）＜/code>）。

第一个奇怪的结果是：

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

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

现在另一个：

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

现在，这表明在排序的< code>ArrayList中查找(对列表左边的每个元素使用< code>contains()调用)比在混排列表中更快。如果我们能利用它已经排序的事实，用一个二分搜索法，那就很容易了，但是我不这么做。

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

Answer 1

匿名用户

查看＜code＞ArrayList的源代码。removeAll（）（OpenJDK7-b147）它似乎委托给一个名为batchRemove（）<-code>的私有方法，如下所示：

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     }

它实际上在数组中循环，并有一堆＜code＞c。contains（）调用。基本上，对于排序数组来说，没有理由让迭代速度更快。

我同意StephenC对基准的怀疑，并且相信在深入研究缓存访问模式等之前仔细检查基准代码会更有成效。

此外，如果基准代码不是罪魁祸首，那么了解java版本和OS/arch等也会很有趣。

Answer 2

由于询问者没有提供任何示例代码，并且对评论和答案中提到的基准一直存在疑问，因此我创建了一个小测试，以查看当参数是混洗列表（而不是排序列表）时，

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都发布在网上...

所以我做了进一步的测试，我将在这里提供代码。

这也可能不被认为是一个明确的答案。但我试图调整测试，以便它们至少提供一些强有力的证据，证明性能降低的原因确实是斯维特林·扎列夫在他的回答中提到的（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 %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

我们可以清楚地看到，时间基本上随着洗牌而线性增加。

当然，这一切仍然不是一个证明，但至少证明了斯维特林·扎列夫的答案是正确的。

Answer 3

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

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

您可以查看此问题，其中更详细地可以看到此效果：为什么筛选未排序列表比筛选排序列表更快