Go vs Kotlin Performance - Nth Prime Calculation


(Luke Bullard) #1

I was doing a test comparison in performance between Go and Kotlin and decided to test out how the two compare in regards to calculating the Nth prime number. From my testing, I found that on average, Go took around twice the amount of time to calculate any Nth prime number that Kotlin took. For instance, if Kotlin took ~250,000ns to calculate the 100th prime, then Go took ~500,000ns.

As an aside, I’m aware of optimizations of calculating the Nth prime number, such as the Sieve of Eratosthenes, but I was originally using these two functions to simulate heavy computational work in a RESTful microservice. I posted the two functions I used below.

Is Kotlin simply faster than Go in this regard? Or is there something else I’m missing?

Thank you so much

    fun simplePrime(primeN : Int) : Int {
        var primeI = 0
        var currNum = 1
        while (primeI < primeN) {
            currNum += 1
            var isPrime = true
            for (i in 2..currNum/2) {
                if (num % i == 0) {
                    isPrime = false
                    break
                }
            }
            if (isPrime) {
                primeI += 1
            }
        }
        return currNum
    }
func getNthPrime(num int) int {
	primeNum := 0
	currNum := 1
	for primeNum < num {
		currNum++
		isPrime := true
		for i := 2; i < currNum/2; i++ {
			if currNum % i == 0 {
				isPrime = false
				break
			}
		}
		if isPrime {
			primeNum++
		}
	}
	return primeNum
}

(Lucas Bremgartner) #2

The code in Kotlin and the code in Go are not the same. In Go the loop condition should be

for i := 2; i < currNum/2; i++

to be on par with the Kotlin version. With that fix, the time for the Go code is actually cut by ~50%, so I guess Kotlin and Go are more or less on par.

Beside of this, I suggest to use the same var names in both versions, which would make it easier to compare the code. I think the Kotlin code does have some typos as well: I guess the var num should be currNum.


(Luke Bullard) #3

Sorry, I didn’t post the same version of the function. I’ll update the post.

I originally had them both iterating through the entire set of numbers, but changed optimized it a bit to be more realistic, but I didn’t realize I posted the optimized version for Kotlin and not for Go. But for the numbers and data I found, I tested using the “optimized” function for both.


(Lucas Bremgartner) #4

In this case you have to share some more details about how you actually performed the benchmarks.

Just as a side note, it can be pretty hard to get a meaningful comparison of the same algorithm in two different programming languages. It all depends on what exactly is measured, how many runs of the function under tests are executed (e.g. are CPU caches cold or warm), etc.


(Luke Bullard) #5

I ran the comparison tests on a private server, with an Intel XEON-E3-1270-V3-Haswell 3.5GHz processor and 2x 4GB Kingston 4GB DDR3 1Rx8. I had swap disabled, and I ran tests of several thousand iterations. For each iteration, I slept for a second in between each run. I timed the functions simply by wrapping the function around calls to nanoTime and calculating the difference, which I’m aware could be flawed but regardless, don’t think it could account for the difference I noted. No CPU intensive background processes were running (~100% Idle)

My results:

-With n=100,

  • Go: ~600,000ns per iteration
  • Kotlin: ~300,000ns per iteration
    -With n=1000
  • Go: ~50,000,000ns per iteration
  • Kotlin: ~25,000,000ns per iteration

Other performance tests I did suggested Go performed better than Kotlin (Bubble sort, String -> Hashmap), but I guess I was mainly wondering if there was something I was doing fundamentally wrong, or if Go struggles in performance in certain scenarios such as this.


(Lucas Bremgartner) #6

With my dated notebook (with Intel® Core™ i5-6200U CPU @ 2.30GHz, not idle at all) and the following benchmark:

package nthprime

import "testing"

var result int

func getNthPrime(num int) int {
	primeNum := 0
	currNum := 1
	for primeNum < num {
		currNum++
		isPrime := true
		for i := 2; i < currNum / 2; i++ {
			if currNum%i == 0 {
				isPrime = false
				break
			}
		}
		if isPrime {
			primeNum++
		}
	}
	return primeNum
}

func BenchmarkNthPrime(b *testing.B) {
	var r int
	for i := 0; i < b.N; i++ {
		r = getNthPrime(100)
	}
	result = r
}

I get the following results:

$  go test -bench=. .
goos: linux
goarch: amd64
pkg: nthprime
BenchmarkNthPrime-4        10000            151375 ns/op
PASS
ok      nthprime       1.532s

Based on the CPU comparison at cpu.userbenchmark.com the Intel XEON is way better and still I get the better numbers per operation with my test on my laptop (~150000 ns/op).


(Karl Benedict) #7

the algorithm thinks that 4 is a prime number?.. :slight_smile:


(Luke Bullard) #8

So, if I run a Go benchmark, I get ~100,000ns per iteration.

goos: linux
goarch: amd64
BenchmarkNthPrime-8   	   10000	    104896 ns/op
PASS

If I run the Kotlin function using a Kotlin benchmark, I get ~40,000ns per iteration.

The original test I had done involved reading input being fed in from another server, which fired a query every second, and then I averaged out all of the iterations. I’m guessing the difference is in regards to the test method?

Regardless, the difference still exists. I’m assuming that in this specific scenario, Kotlin outperforms Go. I guess I’m just surprised there’s a significant difference for such a simple/common scenario.


(Luke Bullard) #9

uhhh are you implying it isn’t? :thinking:

Good thing I’m not using this code for anything :sweat_smile:


(Karl Benedict) #10

only a little bit :slight_smile:

This code should do a little better I think.

package main

import "fmt"

// IsPrime ...
func IsPrime(n int) bool {
	switch {
	case n == 2:
		return true
	case n < 2 || n%2 == 0:
		return false

	default:
		for i := 3; i*i <= n; i += 2 {
			if n%i == 0 {
				return false
			}
		}
	}
	return true
}

func getNthPrime(n int) int {
	var result int = 2
	for {

		if IsPrime(result) {
			n--
		}

		if n == 0 {
			return result
		}

		result++
	}
}

func main() {
	fmt.Println(getNthPrime(100))
}