なぜストリームを単にサブリストを返す反復コードより速くフィルタリングするのですか？

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値をラップするマッピング関数を追加することで、ストリームをすべての新しいオブジェクトを作成してフィルタメソッドに渡し、比較のためにペアの左部分を抽出するように強制すると考えました。それはフィルタリングがない他のアプローチよりも私にはもっと集中的に聞こえ、その結果は元のリストのサブリストに過ぎず、したがってリスト全体を通ることはありません。

ここに何か不足していますか？

Answer 1

おそらく最初のものは50000000要素の全リストを埋めなければならないからです。これは、容量が増えるたびにリストで使用される内部配列のコピーを複数作成することです。

2番目の要素は99000要素のリストを作成するだけで、メモリの割り当てが少なくなり、内部配列のコピーが少なくなります。

さらに高速な解決策は、マッピングする前にフィルタリングして、無駄なボクシングとペアの作成を避けることです。もちろん、10万に制限することもより速くなります。

Answer 2

パフォーマンスの問題はsubListさんの問題ではありません。実際には、メインListを実際に包みます。

ArrayListは、容量を個のコピー要素を必要に応じて新しい配列にリセットし、より多くの要素を追加することができます。 vanillaは、50000000要素を追加するためにより大きなメモリサイズを使用します。 streamが[1000..100000]要素のみを追加して以来、それはstreamより遅くなります。

次のセクションでは、必要として容量を拡張するArrayListクラスで、より多くの要素がよりensureCapacityInternal方法でArrayList結果に追加呼び出す：

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); 
}