多线程实现埃氏筛时核心数增多反而变慢的问题求助

这问题我之前在优化素数筛的时候也踩过坑！核心数加了反而跑不快，本质是共享资源竞争和任务粒度不合理在拖后腿，咱们一步步拆解解决：

为什么核心数越多越慢？ #

1. 共享数组的竞争开销爆炸 #

你用的AtomicBoolean数组（或普通数组加锁）是所有线程的竞争热点——每个线程标记非素数时都要读写同一个数组，核心线程越多，缓存一致性协议的同步开销、锁竞争的阻塞时间就越大，直接抵消了并行计算的收益，甚至让整体速度比单线程还慢。

2. 任务粒度太细导致调度过载 #

你给每个i单独开一个任务，如果n不算特别大，每个任务的执行时间极短（比如标记几个倍数就结束了），线程池的调度开销（线程切换、任务队列操作）会远远超过并行带来的效率提升，核心数越多，调度的额外开销就越高。

3. 线程池参数设置不合理 #

你的线程池核心数6、最大10，还配了容量为n的ArrayBlockingQueue——非核心线程的创建销毁、队列的频繁入队出队都会带来额外开销，而且这种场景下非核心线程完全没必要，反而增加复杂度。

具体解决办法 #

1. 合并任务，增大粒度 #

不要给每个i单独开任务，而是把2到sqrt(n)的范围拆成和核心数匹配的大块，每个线程处理一个区间内的所有i的标记工作，大幅减少任务调度次数：

// 获取CPU核心数，以此为基准拆分任务
int coreCount = Runtime.getRuntime().availableProcessors();
int sqrtN = (int) Math.sqrt(n);
int interval = sqrtN / coreCount;

// 用固定大小线程池更合适，避免非核心线程的开销
ExecutorService executor = Executors.newFixedThreadPool(coreCount);

for (int j = 0; j < coreCount; j++) {
    int start = 2 + j * interval;
    // 最后一个区间覆盖到sqrt(n)
    int end = (j == coreCount - 1) ? sqrtN : start + interval;
    executor.execute(new BatchPrimeTask(start, end, n, list));
}
executor.shutdown();
executor.awaitTermination(1, TimeUnit.HOURS);

// 批量任务的run方法
class BatchPrimeTask implements Runnable {
    private int start, end, n;
    private boolean[] list; // 换成普通boolean数组，配合后续分段锁优化

    public BatchPrimeTask(int start, int end, int n, boolean[] list) {
        this.start = start;
        this.end = end;
        this.n = n;
        this.list = list;
    }

    @Override
    public void run() {
        for (int i = start; i <= end; i++) {
            if (list[i]) { // 确认当前i是素数
                // 标记i的所有倍数
                for (int k = i * i; k < n; k += i) {
                    list[k] = false;
                }
            }
        }
    }
}

2. 减少共享资源竞争：分段锁或数组拆分 #

如果还是用共享数组，别用全局锁或者AtomicBoolean，改用分段锁：把数组分成若干段，每段对应一把锁，线程处理某段的倍数时只需要获取对应段的锁，不同段的线程互不干扰：

// 比如每1024个元素为一段，创建对应的锁数组
int segmentSize = 1024;
Lock[] locks = new Lock[(n + segmentSize - 1) / segmentSize];
for (int i = 0; i < locks.length; i++) {
    locks[i] = new ReentrantLock();
}

// 在标记倍数时，获取对应段的锁
int segmentIndex = k / segmentSize;
locks[segmentIndex].lock();
try {
    list[k] = false;
} finally {
    locks[segmentIndex].unlock();
}

更彻底的方式是拆分数组：每个线程维护自己的局部数组，处理完后再合并到全局数组，完全避免竞争，但需要额外的合并逻辑，适合超大n的场景。

3. 改用分段筛（Segmented Sieve）优化并行效率 #

如果n特别大（比如超过1e8），普通埃氏筛的内存开销会很高，而且共享数组的竞争无法避免。这时候可以用分段筛：把整个范围分成多个小的段，每个线程处理一段，先预先生成sqrt(n)以内的素数，再用这些素数去标记每个段里的非素数。这种方式每个线程的工作内存局部性更好，缓存命中率高，几乎没有竞争。

4. 加个阈值判断：小n用单线程 #

当n比较小（比如小于1e6），单线程的缓存局部性优势完全盖过多线程的并行收益，这时候直接用单线程筛法反而更快。可以加个判断：

if (n < 1_000_000) {
    // 单线程埃氏筛
    singleThreadSieve(n, list);
} else {
    // 多线程版本
    multiThreadSieve(n, list);
}

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