# Why is python faster than Julia

**URL:** <https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890>\
**Category:** Performance\
**Created:** [March 12, 2020, 4:36pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890 "2020-03-12T16:36:22Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![adangreen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adangreen/32/13361_2.png) [@adangreen](https://discourse.julialang.org/u/adangreen)\
**Post date:** [March 12, 2020, 4:36pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/1 "2020-03-12T16:36:22Z")

</div>

I wrote two absolutely identical pieces of code on python and Julia:

```julia
from time import time

start_time = time()
def euclidian_algorithm_division_count(a, b):
    division_count = 1
    if b > a:
        a, b = b, a
    while (c := a % b) != 0:
        a, b = b, c
        division_count += 1
    return division_count

N = 10**100
M = 10**4
from random import randint
division_count_array = []
while M > 0:
    a = randint(1, N)
    b = randint(1, N)
    division_count_array.append(euclidian_algorithm_division_count(a, b))
    M -= 1
print(time() - start_time, "seconds")

```

```julia
@time begin

function euclidean_algorithm_division_count(a, b)
    division_count = 1
    if b > a
        a, b = b, a
    end
    while (c = a % b) != 0
        a, b = b, c
        division_count += 1
    end
    return division_count
end

function main()
    N = big(10)^100
    M = 10^4
    division_count_array = []
    while M > 0
        a, b = rand(1:N, 2)
        push!(division_count_array, euclidean_algorithm_division_count(a, b))
        M -= 1
    end
end

main()

end

```

And that’s the output i got:  
0.6859960556030273 seconds for python;  
1.760202 seconds (9.66 M allocations: 191.444 MiB, 20.62% gc time) for Julia;  
I believe compiled Julia can’t be slower than python for real, thus the problem is in my code. Where did i mistake?

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [March 12, 2020, 4:53pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/2 "2020-03-12T16:53:29Z")

</div>

Apart from any issues with the code itself, you are measuring compilation time in addition to compute time. Try using `@btime` from the `BenchmarkTools` package to get a more reliable measurement.

---

<div class="post-metadata">

**Author:** ![adangreen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adangreen/32/13361_2.png) [@adangreen](https://discourse.julialang.org/u/adangreen)\
**Post date:** [March 12, 2020, 5:02pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/3 "2020-03-12T17:02:03Z")

</div>

got 1.5 seconds with btime, but it’s still slower than python

```julia
using BenchmarkTools

function euclidean_algorithm_division_count(a, b)
    division_count = 1
    if b > a
        a, b = b, a
    end
    while (c = a % b) != 0
        a, b = b, c
        division_count += 1
    end
    return division_count
end

function main()
    N = big(10)^100
    M = 10^4
    division_count_array = []
    while M > 0
        a, b = rand(1:N, 2)
        push!(division_count_array, euclidean_algorithm_division_count(a, b))
        M -= 1
    end
end

@btime main()

```

---

<div class="post-metadata">

**Author:** ![ssfrr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ssfrr/32/3736_2.png) [@ssfrr](https://discourse.julialang.org/u/ssfrr)\
**Post date:** [March 12, 2020, 5:03pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/4 "2020-03-12T17:03:31Z")

</div>

To be more explicit, you want to define your functions as above and then run

```julia
using BenchmarkTools
@btime main()

```

An analogy here would be that timing as you’ve done above is sort of like writing a C program and then timing both compilation and execution.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [March 12, 2020, 5:05pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/5 "2020-03-12T17:05:07Z")

</div>

> [@adangreen](#):
>
> division\_count\_array =

isn’t type inferred

---

<div class="post-metadata">

**Author:** ![ssfrr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ssfrr/32/3736_2.png) [@ssfrr](https://discourse.julialang.org/u/ssfrr)\
**Post date:** [March 12, 2020, 5:09pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/6 "2020-03-12T17:09:12Z")

</div>

Specifically here you’ll want to do `Int[]` rather than just `[]`, so julia knows what types the array will hold.

I usually avoid creating a container first and then `push!`ing into it for this reason (I don’t want to have to specify the element types). So I often do something more like:

```julia
function main()
    N = big(10)^100
    M = 10^4
    division_count_array = map(1:M) do _
        a, b = rand(1:N, 2)
        euclidean_algorithm_division_count(a, b)
    end
end

```

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [March 12, 2020, 5:14pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/7 "2020-03-12T17:14:04Z")

</div>

I’m not sure (and your code doesn’t seem to run?) but profiler says the largest part of code is spend in the `(c = a % b)` line, and chaging the container to `Int[]` doesn’t do anything to my timings.

Profiler points me to

```julia
($fJ)(x::BigInt, y::BigInt) = MPZ.$fC(x, y)

```

in `gmp.jl`, so maybe there’s an issue here with `BigInt`s just not being very fast?

Specifically, rewriting things as:

```julia
function main2()
    N = big(10)^100
    M = 10^4
    division_count_array = Int[]
    while M > 0
        a, b = rand(1:N, 2)
        push!(division_count_array, euclidean_algorithm_division_count(a, b))
        M -= 1
    end
end

@btime main2()

function main3()
    N = big(10)^100
    division_count_array = Array{Int}(undef, 10^4)
    for i ∈ 1:length(division_count_array)
        division_count_array[i] = euclidean_algorithm_division_count(rand(1:N), rand(1:N))
    end
end

@btime main3()

```

I get

```julia
 514.021 ms (9549046 allocations: 185.52 MiB)
  539.400 ms (9552491 allocations: 185.58 MiB)
  485.769 ms (9697452 allocations: 188.44 MiB)

```

so no real changes - maybe there are things to look out for with `BigInt`s I’m unaware of, as I never need to work with them.

And just to add reducing `N` to avoid `BigInt` (which of course isn’t directly comparable as we’re also changing the range for `rand` to consider) the time reduces by a factor of 100 and almost all allocations go away:

```julia

function main4()
    N = 10^30
    division_count_array = Array{Int}(undef, 10^4)
    for i ∈ 1:length(division_count_array)
        division_count_array[i] = euclidean_algorithm_division_count(rand(1:N), rand(1:N))
    end
end

@btime main4()
3.869 ms (2 allocations: 78.20 KiB)

```

---

<div class="post-metadata">

**Author:** ![pixel27](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pixel27/32/8902_2.png) [@pixel27](https://discourse.julialang.org/u/pixel27)\
**Post date:** [March 12, 2020, 6:09pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/8 "2020-03-12T18:09:11Z")

</div>

BigInt and BigFloat are handled by the GNU Multiple Precision Arithmetic Library. My assumption would be that the library is as optimized as it can be. I don’t know what python uses for it’s library, or if they rolled their own. I tried 2 quick things, one was allocating the division\_count\_array in one pass rather than growing it. The second was to turn off garbage collection.

On my machine I get:

- 384 ms to 360 ms - Python code.
- 473 ms - Your (mostly) original Julia code.
- 333 ms - Julia /w GC disabled.

Which has me curious if the python garbage collector ever ran…

My version:

```julia
using BenchmarkTools

function euclidean_algorithm_division_count(a, b)
    division_count = 1
    if b > a
        a, b = b, a
    end
    while (c = a % b) != 0
        a, b = b, c
        division_count += 1
    end
    return division_count
end

function main()
    N = big(10)^100
    R = 1:N
    M = 10^4
    division_count_array = Vector{Int64}(undef, M)
    while M > 0
        a, b = rand(R, 2)
        division_count_array[M] = euclidean_algorithm_division_count(a, b)
        M -= 1
    end
end

GC.enable(false)
@btime main()
GC.enable(true)
GC.gc()

```

---

<div class="post-metadata">

**Author:** ![Amin\_Yahyaabadi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/amin_yahyaabadi/32/9826_2.png) [@Amin\_Yahyaabadi](https://discourse.julialang.org/u/Amin_Yahyaabadi)\
**Post date:** [March 12, 2020, 7:00pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/9 "2020-03-12T19:00:58Z")

</div>

> [@pixel27](#):
>
> a, b = rand(R, 2) division\_count\_array[M] = euclidean\_algorithm\_division\_count(a, b) M -= 1

Also using `@inbounds` gives me a little more speed up:

```julia
function main()
    N = big(10)^100
    R = 1:N
    M = 10^4
    division_count_array = Vector{Int64}(undef, M)
    while M > 0
        a, b = rand(R, 2)
        @inbounds division_count_array[M] = euclidean_algorithm_division_count(a, b)
        M -= 1
    end
end

```

---

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [March 12, 2020, 8:55pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/10 "2020-03-12T20:55:00Z")

</div>

really `rand(1:N,2)` and not `rand(N,2)`?

---

<div class="post-metadata">

**Author:** ![pixel27](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pixel27/32/8902_2.png) [@pixel27](https://discourse.julialang.org/u/pixel27)\
**Post date:** [March 12, 2020, 9:02pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/11 "2020-03-12T21:02:55Z")

</div>

> [@rveltz](#):
>
> really `rand(1:N,2)` and not `rand(N,2)` ?

```julia
julia> rand(big(10), 2)
10×2 Array{Float64,2}:
 0.85374 0.102817
 0.686707 0.545013
 0.905144 0.897086
 0.405992 0.878026
 0.113256 0.640781
 0.0366894 0.302942
 0.593746 0.203189
 0.647248 0.00892756
 0.826612 0.910477
 0.133924 0.318374

```

```julia
rand(big(10)^100, 2)
ERROR: InexactError: Int64(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)
Stacktrace:
 [1] rand(::BigInt, ::Int64) at .\gmp.jl:356
 [2] top-level scope at REPL[10]:1

```

rand(1:N, 2) appears to produce different results than rand(N, 2)…

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 12, 2020, 11:15pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/12 "2020-03-12T23:15:14Z")

</div>

So, `c = a % b` is slow for `BigInt`s because a new `c` is allocated each time. But there’s an in-place version, available, but a bit hidden: `Base.GMP.MPZ.tdiv_r!` ([Integer Division (GNU MP 6.2.1)](https://gmplib.org/manual/Integer-Division.html#Integer-Division))

```julia
function divcount!(a::BigInt, b::BigInt)
    count = 1
    if b > a
        a, b = b, a
    end
    c = a % b
    while !iszero(c)
        a, b, c = b, c, a # we need to shuffle all three variables to avoid aliasing
        count += 1
        Base.GMP.MPZ.tdiv_r!(c, a, b) # this works in-place!
    end
    return count
end

divcount(a::BigInt, b::BigInt) = divcount!(deepcopy(a), deepcopy(b)) # copy is not enough

```

The `divcount!` function actually mutates the inputs, `a` and `b`, so I made a separate `divcounts` which doesn’t. Let’s compare performance:

```julia
function main_(f)
    N = big(10)^100
    M = 10^4
    counts = Vector{Int}(undef, M)
    nrange = 1:N # moving this outside loop since it allocates
    @inbounds for i in eachindex(counts)
        a, b = rand(nrange, 2)
        counts[i] = f(a, b)
    end
    return counts
end

julia> @btime main_(euclidean_algorithm_division_count);
  694.734 ms (5549040 allocations: 108.78 MiB)

julia> @btime main_(divcount);
  134.639 ms (250005 allocations: 13.28 MiB)

```

It’s definitely faster. There might be some gains to be had with the `rand` function too, but that is probably much less.

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [March 12, 2020, 11:23pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/13 "2020-03-12T23:23:16Z")

</div>

I also find that after disabling the garbage collector the python and Julia versions have the same run time.

EDIT: The statement below is wrong. I mistook the timings. The code that uses the reference is _slower_. I think what @yuyichao is getting at is that an allocation is made for the result of `a % b` in any case.

~~[quote=“pixel27, post:8, topic:35890”]  
GNU Multiple Precision Arithmetic Library. My assumption would be that the library is as optimized as it can be.  
[/quote]~~

~~The libraries are fast. But, Julia doesn’t do much, if anything, to optimize code for `BigInt`s.~~

~~For example this  
function euclidean\_algorithm\_division\_count(a, b)  
division\_count = 1  
c = Ref(BigInt())  
if b \> a  
a, b = b, a  
end  
while (c[] = a % b) != 0  
a, b = b, c[]  
division\_count += 1  
end  
return division\_count  
end~~  
~~is a bit faster than the version above becuase it doesn’t allocate `c` every time it is assigned. But, it doesn’t have a big effect on the total run time.~~

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 12, 2020, 11:32pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/14 "2020-03-12T23:32:18Z")

</div>

> [@jlapeyre](#):
>
> is a bit faster than the version above becuase it doesn’t allocate `c` every time it is assigned. But, it doesn’t have a big effect on the total run time.

No this code does not do any (useful) preallocation.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 12, 2020, 11:34pm UTC](https://discourse.julialang.org/t/why-is-python-faster-than-julia/35890/15 "2020-03-12T23:34:27Z")

</div>

> [@jlapeyre](#):
>
> is a bit faster than the version above

Which one is ‘the version above’? It seems slower than the one I suggested:

```julia
julia> @btime divcount($a, $b)
  10.524 μs (13 allocations: 976 bytes)

julia> @btime euclidean_algorithm_division_count($a, $b) # yours
  36.689 μs (498 allocations: 9.88 KiB)

```

And it actually allocates more than the original version

```julia
julia> @btime euclidean_algorithm_division_count($a, $b)
  36.610 μs (496 allocations: 9.84 KiB)

```