基于pthreads的Sieve of Eratosthenes并行化：执行时间结果解读求助

核心问题拆解 #

你的Intel i7-7500U是4核8线程（支持超线程），但并行筛法未体现性能提升、增加迭代次数也无明显变化，大概率是以下几类常见问题导致：

1. 任务划分不合理 #

埃氏筛的核心是标记非质数，若线程任务采用简单的区间均分，会出现严重负载不均：

• 小质数的倍数数量远多于大质数，负责处理小质数区间的线程会持续高负载，而处理大质数的线程早早闲置
• 最终整体执行时间受限于最忙的线程，和串行版本差异极小

2. 共享内存竞争与同步开销 #

若并行实现使用全局数组存储质数标记，且未做合理同步控制：

• 多个线程同时修改同一块内存区域，会触发大量缓存一致性开销（比如MESI协议的总线风暴），拖慢整体速度
• 若使用了全局锁，线程大部分时间都在等待锁释放，完全无法发挥并行优势，性能和串行版本基本一致

3. 任务粒度太小 #

如果给每个线程分配的任务量过小，线程创建、调度的开销会直接抵消并行带来的收益：

• 比如让线程每次仅标记一个质数的倍数，线程调度的耗时可能比实际计算时间还长
• 增加迭代次数只是重复相同的小粒度任务，开销占比依然很高，因此执行时间无明显变化

4. 超线程的局限性 #

i7-7500U的超线程是同一物理核上的两个逻辑线程，它们共享L1/L2缓存和执行单元：

• 对于计算密集型的筛法任务，超线程的加速比远低于物理核的线性增长（比如4核跑满可能接近4倍，但8线程可能仅能达到4.5倍左右）
• 若并行实现本身存在缺陷，超线程甚至可能带来负优化

排查与优化方向 #

代码层面检查 #

• 确认并行版是否实现了无锁或细粒度锁：比如让每个线程负责独立的质数标记任务，仅在收集最终质数结果时做同步
• 检查任务划分逻辑：放弃简单的区间均分，改用质数轮询分配（每个线程处理不同的质数，负载更均衡）

测试脚本优化 #

• 测试时关闭所有后台负载（浏览器、进程等），避免系统资源干扰计时结果
• 每个线程数重复测试5-10次取平均值，减少单次计时的误差

示例优化伪代码 #

将区间划分改为质数轮询分配，能有效均衡负载并减少内存竞争：

void* sieve_worker(void* arg) {
    int thread_id = *(int*)arg;
    int num_threads = *(int*)((int*)arg + 1);
    int n = *(int*)((int*)arg + 2);
    extern char* is_prime; // 全局标记数组，已初始化

    for (int p = 2 + thread_id; p * p <= n; p += num_threads) {
        if (is_prime[p]) {
            for (int i = p * p; i <= n; i += p) {
                is_prime[i] = 0;
            }
        }
    }
    pthread_exit(NULL);
}

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