# Julia Beginner (from Python): Numba outperforms Julia in rewrite. Any tips to improve performance?

**URL:** <https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414>\
**Category:** Performance\
**Tags:** benchmark, python, tullio, loopvectorization\
**Created:** [August 15, 2021, 12:00am UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414 "2021-08-15T00:00:50Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 16, 2021, 2:19pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/21 "2021-08-16T14:19:52Z")

</div>

Thanks for the clarification, I will see if I get things right 🙂 . By the way, in this `LazyGreedy`Julia version, this line:

```julia
idxs = findall(==(0), mask)

```

is not doing anything useful, as `idxs` are not used anywhere in the loop. Just by commenting that line you get a 2x speedup.

edit:

If all is correct now, this is the time for the NaiveGreedy version:

```julia
---------------------------------------------
 Fitting time:
 19.153213 seconds (65.21 k allocations: 8.799 GiB, 0.13% gc time)
125819832 9897.307670089183
---------------------------------------------

```

I get a significant speedup if I use this function for the hot loop, @rmeinl:

```julia
function get_gains!(X, current_values, idxs, gains)
    @tturbo for i in eachindex(idxs)
        s = 0.0
        for j in eachindex(current_values)
            s += sqrt(current_values[j] + X[j, idxs[i]])
        end
        gains[i] = s
    end
end;

```

(from ~20 to about ~13s in my computer).

All files are here: [https://gist.github.com/lmiq/828133335a83088e63f21152416c7f7c](https://gist.github.com/lmiq/828133335a83088e63f21152416c7f7c)

Anyway, thanks for the feedback. I still think that if numba is effectively doing much better than `@tturbo` here we need to localize the difference in the minimal working example possible and bring Chris to the table :-).

---

<div class="post-metadata">

**Author:** ![rmeinl](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rmeinl/32/28163_2.png) [@rmeinl](https://discourse.julialang.org/u/rmeinl)\
**Post date:** [August 16, 2021, 2:31pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/22 "2021-08-16T14:31:18Z")

</div>

Great point thanks! I was already using the `popat` function suggested above so the speedup was not as drastic but it still improved a little. The latest times I got were:

```julia
# NaiveGreedy
10.766 s (82941 allocations: 15.02 MiB)

# LazyGreedy
5.904 s (201 allocations: 167.93 MiB)

```

The most up-to-date functions are in `julia_reimpl` here: [https://github.com/rmeinl/apricot-julia](https://github.com/rmeinl/apricot-julia)

---

<div class="post-metadata">

**Author:** ![rmeinl](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rmeinl/32/28163_2.png) [@rmeinl](https://discourse.julialang.org/u/rmeinl)\
**Post date:** [August 16, 2021, 7:19pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/23 "2021-08-16T19:19:17Z")

</div>

Interesting! I get these:

```julia
# NaiveGreedy old 
11.923 s (82912 allocations: 15.02 MiB)

function get_gains!(X, current_values, idxs, gains)
    Threads.@threads for i in eachindex(idxs)
        s = 0.0
        for j in eachindex(current_values)
            @inbounds s += @fastmath sqrt(current_values[j] + X[j, idxs[i]])
        end
        gains[i] = s
    end
end;

#############################

# NaiveGreedy with @tturbo
12.853 s (27 allocations: 8.89 MiB)

function get_gains!(X, current_values, idxs, gains)
    @tturbo for i in eachindex(idxs)
        s = 0.0
        for j in eachindex(current_values)
            s += sqrt(current_values[j] + X[j, idxs[i]])
        end
        gains[i] = s
    end
end;

```

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 16, 2021, 7:28pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/24 "2021-08-16T19:28:13Z")

</div>

This is probalby a MWE for the critical loop, in Julia:

```julia
using BenchmarkTools
using LoopVectorization

function get_gains!(x, y, idxs, gains)
    @tturbo for i in eachindex(idxs)
        s = 0.0
        for j in eachindex(y)
            s += sqrt(y[j] + x[j, idxs[i]])
        end
        gains[i] = s
    end
end;

d = 54
n = 581012
x = rand(54, 581012)*100;
y = zeros(Float64, d)
idxs = collect(1:n);
gains = zeros(Float64, n);

@benchmark get_gains!($x, $y, $idxs, $gains)

```

Do you agree this is the bottleneck? But I’m too unfamiliar with Python and Numba to be sure to write something comparable there.

If we can really localize and quantify the performance difference, than we can post an issue, somewhere so someone can take a look at it.

> [@rmeinl](#):
>
> ```julia
> # NaiveGreedy old 
> 11.923 s (82912 allocations: 15.02 MiB)
> 
> ```

ps: what is the Python time for the naive greedy algorithm in this case?

---

<div class="post-metadata">

**Author:** ![rmeinl](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rmeinl/32/28163_2.png) [@rmeinl](https://discourse.julialang.org/u/rmeinl)\
**Post date:** [August 16, 2021, 9:47pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/25 "2021-08-16T21:47:27Z")

</div>

The MWE looks good and yes, it seems to be that get\_gains! is the bottleneck.  
The Python version ran in `13.24439001083374` for the NaiveGreedy but I slashed a lot of time with the removal of allocations as mentioned above.

---

<div class="post-metadata">

**Author:** ![rmeinl](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rmeinl/32/28163_2.png) [@rmeinl](https://discourse.julialang.org/u/rmeinl)\
**Post date:** [August 16, 2021, 9:53pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/26 "2021-08-16T21:53:38Z")

</div>

I think it’s fine from here though! Thanks so much for your help. All of you!

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 16, 2021, 10:05pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/27 "2021-08-16T22:05:55Z")

</div>

Thank you for the very well documented example. If you or someone else can provide a MWE of the gains function above in Python/Numba, just to check if there is effectively a huge difference between the parallelization and simd Numba is able to do in comparison with what Julia/turbo does, it would be nice. Just so we understand exactly what happened overall and, perhaps, document it for improvements.

---

<div class="post-metadata">

**Author:** ![rmeinl](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rmeinl/32/28163_2.png) [@rmeinl](https://discourse.julialang.org/u/rmeinl)\
**Post date:** [August 16, 2021, 10:28pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/28 "2021-08-16T22:28:47Z")

</div>

I have one here: [https://github.com/rmeinl/apricot-julia/blob/main/src/calc\_gains.py](https://github.com/rmeinl/apricot-julia/blob/main/src/calc_gains.py) Not sure if I’m using the right tools for benchmarking though, the output is 690.234ms compared to 8ms in Julia

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 16, 2021, 11:20pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/29 "2021-08-16T23:20:41Z")

</div>

Thanks. I get the same. I tried shuffling the indexes of indxs, with which the Julia code runs in 30ms instead, but still 600ms to the python code. Even a plain loop without turbo or threading runs in 145ms, thus either we are not measuring what we are expecting to measure, or the original difference of the codes is somewhere else.

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [August 17, 2021, 12:32am UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/30 "2021-08-17T00:32:40Z")

</div>

> [@lmiq](#):
>
> (from ~20 to about ~13s in my computer).

> [@rmeinl](#):
>
> ```julia
> # NaiveGreedy old 
> 11.923 s (82912 allocations: 15.02 MiB)
> 
> # NaiveGreedy with @tturbo
> 12.853 s (27 allocations: 8.89 MiB)
> 
> ```

Any easy example I can copy/paste?  
Also, what CPUs are you both using?

Also, the size of `current_values`, `X`, and `idxs`?

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 17, 2021, 1:51am UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/31 "2021-08-17T01:51:33Z")

</div>

I’m not sure if this will really help. But as far as I understand, the original problem was that this [python script](https://gist.github.com/lmiq/828133335a83088e63f21152416c7f7c#file-apricot-py) runs in 15s, while [this julia script](https://gist.github.com/lmiq/828133335a83088e63f21152416c7f7c#file-apricot_naivegreedy_old-jl) runs in 26s.

The julia script there uses `@threads`, which if replaced by `@tturbo` (the two `get_gains!` functions are there), accelerates to 22s (here). Thus `@threads` is doing a poor job, `@tturbo` is much better, something somewhat expected since the loop does a very cheap calculation.

Why exactly the python script is still faster is not clear to me yet, but I am inclined to believe that the `get_gains!` function and the efficiency of that parallelization/vectorization is not anymore related to the difference. That is because when we tried to trim down the peformance of that function, [here](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/24) and [here](https://github.com/rmeinl/apricot-julia/blob/main/src/calc_gains.py), it seems that Julia is doing fine relative to Numba (with or without `@turbo`).

The “solution” went on on rewriting the algorithm, and the improvements proposed above led [to this](https://gist.github.com/lmiq/828133335a83088e63f21152416c7f7c#file-apricot_naivegreedy-jl) “naive greedy” version which runs in 13s, but with the same “hot loop above”, and the improvement of the [“lazy greedy” version](https://gist.github.com/lmiq/828133335a83088e63f21152416c7f7c#file-apricot_lazygreedy-jl), which runs in 7s.

Thus, part of the “original problem” was the poor performance of `@threads` for a loop that does very cheap calculations, but the greatest improvements came from changing other things not related to that loop. I still find the original problem interesting because, while clearly the path of removing allocations etc is expected to improve the Julia code, it is not completely evident where the Python script is getting those 7-10s advantage in the original implementations (and it is not in the Numba jit part).

---

<div class="post-metadata">

**Author:** ![genkuroki](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/genkuroki/32/18030_2.png) [@genkuroki](https://discourse.julialang.org/u/genkuroki)\
**Post date:** [August 17, 2021, 9:49am UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/32 "2021-08-17T09:49:28Z")

</div>

On my Windows 10 Python 3.8.5 environment, the execution time of `fit(X=X_digits, k=k)` in [python\_reimpl.ipynb](https://github.com/rmeinl/apricot-julia/blob/5f130f846f8b7f93bb4429e2b182f0765a61035c/notebooks/python_reimpl.ipynb) is about 14-15 seconds. See [https://github.com/genkuroki/public/blob/main/0016/apricot/python\_reimpl.ipynb](https://github.com/genkuroki/public/blob/main/0016/apricot/python_reimpl.ipynb)

I have made my own direct translation of python\_reimpl.ipynb to Julia: [julia\_translation\_of\_python\_reimpl.ipynb](https://github.com/genkuroki/public/blob/main/0016/apricot/julia_translation_of_python_reimpl.ipynb).

That translation does not use LoopVectorizations.jl, only uses `Threads.@threads`. It is just a simple direct translation that contains nothing special.

Screenshot for line-by-line comparison between the Python version and the Julia version:

 ![image](https://global.discourse-cdn.com/julialang/original/3X/a/f/af220958438e9c86a8503fec05d1b488763a6659.jpeg)

In my Julia 1.6.2 environment, the execution time of `fit(X_digits, k)` in that direct translation is about 12-13 seconds.

The plots of the two results are shown below.

 ![python](https://global.discourse-cdn.com/julialang/original/3X/3/a/3a12cee8dee4281aa3ec9526433780eb2284d5ae.png)

 ![julia](https://global.discourse-cdn.com/julialang/original/3X/c/0/c0477abe1b92eff5ac2af05d2b1d4360d66b1ded.png)

Python 3.8.5 Numba: 13～14 sec  
↓  
↓ straightforward simple translation  
↓  
Julia 1.6.2: 12～13 sec

In my experience, Julia tends to be a bit faster than Numba when things go well in general; Numba is also fast enough and quite useful, so I encourage my friends to use Numba. But Numba requires special limiting conditions to be successful; it can’t be “anything goes” like Julia. Particular attention should be paid to the use of multiple libraries in combination. For example, take a look at the following:

> **[Why Numba and Cython are not substitutes for Julia - Stochastic Lifestyle](http://www.stochasticlifestyle.com/why-numba-and-cython-are-not-substitutes-for-julia/)**
>
> Sometimes people ask: why does Julia need to be a new language? What about Julia is truly different from tools like Cython and Numba? The purpose of this blog post is to describe how Julia’s design gives a very different package development...

EDIT1: Fix a logical bug of [julia\_translation\_of\_python\_reimpl.ipynb](https://github.com/genkuroki/public/blob/main/0016/apricot/julia_translation_of_python_reimpl.ipynb) and update the image.

EDIT2: Add a screenshot for line-by-line comparison.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 17, 2021, 10:40am UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/33 "2021-08-17T10:40:34Z")

</div>

Can you readily see now what’s so bad about this script? [https://gist.github.com/lmiq/828133335a83088e63f21152416c7f7c#file-apricot\_naivegreedy\_old-jl](https://gist.github.com/lmiq/828133335a83088e63f21152416c7f7c#file-apricot_naivegreedy_old-jl)

---

<div class="post-metadata">

**Author:** ![genkuroki](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/genkuroki/32/18030_2.png) [@genkuroki](https://discourse.julialang.org/u/genkuroki)\
**Post date:** [August 17, 2021, 11:41am UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/34 "2021-08-17T11:41:09Z")

</div>

As already pointed out, `idxs = findall(==(0), mask)` causes huge memory allocation.

The only operation needed is to remove the element `idxs[idx]` from the array `idxs`. A straightforward Julia translation would be `popat!(idxs, idx)`, even if there is a better way.

[Document of `Base.popat!`](https://docs.julialang.org/en/v1/base/collections/#Base.popat!)

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 17, 2021, 12:47pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/35 "2021-08-17T12:47:35Z")

</div>

Well, I do not sort of agree that that was a straightforward translation. You improved what was being done, at least as far as I can understand. The `np.where` command in python is returning the array of elements for which `mask==0`:

```python
>>>> import numpy as np
>>>> mask = np.random.randint(0,high=10,size=10)
>>>> mask
array([2, 1, 0, 1, 4, 6, 0, 4, 3, 3])
>>> idxs = np.where(mask == 0)[0]
>>> idxs
array([2, 6])

```

This seems equivalent to use `findall` in Julia:

```julia
julia> mask = rand(0:10,10);

julia> idxs= findall(isequal(0),mask)
2-element Vector{Int64}:
 1
 4

```

Thus, what is the miracle python is doing there? Why that findall is slowing down so much the Julia code but not Python one?

IMO the “straighforward” translation would be pretty much what the OP posted originally, and while I agree that it can be improved (as you did), I don’t see why it is 50% slower in Julia than in Python.

---

<div class="post-metadata">

**Author:** ![stillyslalom](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stillyslalom/32/45687_2.png) [@stillyslalom](https://discourse.julialang.org/u/stillyslalom)\
**Post date:** [August 17, 2021, 1:03pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/36 "2021-08-17T13:03:24Z")

</div>

Because `findall(==(0), mask)` grows incrementally by `push!`ing new elements, it requires several copies and is probably hard if not impossible to SIMD. It’s faster to use `findall(mask .== 0)`, which generates a BitVector that allows for efficient determination of the output size (probably `popcnt` on the underlying `UInt64` storage). Python is probably doing something similar.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 17, 2021, 1:09pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/37 "2021-08-17T13:09:34Z")

</div>

That is a nice insight. Unfortunately my microbenchmarks indicate that `findall` is faster than `np.where`. But in that respect I must assume that I am not completely confident that I’m benchmarking the python script correctly:

```python
>>> mask = np.random.randint(0,high=10,size=1_000_000)
>>> 1000*timeit.timeit("np.where(mask==0)", number=1, globals=globals())
17.385129001922905 # miliseconds
>>> 

```

```julia
julia> mask = rand(0:10,1_000_000);

julia> @btime findall(isequal(0),$mask)
  2.366 ms (18 allocations: 2.00 MiB)

```

---

<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:** [August 17, 2021, 1:12pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/38 "2021-08-17T13:12:01Z")

</div>

Interesting. Look at this:

```julia
jl> @btime findall(==(0), r) setup=(r=rand((0,1), 100_000));
  624.500 μs (17 allocations: 1.00 MiB)

jl> @btime findall(r .== 0) setup=(r=rand((0,1), 100_000));
  68.600 μs (5 allocations: 402.48 KiB)

```

Here’s a direct comparison to numpy:

```julia
In [2]: mask = np.random.randint(0,high=10,size=1_000_000)

In [3]: %timeit np.where(mask==0)
1.78 ms ± 7.82 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

```

Julia:

```julia
jl> @btime findall(==(0), r) setup=(r=rand(0:10, 1_000_000));
  1.770 ms (18 allocations: 2.00 MiB)

jl> @btime findall(r .== 0) setup=(r=rand(0:10, 1_000_000));
  575.500 μs (6 allocations: 831.19 KiB)

```

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [August 17, 2021, 3:31pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/39 "2021-08-17T15:31:06Z")

</div>

> [@lmiq](#):
>
> Thus, what is the miracle python is doing there? Why that findall is slowing down so much the Julia code but not Python one?

Python and julia have very differenc GCs that are optimized for different things. I wonder if python’s gc is just better optimized for this particular allocation pattern. Julia’s GC is noncompacting, mark and sweep, probably optimized for high throughput with large (say big matrix) allocations, whereas python’s is based on reference counting, probably optimized for many small allocations since that’s the way you are supposed to write python code.

I say _probably_ since I’m not an expert at garbage collection, but merely guessing.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [August 17, 2021, 3:36pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/40 "2021-08-17T15:36:34Z")

</div>

ehhh, guys, `%timeit` turns off GC during the timing

[Previous page](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414.md?page=1)

[Next page](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414.md?page=3)
