为什么要过滤一个流比仅仅返回一个子列表的迭代代码更快？

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 

我使用JMH运行测试，我不明白结果。我想通过添加将Integer值封装在Pair中的映射函数会强制流创建所有新对象，以将它们传递给过滤器方法，然后提取Pair的左边部分进行比较。对于我来说，这听起来比另一种没有过滤的方法更加密集，结果只是原来的一个子列表，因此没有遍历整个列表。

我失去了一些东西在这里？

Answer 1

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

第二个只需创建99000个元素的列表，从而分配更少的内存，并减少内部数组的副本。

甚至更​​快的解决方案是在映射之前进行过滤，从而避免无用的装箱和创建对。限制到100,000人当然也会更快。

Answer 2

性能问题不是subList的问题，它确实简单地包装了主要List。

和ArrayList将重置容量&将元素复制到新的数组中重复需要添加更多元素。 vanilla使用更大的内存大小来添加50000000元素。所以它比stream慢，因为stream仅添加[1000..100000]元素。

以下部分是ArrayList类需要扩展容量，更多元素添加到ArrayList结果更ensureCapacityInternal方法调用：

private void ensureCapacityInternal(int minCapacity) { 
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
     minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 
    } 

    ensureExplicitCapacity(minCapacity); 
} 

也许以下版本vanilla会比stream快，但仍然使用更大的内存大小：

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