4核CPU禁用超线程时，并行快排8线程为何比4线程更快？

问题背景 #

在禁用超线程的4核CPU上测试并行快速排序，按常规认知CPU密集型任务的最优线程数等于核心数，否则会产生线程上下文切换开销，但测试结果显示8线程的排序速度反而比4线程更快，需解释该现象。

测试结果 #

手动测试结果 #

CPU Cores : 4

10 tests ran with 1 thread(s), on an array of size : 30000000. Sorting process took on avg for each test : 3579
10 tests ran with 2 thread(s), on an array of size : 30000000. Sorting process took on avg for each test : 2458
10 tests ran with 4 thread(s), on an array of size : 30000000. Sorting process took on avg for each test : 1230
10 tests ran with 8 thread(s), on an array of size : 30000000. Sorting process took on avg for each test : 1030
10 tests ran with 16 thread(s), on an array of size : 30000000. Sorting process took on avg for each test : 1026
10 tests ran with 32 thread(s), on an array of size : 30000000. Sorting process took on avg for each test : 1036
10 tests ran with 64 thread(s), on an array of size : 30000000. Sorting process took on avg for each test : 1094

JMH测试结果（3000万样本数组，10次迭代） #

Benchmark            Mode  Cnt     Score     Error  Units
Sample.run16Threads  avgt   10  1057.336 ±  38.845  ms/op
Sample.run1Thread    avgt   10  3385.159 ±  15.619  ms/op
Sample.run2Threads   avgt   10  1809.542 ±  23.794  ms/op
Sample.run32Threads  avgt   10  1133.388 ±  86.976  ms/op
Sample.run4Threads   avgt   10  1120.386 ± 113.688  ms/op
Sample.run64Threads  avgt   10  1546.910 ± 488.938  ms/op
Sample.run8Threads   avgt   10  1031.181 ±  52.650  ms/op

代码实现 #

ParallelQuickSort类 #

public class ParallelQuickSort extends RecursiveAction {
    private final int left;
    private final int right;
    private final int[] arr;

    public ParallelQuickSort(int left, int right, int[] arr) {
        this.left = left;
        this.right = right;
        this.arr = arr;
    }

    private int partition(int[] arr, long pivot) {
        int leftPtr = left - 1;
        int rightPtr = right;

        while ( true ) {
            while ( arr[++leftPtr] < pivot ) ;
            while ( rightPtr > 0 && arr[--rightPtr] > pivot ) ;

            if ( leftPtr >= rightPtr ) {
                break;
            } else {
                swap( arr, leftPtr, rightPtr );
            }
        }
        swap( arr, leftPtr, right );
        return leftPtr;
    }

    private void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    @Override
    protected void compute() {
        if ( right - left <= 0 ) {
            return;
        }
        long pivot = arr[right];
        int partition = partition( arr, pivot );
        ForkJoinTask.invokeAll( createSubTasks( partition ) );
    }

    private List<ParallelQuickSort> createSubTasks(int partition) {
        return List.of(
                new ParallelQuickSort( left, partition - 1, arr ),
                new ParallelQuickSort( partition + 1, right, arr )
        );
    }
}

Main类 #

public class Main {
    public static void main(String[] args) {
        SecureRandom secureRandom = new SecureRandom();
        int[] arr = IntStream.range( 0, 30_000_000 ).map( i -> secureRandom.nextInt( 200_000 ) ).toArray();
        int tests = 10;

        System.out.println( "CPU Cores : " + Runtime.getRuntime().availableProcessors() + "\n" );
        for ( int threads = 1; threads <= 64; threads *= 2 ) {
            long time = 0;
            for ( int i = 0; i < tests; ++i ) {
                int[] sample = Arrays.copyOfRange( arr, 0, arr.length );
                ForkJoinPool forkJoinPool = new ForkJoinPool(threads);
                long start = System.currentTimeMillis();
                forkJoinPool.invoke( new ParallelQuickSort( 0, arr.length - 1, sample ) );
                long end = System.currentTimeMillis();
                forkJoinPool.shutdown();
                time += end - start;
                //System.out.println( isSorted( sample ) );
            }
            System.out.println( tests + " tests ran with " + threads +
                    " thread(s), on an array of size : " + arr.length + ". Sorting process took on avg for each test : " + time / tests );
        }
    }

    private static boolean isSorted(int[] arr) {
        boolean isSorted = true;
        for ( int i = 0; i < arr.length - 1; ++i ) {
            if ( arr[i] > arr[i + 1] ) {
                isSorted = false;
                break;
            }
        }
        return isSorted;
    }
}

原因解释 #

• ForkJoin工作窃取适配任务不均：并行快速排序通过递归拆分任务，而快速排序的分区结果天然不均匀——部分子任务数据量小、执行快，部分则耗时更久。当线程数略多于核心数时，空闲线程可通过工作窃取机制从忙碌线程的任务队列中获取未执行的子任务，避免核心闲置，提升整体CPU利用率。4线程时，若某个核心的线程提前完成任务，可能因无任务可窃取导致核心短暂空闲。
• 内存延迟的掩盖：快速排序虽以CPU计算为主，但需频繁访问数组内存，存在内存加载延迟。当线程数多于核心数时，CPU可在某线程等待内存数据的间隙调度其他线程执行计算，利用等待时间完成更多工作，抵消内存延迟带来的效率损失。
• 测试误差的影响：从JMH结果看，4线程与8线程的性能差值处于误差重叠范围（4线程误差±113ms，8线程±52ms），实际性能差距可能远小于测试显示的数值，部分差异源于测试过程中的系统波动。

内容的提问来源于stack exchange，提问作者Alexander Argyriou