Java多线程快速排序CPU利用率无法达100%问题排查求助

Let's walk through the issues in your code that are holding back CPU utilization, then fix them step by step:

1. You're Creating Way Too Many Threads (And Paying a Huge Overhead) #

Right now, every time you split the array, you spawn two new threads—even for tiny subarrays (like a few hundred elements). Thread creation isn't free: it takes time to allocate stack space, register the thread with the OS, and handle scheduling. For small arrays, the time spent creating threads is way longer than the time spent sorting the elements themselves.

Worse, having hundreds or thousands of threads running at once forces your CPU to spend most of its time switching between threads (context switching) instead of actually doing sorting work. That's why your CPU is stuck at 40%—it's busy juggling threads, not computing.

2. You're Not Waiting for Threads to Finish #

Your main thread starts the initial sort thread and immediately exits. While the JVM will keep running non-daemon threads, you have no way to confirm when sorting finishes, and the unregulated thread spawning leads to chaotic scheduling that hurts efficiency.

3. No Threshold for Single-Threaded Sorting #

Multi-threading only makes sense for large chunks of work. For small subarrays, single-threaded sorting (even a simple insertion sort!) is faster because you avoid all the thread overhead.

Fixed Code Example #

Here's how to adjust your code to fix these issues:

First, Update the SortThread Class #

We'll add a threshold for single-threaded sorting, wait for child threads to finish, and avoid spawning threads for tiny arrays:

public class SortThread implements Runnable {
    private int[] arr;
    private int start;
    private int end;
    // Threshold: use single-threaded sort for subarrays smaller than this
    private static final int SINGLE_THREAD_THRESHOLD = 1000;

    public SortThread(int[] arr, int start, int end) {
        this.arr = arr;
        this.start = start;
        this.end = end;
    }

    @Override
    public void run() {
        // Use single-threaded sort for small subarrays
        if (end - start < SINGLE_THREAD_THRESHOLD) {
            quickSortSingleThread(arr, start, end);
            return;
        }

        if (start < end) {
            int partitionIndex = partition(arr, start, end);
            SortThread sortThreadLeft = new SortThread(arr, start, partitionIndex - 1);
            SortThread sortThreadRight = new SortThread(arr, partitionIndex + 1, end);
            Thread sortLeft = new Thread(sortThreadLeft);
            Thread sortRight = new Thread(sortThreadRight);
            
            sortLeft.start();
            sortRight.start();
            
            // Wait for child threads to finish before exiting this thread
            try {
                sortLeft.join();
                sortRight.join();
            } catch (InterruptedException e) {
                // Restore interrupt status if interrupted
                Thread.currentThread().interrupt();
            }
        }
    }

    // Single-threaded quicksort for small arrays
    private void quickSortSingleThread(int[] arr, int start, int end) {
        if (start < end) {
            int partitionIndex = partition(arr, start, end);
            quickSortSingleThread(arr, start, partitionIndex - 1);
            quickSortSingleThread(arr, partitionIndex + 1, end);
        }
    }

    private int partition(int arr[], int begin, int end) {
        int pivot = arr[end];
        int i = (begin - 1);
        for (int j = begin; j < end; j++) {
            if (arr[j] <= pivot) {
                i++;
                int swpTemp = arr[i];
                arr[i] = arr[j];
                arr[j] = swpTemp;
            }
        }
        int swapTemp = arr[i + 1];
        arr[i + 1] = arr[end];
        arr[end] = swapTemp;
        return i + 1;
    }
}

Then, Update the Main Class #

Wait for the main sort thread to finish so you know when sorting is done:

import java.util.Random;

public class Main {
    public static void main(String[] args) throws InterruptedException {
        int[] arr;
        Random random = new Random();
        arr = new int[53000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt();
        }
        
        SortThread sortThread = new SortThread(arr, 0, arr.length - 1);
        Thread threadSort = new Thread(sortThread);
        threadSort.start();
        
        // Wait for the main sort thread to complete
        threadSort.join();
        System.out.println("Sorting finished successfully!");
    }
}

Even Better: Use a Thread Pool #

For more control over thread count (matching your CPU core count), replace manual thread creation with an ExecutorService:

// Update SortThread to accept an ExecutorService
public class SortThread implements Runnable {
    private int[] arr;
    private int start;
    private int end;
    private ExecutorService executor;
    private static final int SINGLE_THREAD_THRESHOLD = 1000;

    public SortThread(int[] arr, int start, int end, ExecutorService executor) {
        this.arr = arr;
        this.start = start;
        this.end = end;
        this.executor = executor;
    }

    @Override
    public void run() {
        if (end - start < SINGLE_THREAD_THRESHOLD) {
            quickSortSingleThread(arr, start, end);
            return;
        }

        if (start < end) {
            int partitionIndex = partition(arr, start, end);
            // Submit child tasks to the thread pool
            executor.submit(new SortThread(arr, start, partitionIndex - 1, executor));
            executor.submit(new SortThread(arr, partitionIndex + 1, end, executor));
        }
    }

    // quickSortSingleThread and partition methods remain the same...
}

And update Main to use the thread pool:

import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class Main {
    public static void main(String[] args) throws InterruptedException {
        int[] arr;
        Random random = new Random();
        arr = new int[53000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt();
        }
        
        // Create a thread pool with size matching your CPU core count
        ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
        executor.submit(new SortThread(arr, 0, arr.length - 1, executor));
        
        // Shutdown the pool and wait for all tasks to finish
        executor.shutdown();
        executor.awaitTermination(1, TimeUnit.HOURS); // Adjust timeout as needed
        System.out.println("Sorting finished successfully!");
    }
}

Why This Works #

• Threshold for single-threaded sorting: Avoids thread overhead for small arrays where it doesn't make sense.
• Waiting for child threads: Prevents spawning thousands of threads at once, keeping the thread count manageable.
• Thread pool: Limits threads to your CPU core count, so each core has exactly one thread to work on—no wasted context switching, and your CPU will hit near 100% utilization.

内容的提问来源于stack exchange，提问作者Farrukh Nabiyev