6

I wanted to try the Julia programming language, as I heard it is supposed to be faster than Python. I decided to try a dynamic program for Project Euler #14, as it dealt with a lot of computation (finding the longest Collatz sequence).

I wrote a program for it in Julia, and then decided to try to make an analogous program in Python, so see how fast each of them were. However, on my machine, the Python program runs in about 2 seconds, while the Julia one takes about 7. This surprised me, because as I said before Julia claims to be faster than Python, so I was wondering if there was anything inherent about the scripts that makes the Julia one so much slower. I attempted to have them both computed in the same way.

Here are the scripts, I would appreciate any insight!

Julia:

global max_val = 0
global max_item = 0
global d = Dict{Integer,Integer}()
function coll_length(n)
    #println(n)
    global max_val
    global max_item
    global d
    if haskey(d,n)
        return d[n]
    end
    if n==1
        answer = 1
    elseif n%2==1
        answer = 1+coll_length(3n+1)
    else
        answer = 1+coll_length(n/2)
    end

    d[n]=answer
    if max_val<answer
        max_val=answer
        max_item=n
    end
    return answer
end


for i = 1:1000000
    coll_length(i)
end
println(max_item)

Python:

d = {}
max_val = 0
max_item = 0

def coll_length(n):
    global d 
    global max_val 
    global max_item 

    if n in d:
        return d[n]
    if n==1:
        answer= 1
    elif n%2==0:
        answer= 1+coll_length(n/2)
    else:
        answer= 1+coll_length(3*n+1)

    d[n]=answer
    if max_val<answer:
        max_val=answer
        max_item=n
    return answer

for n in range(1,1000000+1):
    coll_length(n)
