In programming, checking for prime numbers is a classic algorithmic problem. For small datasets, a traditional serial loop is sufficient; however, when the dataset scales to hundreds of thousands or more, improving computational efficiency becomes critical.
This article uses Go to compare the performance differences between a “traditional serial implementation” and a “multi-goroutine concurrent implementation” when counting prime numbers in the range of 1 to 200,000, and provides an in-depth analysis of the underlying principles.
1. Requirements and Analysis
Objective:
Count all prime numbers between 1 and 200,000, and compare the execution time of different implementation approaches.
1. Traditional approach (serial):
Use a for loop to iterate from 1 to 200,000. Call the isPrime function to check each number. In this approach, all calculations execute sequentially in the main thread, unable to leverage the advantages of a multi-core CPU.
2. Concurrent approach (parallel – task queue pattern):
The core idea is “dynamic load balancing.” Instead of assigning a fixed range of numbers to each goroutine, we set up a “task channel.”
Architecture design:
– Task producer: Start a goroutine responsible for sequentially putting numbers from 1 to 200,000 into intChan (the task channel).
– Task consumers (multiple Goroutines): Start 2 Goroutines (or adjust based on the number of CPU cores). These goroutines do not care about which segment of numbers they process; they only “grab” tasks from intChan. Whichever goroutine is idle takes the next number from the channel for evaluation.
– Result collection (primeChan): If a goroutine determines that the current number is prime, it writes it to primeChan.
– Synchronization control (exitChan): When all computing goroutines finish processing all tasks in the channel, they notify the main thread that the counting is complete.
The benefit of this pattern is that if checking a particular number is especially time-consuming, it will not block other goroutines. Other goroutines continue to take new tasks from the channel, achieving true dynamic load balancing.
2. Code Implementation Comparison
1. Traditional serial implementation (goroutine-apply02/main.go)
This implementation is very straightforward:
package main
import (
"fmt"
"time"
)
func main() {
start := time.Now().Unix()
for num := 1; num <= 200000; num++ {
flag := true //假设是素数
//判断num是不是素数
for i := 2; i < num; i++ {
if num%i == 0 { //说明该num不是素数
flag = false
break
}
}
if flag {
//将这个数就放入到primeChan
//primeChan<- num
//将结果输出
//fmt.Printf("素数=%d\n", num)
}
}
end := time.Now().Unix()
fmt.Println("普通的方法耗时=", end-start)
}
2. Multi-goroutine concurrent implementation (goroutine-apply/main.go)
The concurrent implementation uses Channels for task distribution:
package main
import (
"fmt"
"time"
)
// 向 intChan 放入 1-200000 个数
func putNum(intChan chan int) {
for i := 1; i <= 200000; i++ {
intChan <- i
}
//关闭intChan
close(intChan)
}
// 从 intChan取出数据，并判断是否为素数,如果是，就放入到 primeChan
func primeNum(intChan chan int, primeChan chan int, exitChan chan bool) {
// 使用 for 循环
// var num int
var flag bool //
for {
//time.Sleep(time.Millisecond * 10)
num, ok := <-intChan //intChan 取不到..
if !ok {
break
}
flag = true //假设是素数
//判断num是不是素数
for i := 2; i < num; i++ {
if num%i == 0 { //说明该num不是素数
flag = false
break
}
}
if flag {
//将这个数就放入到primeChan
primeChan <- num
}
}
fmt.Println("有一个primeNum 协程因为取不到数据，退出")
//这里我们还不能关闭 primeChan
//向 exitChan 写入true
exitChan <- true
}
func main() {
intChan := make(chan int, 1000)
primeChan := make(chan int, 20000) //放入结果
//标识退出的管道
exitChan := make(chan bool, 2) // 2个
start := time.Now().Unix()
//开启一个协程，向 intChan 放入 1-200000 个数
go putNum(intChan)
//开启4个协程，从 intChan 取出数据，并判断是否为素数,如果是，就
//放入到 primeChan
for i := 0; i < 2; i++ {
go primeNum(intChan, primeChan, exitChan)
}
//这里我们主线程，进行处理
//直接
go func() {
for i := 0; i < 2; i++ {
<-exitChan
}
end := time.Now().Unix()
fmt.Println("使用协程耗时=", end-start)
//当我们从 exitChan 取出了4个结果，就可以放心的关闭 prprimeChan
close(primeChan)
}()
//遍历我们的 primeChan ,把结果取出
for {
_, ok := <-primeChan
if !ok {
break
}
//将结果输出
//fmt.Printf("素数=%d\n", res)
}
fmt.Println("main线程退出")
}
3. Performance Test Results
In my test environment (2-core CPU), the results for counting primes from 1 to 200,000 are as follows: see Figure 1.
– Traditional serial implementation: takes about 25 seconds.
– Multi-goroutine concurrent implementation: takes about 12 seconds.
As you can see, the concurrent implementation improves efficiency by about 50%. Theoretically, on a 4-core CPU, the estimated time would be around 6 seconds.
4. In-Depth Analysis: Why is Concurrency Faster?
1. Dynamic task distribution:
As you noted, the goroutines related to primeNum run concurrently. They compete for tasks collectively through for num := range intChan. This means that if the CPU has two cores, two goroutines are computing in parallel at the same time. Once a goroutine finishes checking a number, it immediately fetches the next one from the channel without waiting for a specific “range” to finish.
2. CPU core utilization:
In serial mode, only one core runs at full speed. In concurrent mode, the Go runtime scheduler maps these 2 Goroutines onto available operating system threads, allowing both cores to participate in the prime-checking computation simultaneously and significantly reducing total wait time.
3. Synchronization role of Channels:
Here, intChan acts as a “task pool.” It decouples task production from consumption. Regardless of whether the producer is fast or slow, consumers process available tasks as quickly as possible. Meanwhile, exitChan ensures that the main thread only performs the final count after all subtasks are truly complete, preventing data omission.
5. Summary and Recommendations
From this prime-counting case study, we can draw the following conclusions:
1. Concurrency is suitable for splitting CPU-intensive tasks: For a large number of independent computational tasks, leveraging multi-core advantages can significantly reduce total execution time.
2. “Task queues” are more flexible than “static sharding”: Distributing tasks via Channels can automatically handle uneven loads, resulting in better code scalability.
3. Channels are the cornerstone of concurrency safety: Proper use of Channels can avoid complex lock operations, making concurrent code more concise and readable.
In actual development, when encountering similar large-scale data processing scenarios, consider trying Go’s concurrency model—it often delivers unexpected performance gains.