<p>I was working with an intern today that submitted a homework assignment for class last year. The project was to create a prime number counter that was as fast as possible in Java. I knew I could blow it away in Go so I converted his project over to Golang and then made adjustments to get some extra speed out of it.</p>
<p>I'm actually interested to see how fast you get make it in Go. These speeds are relative to my processor.</p>
<p>My code is here without Go routines:
<a href="https://gist.github.com/josephspurrier/c3073854dd718f5c8021">https://gist.github.com/josephspurrier/c3073854dd718f5c8021</a></p>
<pre><code>2015/08/19 18:48:26 Test 1: 664579 took 51.0003ms
2015/08/19 18:48:27 Test 2: 5761455 took 693.0054ms
2015/08/19 18:48:35 Test 3: 50847534 took 8.229995s
</code></pre>
<p>How fast can you make it (with or without Go routines)?</p>
<hr/>**评论：**<br/><br/>FIuffyRabbit: <pre><p>Test 3 needs to be run on 64bit go or you blow the stack.</p></pre>fungussa: <pre><p>What are the times for the Java version? </p></pre>bonafidebob: <pre><p>I've been doing a lot of JS lately and was curious about relative performance, so I converted your function to JavaScript... </p>
<p>TL;DR it's a bit slower, but only takes about 5% longer.</p>
<p>First I cleaned up the go a bit so I could follow it more easily:</p>
<pre><code>func countPrimes(limit int) int {
// Return if less than 1
if limit <= 1 {
return 0
}
// Get the sqrt of the limit
sqrtLimit := int(math.Sqrt(float64(limit)))
// Create array
numbers := make([]bool, limit)
// Set 1 to prime
numbers[1] = true
numPrimes := 0
// Count the number of olds
if limit%2 == 0 {
numPrimes = limit / 2
} else {
numPrimes = (limit + 1) / 2
}
// Loop through odd numbers
for i := 3; i <= sqrtLimit; i += 2 {
if !numbers[i] {
for j := i*i; j < limit; j += i*2 {
if !numbers[j] {
numbers[j] = true
numPrimes -= 1
}
}
}
}
return numPrimes
}
</code></pre>
<p>Times on my somewhat old mac:</p>
<pre><code>2015/08/19 21:14:48 Test 1: 25 took 1.005µs
2015/08/19 21:14:48 Test 2: 664579 took 118.712526ms
2015/08/19 21:14:50 Test 3: 5761455 took 1.543064149s
2015/08/19 21:15:07 Test 4: 50847534 took 16.911457224s
</code></pre>
<p>And then I translated it to JS. A regular array (object) was too slow and small, so I just swapped in a typed array of Int8s. (Yes, uses 8x the memory needed... whatever.)</p>
<pre><code>function countPrimes(limit) {
// Return if less than 1
if (limit <= 1) {
return 0
}
// Get the sqrt of the limit
var sqrtLimit = Math.floor(Math.sqrt(limit));
// Create array
var numbers = new Int8Array(limit);
// Set 1 to prime
numbers[1] = 1;
var numPrimes = Math.ceil(limit / 2);
// Loop through odd numbers
for (var i = 3; i <= sqrtLimit; i += 2) {
if (!numbers[i]) {
for (var j = i*i; j < limit; j += i*2) {
if (!numbers[j]) {
numbers[j] = 1;
numPrimes--;
}
}
}
}
return numPrimes
}
</code></pre>
<p>Equivalent times running with node (stable: 0.12.7)</p>
<pre><code>Test 1: 25 took 0.001 sec
Test 2: 664579 took 0.121 sec
Test 3: 5761455 took 1.656 sec
Test 4: 50847534 took 18.866 sec
</code></pre></pre>jerf: <pre><p>This is the sort of code I consider "easy mode" for a JIT... if a JIT can't take this sort of math code and basically run it at full C speed, it shouldn't even have been released. It proves little about the relative speed of the languages in "real" code, unless you're just doing math.</p>
<p>That's not a criticism of your code, Go, JS, or anything else... it's an observation about the nature of JIT'ed languages. If it's a criticism of anything, it's only the idea that you can test speed meaningfully via this sort of code.</p>
<p>Similarly, rather than open another comment... I see no reason why Go would be faster than Java at this task, and, indeed, would expect it to be slower, unless by sheer luck the Go compiler managed to emit the same code the highly optimized Java JIT settled on by witnessing the code run.</p>
<p>In fact, in general, Go isn't "faster" than Java right now, at least on transliterated code. Much like how good Python can sometimes beat bad C, if Go is faster than Java, it's because it makes it easier than Java to do the right thing sometimes, not because it can do the exact same thing faster than Java.</p>
<p>The big thing about Go vs. Java is that unlike C vs. Python where there's 40-100x the speed difference, Java and Go are going to be more like 2x... in general, that's basically nothing, it's dominated by local algorithm and incidental considerations. Java may be faster than Go, but 2x isn't really enough to matter... if you're in a situation where Go is too slow for some task after optimization, the solution is to figure out how to get another server, not rewrite it in Java. This is in contrast to Python or Ruby or something.</p></pre>bonafidebob: <pre><p>Not 'my' code here, I was mostly trying to understand whether op's code (op's intern's code?) had anything go-ish about it.</p>
<p>Once I understood it didn't, I was curious if JavaScript would be any worse, and there's one way to know for sure...</p>
<p>One thing I'm curious about, will the go compiler efficiently pack the array of bools? I would have to do that myself in JS, unless UInt1Array becomes a JS thing.</p></pre>bonafidebob: <pre><p>To be fair, there's nothing about this code that takes any particular advantage of go; it's just math in a loop. The compiler isn't going to do fantastic things with it, and so the V8 optimizer will do an excellent job as well.</p></pre>dchapes: <pre><p>See <a href="https://godoc.org/github.com/jbarham/primegen.go#Primegen.Count" rel="nofollow"><code>github.com/jbarham/primegen.go</code></a>.</p></pre>
