結論

parallelStream() によってJavaプログラムは10倍速くなる可能性がある

環境

CPU：Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz、2208 Mhz、6 個のコア、12 個のロジカルプロセッサ
メモリ：16GB
Java：Amazon Corretto-11.0.3.7.1

検証内容

検証用コード

Main.java

import java.util.List;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) {
		List<Integer> n1 = new ArrayList<>();
		List<Integer> n2 = new ArrayList<>();

		for(int i = 0; i < 500; i++) {
			n1.add(i);
			n2.add(i);
		}

		long s1 = System.currentTimeMillis();
		n1.stream().forEach(i -> { try { Thread.sleep(10); } catch(Exception e) { e.printStackTrace(); } });
		long t1 = System.currentTimeMillis();

		long s2 = System.currentTimeMillis();
		n2.parallelStream().forEach(i -> { try { Thread.sleep(10); } catch(Exception e) { e.printStackTrace(); } });
		long t2 = System.currentTimeMillis();

		System.out.printf("n1 exec time: %d [ms]\n", t1 - s1);
		System.out.printf("n2 exec time: %d [ms]\n", t2 - s2);
	}
}

取り立てて解説する点はあまりないです。n1 は順次ストリームで、 n2 は並列ストリームで500回 Thread.sleep(10) を呼び出しています。try-catchしているのは Thread.sleep() の検査例外に対応するためです。forEach の中のiは虚空に消えています。

実行結果

n1 exec time: 5298 [ms]
n2 exec time: 505 [ms]

n2 は n1 に比べて10倍以上速くなってます！
n1 は10ms × 500回の結果が如実に現れていますね。

補足

公式ドキュメントによると、デフォルトの並列スレッド数は、コンピュータで利用できるプロセッサの数と等しいそうです。

For applications that require separate or custom pools, a ForkJoinPool may be constructed with a given target parallelism level; by default, equal to the number of available processors.

並列ストリームでの実行時間が順次ストリームのものの1/10以下になっているところを見るに、物理プロセッサ数ではなく論理プロセッサ数がデフォルト値として適用されているようですね。
「10倍速くなる」...っておま環じゃねーか！！　という大変もっともなツッコミはあると思いますが、最近のPCなら大抵8論理プロセッサくらいはあると思うので許してください。

注意

各スレッドで共通して参照しているオブジェクトを更新したり削除したりする操作は、基本的にしないほうがいいです(Listに対するaddなど)。