<p>I know, concurrency is not parallel :) But I assumed Go routines would at least fill up available CPU cores. So made this little test on a Raspberry Pi 3 where I find primes in serial and using Go-Routines.</p>
<p>The latter is much slower - which caught me by surprise.</p>
<p>Just doing it in serial (primes from 1 to 1.6 million) took 5.6 seconds, whereas using Go routines took a whopping 13.8 seconds.</p>
<p>I see when running the program, the CPU meter do not budge much over 25% as well.</p>
<p>So I must have done something wrong somewhere!?</p>
<p><a href="https://github.com/rDybing/piPrime">source and more here</a></p>
<p>Any help figuring this out appreciated :)</p>
<hr/>**评论：**<br/><br/>faiface: <pre><p>I think the problem is that the sequential version uses the cache much better than the concurrent version (one local for-loop vs sending values here and there).</p>
<p>Try rewriting your code in such a way, that you fire up multiple goroutines, which won't actively communicate, instead, let each of them process a sub-interval of all of the numbers you want to check. This way, each goroutine will fully utilize cache and should achieve much better performance.</p>
<p>At the end, aggregate the results from each goroutine.</p></pre>nathankerr: <pre><p>It's pretty common for a concurrent implementation to slow things down. I wrote about just such an experience and then detailed how I used the tools provided by Go to speed it up: <a href="https://pocketgophers.com/concurrency-slower/">https://pocketgophers.com/concurrency-slower/</a></p>
<p>My first impression of your concurrent version is the channel operations you use are not needed. You would also probably get better performance if you used one fewer instance of isPrimeConc because primeConcurrent is also in a goroutine that has processing (sending and receiving) for every step.</p>
<p>I will be back in a bit with my own version.</p></pre>nathankerr: <pre><p>Since I wanted to use <a href="https://godoc.org/golang.org/x/perf/cmd/benchstat" title="benchstat" rel="nofollow">benchstat</a>, the functions being benchmarked needed to not output their progress (benchstat can’t parse the output if they do). So I moved the output and timing stuff to <code>main</code> and had the prime functions return the number of primes found.</p>
<p>I then found the minimal scalable unit (MSU) as described in the article and split the work apart in a similar way because the only interaction between the MSUs is the count of prime numbers found. I used the original <code>isPrime</code> for both the sequential and concurrent versions.</p>
<h2><code>piPrime.go</code></h2>
<pre><code>package main
import (
"fmt"
"math"
"runtime"
"sync"
"time"
)
// set to 1.6 million - not 16 million - to save some time when debugging
// I made this a global so the benchmarks use the same number
const countTo uint64 = 1600000
func main() {
fmt.Println("here we go. Ol'skool serial prime-finder")
start := time.Now()
primes := primeSequential(countTo)
fmt.Printf("%8d || time: %6.2f || primes: %d\n", countTo, time.Since(start).Seconds(), primes)
fmt.Println("and now the concurrent way!")
start = time.Now()
primes = primeConcurrent(countTo)
fmt.Printf("%8d || time: %6.2f || primes: %d\n", countTo, time.Since(start).Seconds(), primes)
}
func primeSequential(limit uint64) int32 {
var primeCount int32
for i := uint64(2); i < limit; i++ {
if isPrime(i) {
primeCount++
}
}
return primeCount
}
func primeConcurrent(limit uint64) int32 {
mu := &sync.Mutex{} // protects primeCount
var primeCount int32
wg := &sync.WaitGroup{}
nworkers := uint64(runtime.GOMAXPROCS(-1))
work := limit / nworkers
for i := uint64(0); i < nworkers; i++ {
begin := work * i
end := begin + work
switch i {
case 0:
// start at 2
begin = 2
case nworkers - 1:
// last worker picks up the slack
end = limit
}
wg.Add(1)
go func() {
defer wg.Done()
for i := begin; i < end; i++ {
if isPrime(i) {
mu.Lock()
primeCount++
mu.Unlock()
}
}
}()
}
wg.Wait()
return primeCount
}
func isPrime(number uint64) bool {
var i uint64
var s uint64
s = uint64(math.Sqrt(float64(number)))
if number > 2 && number%2 == 0 {
return false
}
for i = 3; i <= s; i += 2 {
if number%i == 0 {
return false
}
}
return true
}
</code></pre>
<h2><code>piPrime_test.go</code></h2>
<pre><code>package main
import "testing"
func BenchmarkPrimes(b *testing.B) {
for i := 0; i < b.N; i++ {
// primeSequential(countTo)
primeConcurrent(countTo)
}
}
</code></pre>
<h2>Benchmarks</h2>
<p>I ran the benchmarks with:</p>
<pre><code>go test -bench Primes -count 10 |tee concurrent.txt
</code></pre>
<p>Switching the comment in the benchmark and <code>tee</code>ing to the correct file for the version I wanted to run and ended up with:</p>
<pre><code>$ benchstat sequential.txt concurrent.txt
name old time/op new time/op delta
Primes-2 1.01s ± 1% 0.62s ± 1% -38.46% (p=0.000 n=9+8)
</code></pre>
<h2>Further Optimizations</h2>
<p>Optimizations I can think of (without having profiled them):</p>
<ul>
<li>workers should aggregate primes locally, then update <code>primeCount</code> once at the end; this should reduce mutex contention</li>
<li><code>isPrime</code> should calculate <code>Sqrt</code> after the even check is done</li>
</ul></pre>siritinga: <pre><p>Your problem is that you are feeding 4 values to 4 goroutines and then waiting for the reply to send other 4 values, starving the goroutines.</p>
<p>I've changed your code to reuse isPrime in both versions, creating a goroutine that feeds the prime goroutines and also using time.Time to compute durations.</p>
<p><a href="https://pastebin.com/2h4M2ViG" rel="nofollow">https://pastebin.com/2h4M2ViG</a></p>
<p>In my PC I can see a clear improvement for big values, however for small values the overhead of channels doesn't worth the effort of parallelizing.</p>
<p>Regards.</p></pre>Zy14rk: <pre><p>Thanks - that worked very nicely. Uploaded the new version to the repo with credit going to you where it is due :) </p>
<p>I got to remember that pattern of using go-routines. Very nice. Thanks again!</p></pre>joushou: <pre><p>I've left a comment elsewhere, but batching (split range in 4, instead of looping over it) and only sending primes back (with a "done" message at the end) would give a very drastic boost as well.</p></pre>joushou: <pre><p>It's slow because of two things:</p>
<ol>
<li>You're sending the result for every integer from all the goroutines down a channel that has a tiny 100 number buffer, to be consumed by 1 goroutine. That means that your code cannot run any faster than that single goroutine can consume results. Your workers are waiting to get rid of their result. Send fewer results (batch, only send on prime, ...).</li>
<li>You're sending too small tasks to the goroutines - your primitive isPrime function only becomes expensive once the number is above a few hundred thousand, and for most of your run, sending the request to the worker is harder than the task itself. This means that your workers are waiting to get new requests, rather than spending time working. Instead, batch your requests (send a <em>range</em>, not a number).</li>
</ol>
<p>There are way more things to consider, and concurrent code will always have a penalty for its concurrency, but a good thing to consider is that you want your workers to run on their own, without talking to anyone, for as long as possible.</p></pre>epiris: <pre><p>To start use the time package instead of that milis stuff, it's probably not even accurate.</p>
<pre><code>start := time.Now()
fmt.Println(time.Now()-start) // 14ms
</code></pre>
<p>As sort of mentioned in another post, though not due to caching, it's not written to benefit from concurrency. It's just a sequential loop with the added overhead of synchronization. Instead make a Range struct that sends a worker a large batch of numbers to find. I.e:</p>
<pre><code>type Range struct { start, end }
for I < 16m, I+= batchsize
queue <- Range{I, I + batchSize }
</code></pre>
<p>Now you can remove a total of 16*n million runtime scheduler events needed that pause your goroutine, including accepting results, sending results, etc. Now that you are working on larger ranges you can ditch trial division, it is the slowest method for finding primes for larger numbers. Since your script goes to 16 million you should use sieve of atkin for larger ranges or eratosthenes (check spelling) since they are much more efficient for large numbers. At this point things should be much faster than the sequential.</p></pre>dlsniper: <pre><p>Read and apply this <a href="https://blog.golang.org/profiling-go-programs" rel="nofollow">https://blog.golang.org/profiling-go-programs</a> and <a href="https://making.pusher.com/go-tool-trace/" rel="nofollow">https://making.pusher.com/go-tool-trace/</a></p></pre>nevyn: <pre><p>I'd start with what others have done:</p>
<p><a href="https://www.google.com/search?q=golang+sieve+of" rel="nofollow">https://www.google.com/search?q=golang+sieve+of</a></p>
<p>Eg.</p>
<p><a href="https://play.golang.org/p/9U22NfrXeq" rel="nofollow">https://play.golang.org/p/9U22NfrXeq</a></p></pre>NoEffex: <pre><p>I think you need to set the number of cores to use. </p>
<p><code>import "runtime"
runtime.GOMAXPROCS(runtime.NumCPU())</code></p>
<p>This allows GO to use all cpu threads</p></pre>dlsniper: <pre><p>You don't need to this since a few releases now, iirc Go 1.4 or 1.5.</p></pre>NoEffex: <pre><p>Oh right I didn't know that</p></pre>