print max_item
Arya
  • 1,382
  • 2
  • 15
  • 36
  • 2
    Well, because you found an example doesn't mean anything about whether Julia or Python are "faster" -- whatever that means, in a general sense. – Marcus Müller Feb 08 '16 at 15:51
  • I'd generally criticize that your program isn't very optimal for either language. Recursion in non-functional languages, especially if you're not using tail recursion, is a pretty bad idea, and it's up to the runtime to make things work at all, though this definitely has everything you need to produce a stack overflow! – Marcus Müller Feb 08 '16 at 15:53
  • @pp_ Julia is *three times slower*, not faster. And my guess is "because engineering hours worth of millions of went into optimizing the standard Python interpreter". – Marcus Müller Feb 08 '16 at 15:54
  • Yeah - I know very well that this isn't the most efficient solution in either language, and that this doesn't prove anything substantial. I just hacked it up in Julia and I wanted to know what about the solution itself made it faster in Python – Arya Feb 08 '16 at 15:54
  • 1
    Wild guess: because python dicts with integer keys are extremely well-optimized. – Marcus Müller Feb 08 '16 at 15:57
  • 9
    *"I know very well that this isn't the most efficient solution in either language"* – Then it's not worth discussing. If you wonder which language is faster, you need to implement the *fastest possible solution* in both languages and then compare. Comparing *some suboptimal implementation* vs. *some other suboptimal implementation* doesn't proof anything. – deceze Feb 08 '16 at 15:59
  • *"Julia’s LLVM-based just-in-time (JIT) compiler combined with the language’s design allow it to approach and often match the performance of C"* - Are you reading [the documentation](http://julialang.org/)? The fact whether one approach is faster than another really depends on the lower-level compilation/interpretation of the language – OneCricketeer Feb 08 '16 at 16:00
  • @deceze I'm not arguing that this means one of them is faster, I'm just curious what about this solution makes it faster in Python. – Arya Feb 08 '16 at 16:02
  • To add what @deceze said: it doesn't only prove anything, *it's not even an indication* for anything. Point is that "I'm instructing my children to use my car keys to open a can, and my son is 200% faster than my daughter at opening cans with car keys" doesn't prove anything: Your daughter might simply be refusing to do that, and getting the can opener from the kitchen. *Because you ask them a thing that neither of your kids are good at (heavy manual labor) and asking them to do things in a manner that noone else would*. – Marcus Müller Feb 08 '16 at 16:03
  • *"what about this solution makes it faster in Python"* – Because the parts that are used within this solution happen to be faster in Python than the somewhat equivalent parts in Julia. You'll find that in any language/framework/compiler/interpreter/runtime/whatever: some are better at some things than others at similar things. – deceze Feb 08 '16 at 16:05
  • 4
    Do the programs even give the same answer? Just wondering given the Python function returns `answer` while the Julia one returns a mysterious `x` that exists nowhere else in the code. – Duncan Feb 08 '16 at 16:06
  • What is the actual programming problem you're asking about here? This isn't the best forum for discussing the relative merits of different programming languages. Please refer to https://stackoverflow.com/tour . – John Percival Hackworth Feb 08 '16 at 16:16
  • 2
    I'm voting to close this question as off-topic because it's seeking discussion of the relative performance of two programming languages based on sub-optimal code. – John Percival Hackworth Feb 08 '16 at 16:18
  • @Duncan that's my bad, I was trying to have nice variable names but I forgot to edit that one – Arya Feb 08 '16 at 16:23
  • 2
    @JohnPercivalHackworth it should stay -> http://stackoverflow.com/help/how-to-ask – Andy K Feb 08 '16 at 16:23
  • @MarcusMüller For your example, your experiment is an indication that your son is better at using his hands. It's not a useful conclusion (given that it's useless) but it's interesting to me and I was curious. – Arya Feb 08 '16 at 16:24
  • @deceze That's obviously the answer but I would like to have some more context, why are these certain techniques better in Python than Julia? – Arya Feb 08 '16 at 16:25
  • @JohnPercivalHackworth I mean it doesn't matter that much at this point, my question has been downvoted to hell (after being up +3) so I assume it's as good as dead. – Arya Feb 08 '16 at 16:28
  • @Arya, no, it doesn't say that the son is better at using hands. Really. It means that your son is better at doing something totally irrelevant to any practical performance. – Marcus Müller Feb 08 '16 at 16:35
  • 13
    This question seems fine to me: this is a comparison of two essentially identical algorithms in Python and Julia. The answer is that if you want your Julia code to be fast, you should not use mutable global variables – this is our very first performance tip: http://docs.julialang.org/en/release-0.4/manual/performance-tips/#avoid-global-variables. @Arya: if you want a friendlier discussion of your code, you may want to try posting to julia-users@googlegroups.com. – StefanKarpinski Feb 08 '16 at 16:50
  • 3
    You may also want to check out the efficient code for Euler #14 in Julia's test suite: https://github.com/JuliaLang/julia/blob/82f810d79640d2aac/test/euler.jl#L221-L240 – on my system it computes euler14(999999) in 18 milliseconds. – StefanKarpinski Feb 08 '16 at 16:50
  • 6
    There seem to be several issues in the Julia code..: (1) n/2 should probably be div(n,2) to get integer division; (2) Dict{Int,Int} is probably better rather than Dict{Integer,Integer}; (3) attach `const` to the declaration of `d` in the global scope. With these modifications, the time changed from 4.3 sec to 0.5 sec on my computer. – roygvib Feb 08 '16 at 17:00
  • 1
    I've voted to reopen. The question boils down to a "why is my Julia code slow" question, which is a perfectly valid fit for the StackOverflow format. OP has taken care to provide code and to format the question correctly... I'm really at a loss as to why the close-vote went through. Incidentally Arya, pay close attention to the comments of @StefanKarpinski as they're spot on. – Colin T Bowers Feb 08 '16 at 22:57
  • 2
    @deceze There is an interesting discussion here about comparing *algorithms* versus comparing language speed. My personal opinion is that comparison of sub-optimal algorithms in different languages can still be a relevant question to ask. For some interesting reading on this, have a look a Stefan Karpinski's answer to [this StackOverflow question](http://stackoverflow.com/questions/9968578/speeding-up-julias-poorly-written-r-examples). – Colin T Bowers Feb 08 '16 at 23:07
  • 4
    Given that there are several answers to the question in the comments, perhaps it can be reopened? – Simon Byrne Feb 09 '16 at 14:49
  • 1
    @Arya `nʹ` in the `euler14` function is just an identifier but **notice that `ʹ` (`Int('ʹ') #=> 697`) is not the same as `'` (`Int('\'') #=> 39`)** (very confusing stuff, since indistinguishable in many fonts), the former can be part of an identifier, read it as *n prime*, the latter can't be used in an identifier, instead it is the conjugate transposition operator, ie: `typeof([1,2,3,4]) #=> Array{Int64,1}`, `typeof([1,2,3,4]') #=> Array{Int64,2}`. Also instead of using global variables you can use a type to encapsulate the state, ie: https://gist.github.com/Ismael-VC/f2e31486defff43f927c – HarmonicaMuse Feb 09 '16 at 15:18

0 Answers0