为什么过滤流比简单返回子列表的迭代代码更快？

Question

public static final int N = 50000000;

static List<Integer> sourceList = new ArrayList<>();

static {
  for (int i = 0; i < N; i++) {
    sourceList.add(i);
  }
}

@Benchmark
public List<Pair<Integer, Integer>> vanilla() {
   List<Pair<Integer, Integer>> collect1 = 
   sourceList.stream()
     .map(integer -> Pair.of(integer, integer))
     .collect(Collectors.toList());
   return collect1.subList(1000, 100000);
}

@Benchmark
public List<Pair<Integer, Integer>> stream() {
  return sourceList.stream()
    .map(value -> Pair.of(value, value))
    .filter(value -> value.getLeft() > 1000 && value.getLeft() < 100000)
    .collect(Collectors.toList());
}

Benchmark     Mode  Cnt    Score   Error  Units
Test.stream   avgt   20    9.867 ± 0.218  ns/op
Test.vanilla  avgt   20  183.304 ± 8.550  ns/op

Answer 1

很可能是因为第一个元素必须填充50000000个元素的整个列表，这涉及到分配更多的内存，每次达到容量时都要复制列表使用的内部数组。

第二个只需要创建99000个元素的列表，因此分配的内存更少，内部数组的副本也更少。

一个更快的解决方案是在映射之前进行过滤，从而避免无用的装箱和创建对。当然，限制到10万也会更快。