基于Golang的并行素数筛算法实现

本文深入剖析了在Go语言中实现并行素数筛（Sieve算法）时常见的性能陷阱与工程实践：当未加约束地滥用goroutine，筛至10⁶即因协程泛滥导致调度器崩溃、内存暴涨而卡死；真正高效的并发方案在于“分段处理+管道限流”，即预筛质数表、按固定区间分配任务、用原子操作（atomic.OrUint32+位图）替代锁写入、避免高频传单值channel，并针对ARM64/wasm等受限平台主动降并发、调大分段、禁用阻塞操作——核心洞见是：Go并发的威力不在于数量，而在于让每个goroutine承载足够计算密度、避开调度与内存瓶颈，在稀疏负载下实现真正可伸缩的并行。

Go 里用 goroutine 实现 Sieve 算法，为什么筛到 10⁶ 就卡死？

因为没控制 goroutine 数量，筛到中间会起几万个协程，调度器扛不住，内存暴涨后被系统 kill。Go 的并发不是“越多越好”，而是“按需分段+管道限流”。

实操建议：

• 把 [2, n] 拆成固定大小的段（比如每段 10000），每个段一个 goroutine 负责标记合数
• 用 sync.WaitGroup 等待所有段处理完，别用无缓冲 channel 做同步——容易死锁
• 避免让每个质数都起一个 goroutine 去筛（经典错误：为 2、3、5…各自开 goroutine），这会导致 O(n/2 + n/3 + …) 级别的 goroutine 泛滥

channel 传素数还是传区间？选错就拖慢 3 倍

传单个 int 素数看似直观，但高频小数据写 channel 开销远超计算本身；传区间（如 struct{ from, to int }）才能压住调度成本。

实操建议：

• 主 goroutine 预生成质数表（用基础版 Sieve 筛出 ≤ √n 的质数），然后分发给工作 goroutine 处理各自区间
• 工作 goroutine 只读不写 channel，结果通过切片指针或预分配数组回填，避免 channel 串行化瓶颈
• 如果硬要用 channel 汇总结果，务必用带缓冲的：ch := make(chan int, 1024)，否则一卡全卡

为什么 atomic.Bool 比 mutex 更适合标记合数数组？

因为筛法本质是大量并发写同一块布尔数组（isComposite[i]），而 atomic.StoreBool 比 mutex.Lock() 快 5–10 倍，且无锁竞争风险。

实操建议：

• 用 []uint32 模拟位图（每 bit 表示一个数），配合 atomic.OrUint32 做原子置位，省内存又快
• 别用 []bool —— Go 里它不是单字节对齐，atomic 操作会 panic
• 若必须用 []bool，改用 sync.Mutex 保护整段（比如每 64 个数一个锁），别锁整个数组

交叉编译到 ARM64 或 wasm 时，goroutine 数量要调低

ARM64 设备内存小、调度器更敏感；wasm 甚至不支持真正的 OS 线程，goroutine 是纯用户态模拟，起太多直接爆栈。

实操建议：

• 用 runtime.GOMAXPROCS(2) 强制限制并发度，别依赖默认值
• 在 init() 里检查 runtime.GOARCH，ARM64/wasm 下自动把分段大小翻倍、goroutine 数减半
• wasm 目标下禁用所有 time.Sleep 和阻塞式 channel 操作，它们不会真正休眠，只会空转耗尽配额

事情说清了就结束。真正难的不是并发模型，而是怎么让每个 goroutine 干够活、又别抢着干——筛法里的“活”是稀疏的（大部分数早被筛掉），得靠预判质数分布来平衡负载，这点常被忽略。

今天关于《基于Golang的并行素数筛算法实现》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！