Execution time julia program to count primes

user_15592952 0
Viewed 115

I am experimenting a bit with julia, since I've heard that it is suitable for scientific calculus and its syntax is reminiscent of python. I tried to write and execute a program to count prime numbers below a certain n, but the performances are not the ones hoped. Here I post my code, with the disclaimer that I've literally started yesterday in julia programming and I am almost sure that something is wrong:

n = 250000
counter = 0

function countPrime(counter)
    for i = 1:n
        # print("begin counter= ", counter, "\n")
        isPrime = true
        # print("i= ", i, "\n")
        for j = 2:(i-1)
            if (i%j) == 0 
                isPrime = false
            #   print("j= ", j, "\n")
                break
            end
            
        end

        (isPrime==true) ? counter += 1 : counter
    #   print("Counter= ", counter, "\n")
    end
    return counter
end

println(countPrime(counter))

The fact is that the same program ported in C has about 5 seconds of execution time, while this one in julia has about 3 minutes and 50 seconds, which sounds odd to me since I thought that julia is a compiled language. What's happening?

julia execution-time performance
1 Answers

Here is how I would change it:

function countPrime(n)
    counter = 0
    for i in 1:n
        isPrime = true
        for j in 2:i-1
            if i % j == 0 
                isPrime = false
                break
            end            
        end
        isPrime && (counter += 1)
    end
    return counter
end

This code runs in about 5 seconds on my laptop. Apart from stylistic changes the major change is that you should pass n as a parameter to your function and define the counter variable inside your functions.

The changes follow one of the first advices in the Performance Tips section of the Julia Manual.

The point is that when you use a global variable the Julia compiler is not able to make assumptions about the type of this variable (as it might change after the function was compiled), so it defensively assumes that it might be anything, which slows things down.

As for stylistic changes note that (isPrime==true) ? counter += 1 : counter can be written just as isPrime && (counter += 1) as you want to increment the counter if isPrime is true. Using the ternary operator ? : is not needed here.

To give a MWE of a problem with using global variables in functions:

julia> x = 10
10

julia> f() = x
f (generic function with 1 method)

julia> @code_warntype f()
MethodInstance for f()
  from f() in Main at REPL[2]:1
Arguments
  #self#::Core.Const(f)
Body::Any
1 ─     return Main.x

You can see that here inside the f function you refer to the global variable x. Therefore, when Julia compiles f it must assume that the value of x can have any type (which is called in Julia Any). Working with such values is slow as the compiler cannot use any optimizations that would take advantage of more specific type of value processed.

user_12695670
Related