Testing Julia for speed (i)

The speed of a program shouldn’t really matter, I mean it is ultimately about how robust a program is, and how correct it’s output is. However in the age of big data, no-one really wants to wait an eternity  for a program to perform its tasks. Consider the task of developing an AI to beat a human at a board game such as chess – here the aim is to win, not necessarily to do it in any set time frame. However processing a large image or 3D data set ultimately requires some element of speed. In order to experiment with how fast Julia is we will use three algorithms: (i) Ackermann’s function, (ii) Bubblesort, and (iii) a simple mean-filter for image noise suppression applied to a large image. These will be used to compare Julia with C, Python, and Fortran.

Ackermann’s Function

Ackermann’s function was originally conceived in 1928 by Wilhelm Ackermann, and has been used extensively in the past for studies in computational efficiency, especially by B.A. Wichmann. Ackermann’s function is interesting from the point of view that it is a highly recursive function.  Ackermann’s function has the following recurrence relation:

ackermannFORM

This is expressed as a recursive function, which may seem simple, but the larger m and become, the more complex the recursion becomes. Due to the limitations Python has with recursion, we will use an iterative version of Ackermann, which relies on the use of stacks to implement recursion. Ackermann’s function is a classic function which serves no purpose other than evaluating computational performance.

The code for Python and Julia includes use of built-in functionality to implement a stack, whereas in C and Fortran the code for the stack is provided in the form of a library, and module respectively. Here is the Julia code to calculate the iterative version of Asckermann’s function.

function ackermannIterative(m,n)
    stack = []
    push!(stack, m)
    while (isempty(stack) == false)
        m = pop!(stack)
        if m == 0
            n = n + 1
        elseif n == 0
            push!(stack, m-1)
            n = 1
        else
            push!(stack, m-1)
            push!(stack, m)
            n = n - 1
        end
    end
    return n
end

print("Value m: ")
m = chomp(readline())
m = parse(Int, m)

print("Value n: ")
n = chomp(readline())
n = parse(Int, n)

@time result = ackermannIterative(m, n)
println("Ackermann : ", result)

To test the various languages, we will calculate Ackermann(4,1), which has a value of 65533.

timingAckermann

As is expected, C leads the pack, with Fortran trailing close by. This is not unexpected from two statically typed languages. Julia is approximately 4 times slower than C. Python is the outlier here, being more than 25 times slower than C, and 7 times slower than Julia. There is little that can be done to improve this code, as very little is calculated, it is merely involves some simple arithmetic, and calls to add and remove items from a stack.

 

 

 

Advertisements

2 thoughts on “Testing Julia for speed (i)

  1. perfectionatic says:

    Your code suffers from a bit of type instability, which could slow things down.
    stack=[] will result in any empty array to type “Any”. At little type annotation can go a long way.
    Instead using stack=Int[].
    No type instability here. You can check by running
    @code_warntype ackermannIterative2(4,1)
    This slight modification brought improved performance from 101 seconds in the original version, down to 33 seconds. So the code can be improved after-all!
    In Julia, you can always get better speed if you eliminate type instability.

    • spqr says:

      Good point. Honestly didn’t think about it. One of the drawbacks to such a diverse language.
      I ran the improvement myself, and a good 4x efficiency increase. Cool.

      $julia ackermannIimp.jl
      Value m: 4
      Value n: 1
      25.508446 seconds (4.69 k allocations: 1.263 MB)
      Ackermann : 65533

      $ julia ackermannI.jl
      Value m: 4
      Value n: 1
      115.957018 seconds (3.00 k allocations: 1.182 MB)
      Ackermann : 65533

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s