# 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:** 17\
**Page:** 3

<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, 4:20pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/41 "2021-08-17T16:20:00Z")

</div>

That’s a good guess. But does not explain it:

@tturbo version of: [Julia:](https://gist.github.com/lmiq/828133335a83088e63f21152416c7f7c#file-apricot_naivegreedy_old-jl)  
Fitting time:  
20.318218 seconds (22.10 k allocations: 8.795 GiB, 0.36% gc time)  
125819832 9897.307670089082

([python:](https://gist.github.com/lmiq/828133335a83088e63f21152416c7f7c#file-apricot-py))

Fitting time: 12.01971983909607  
125818832 9897.307670089194

(not using timeit in these)

---

<div class="post-metadata">

**Author:** ![paulmelis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paulmelis/32/35063_2.png) [@paulmelis](https://discourse.julialang.org/u/paulmelis)\
**Post date:** [August 17, 2021, 4:21pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/42 "2021-08-17T16:21:59Z")

</div>

> [@baggepinnen](#):
>
> 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.

What’s called the “garbage collector” in Python is a separate GC that is only used to break reference cycles. This GC supplements the reference counting scheme that is used for regular memory management. So the disabling of the GC that `%timeit` does will only stop the cycle collector, regular reference counting will still be active. But this can still have an effect on the timing outcome, of course.

---

<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, 5:16pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/43 "2021-08-17T17:16:23Z")

</div>

No miracles.

I have also made a version that uses bitvector masking to create the index vectors `idxs` repeatedly (with huge allocations), apart from [the Julia version using `popat!`](https://github.com/genkuroki/public/blob/main/0016/apricot/julia_translation_of_python_reimpl.ipynb). The bitvector masking Julia version is a translation more straightforward than the `popat!` version.

The bitvector masking version appears to be a completely straightforward translation, line by line, from the Python version. Look at the screenshot of the Jupyter notebooks, [Julia bitvector masking version](https://github.com/genkuroki/public/blob/main/0016/apricot/bitvector_masking_version.ipynb) and [Python version](https://github.com/genkuroki/public/blob/main/0016/apricot/python_reimpl.ipynb), below.

 ![image](https://global.discourse-cdn.com/julialang/original/3X/5/4/54ce90b64577508837b81801b8e712d8fcd6ba64.jpeg)

The results of execution time are as follows:

- Julia popat! version: 12-13 seconds (15MB)
- Julia bitvector masking version: about or under 14 seconds (4.3GB)
- Python version: 14-15 seconds

If there is a miracle on Python, then there must be a miracle on Julia. In fact there are no miracles anywhere.

EDIT: `axes(mask, 1)[mask]` → `findall(mask)`

---

<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, 5:21pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/44 "2021-08-17T17:21:14Z")

</div>

Ok, here is a MWE, the Juila code is 10x slower than the Python code:

In Julia:

```julia
function fit()
    local idxs
    mask = zeros(Int, 500_000)
    for i in 1:1000
       idxs = findall(==(0), mask)
    end
    return length(idxs)
end
println(fit())
@time fit();
~               

```

Python:

```julia
import time
import numpy as np

def fit():
    mask = np.zeros(500_000)
    for i in range(0,1000):
        idxs = np.where(mask == 0)[0]
    return idxs.size

print(fit())
tic = time.time()
fit()
toc0 = time.time() - tic
print(toc0)

```

If one replaces `findall(==(0),mask)` by `findall(mask .== 0)`, the Julia code improves a lot, but it is still 50% slower than the python one.

At the end, the thing is this:

```julia
julia> @btime findall($mask .== 0);
  524.255 μs (6 allocations: 3.88 MiB)

julia> @btime findall(==(0),$mask);
  3.105 ms (20 allocations: 5.00 MiB)

```

IMO that places some questioning on possible improvements on `findall`.

> [@genkuroki](#):
>
> appears to be a completely straightforward translation, line by line

I appreciate that, but I do not think that translating `np.zeros(n)` to `trues(n)`, and masking by the bit vector are straightforward translations. What I wanted to know is where the difference was coming from, not if a faster version could be written. The “problem” with findall is what explains most of it, although I think I have noticed an important time gain when removed the call to `argmax`, something that was not noticeable in the Python version.

---

<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, 6:35pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/45 "2021-08-17T18:35:00Z")

</div>

Since there is no direct counterpart to Python’s `np.where` in Julia (`findall(==(0), mask)` is also not considered the strictly direct counterpart of `np.where(mask == 0)[0]`), that level of difference is unavoidable.

If you are dissatisfied, please rewrite the code using Julia’s BitVector counterpart on the Python side.

Also, note that the number of characters in the Julia side code is reduced. It would be odd to prohibit something that can be written simply on the Julia side.

It would be a definite fact that miracle does not exist.

If we had written the code normally on the Julia side, we could have done it faster than the Python Numba version, without having to use a particularly excellent tool like LoopVectorization.jl.

It would be, however, very interesting if someone could report on the details of the implementation of `np.where` 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, 6:46pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/46 "2021-08-17T18:46:35Z")

</div>

Looks like the core method is defined here: [https://github.com/numpy/numpy/blob/e69faef03428b82f5651a5fb521610ddea2bd22a/numpy/core/src/multiarray/item\_selection.c#L2600-L2633](https://github.com/numpy/numpy/blob/e69faef03428b82f5651a5fb521610ddea2bd22a/numpy/core/src/multiarray/item_selection.c#L2600-L2633)

Linked PR: [https://github.com/numpy/numpy/pull/4370/files](https://github.com/numpy/numpy/pull/4370/files)

It appears to use multithreading beyond some input array size threshold, which the Julia implementation doesn’t yet allow.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [August 17, 2021, 6:47pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/47 "2021-08-17T18:47:38Z")

</div>

Note that numpy is BSD-3 licensed.

---

<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, 6:47pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/48 "2021-08-17T18:47:54Z")

</div>

My point is that for me, and probably for others, it was not obvious at all that `findall(==(0),x)` could be so much worse than `findall(x .== 0)`. Personally, I would even think that the opposite would be true, since it its evident that `x .== 0` allocates an intermediate vector that could be avoided.

It might well be that depending on the test function, size and type of vectors, the implementation of findall is the best one can get considering pros and cons. But I, at least, learnt something (about Julia) here.

---

<div class="post-metadata">

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

</div>

> [@lmiq](#):
>
> ```julia
> julia> @btime findall(==(0),$mask);
> 3.105 ms (20 allocations: 5.00 MiB)
> 
> ```

Interestingly, it appears this slowness has already been fixed in `master` [EDIT:] and 1.7. In `array.jl` line 2280:

```julia
# Broadcasting is much faster for small testf, and computing
# integer indices from logical index using findall has a negligible cost
findall(testf::Function, A::AbstractArray) = findall(testf.(A))

```

So this performs the same as `findall(mask .== 0)`. It seems that `findall` was written generically for any collection, and this specialization for `AbstractArray` was added recently.

---

<div class="post-metadata">

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

</div>

Diving into NumPy, the relevant C code is here.

[https://github.com/numpy/numpy/blob/e69faef03428b82f5651a5fb521610ddea2bd22a/numpy/core/src/multiarray/item\_selection.c#L2569-L2653](https://github.com/numpy/numpy/blob/e69faef03428b82f5651a5fb521610ddea2bd22a/numpy/core/src/multiarray/item_selection.c#L2569-L2653)

The first thing that happens is that NumPy counts the number of nonzeros. If the number of nonzeros is `0`, then it just returns an empty array:  
[https://github.com/numpy/numpy/blob/e69faef03428b82f5651a5fb521610ddea2bd22a/numpy/core/src/multiarray/item\_selection.c#L2596-L2598](https://github.com/numpy/numpy/blob/e69faef03428b82f5651a5fb521610ddea2bd22a/numpy/core/src/multiarray/item_selection.c#L2596-L2598)

We can implement that shortcut in Julia:

```julia
julia> function fit()
           local idxs
           mask = zeros(Int, 500_000)
           for i in 1:1000
              mask_nz = Array{Bool}(mask)
              num_nz = count(mask_nz)
              if num_nz == 0
                 idxs = Int[]
              else
                 idxs = findall(mask_nz)
              end
           end
           return length(idxs)
       end
fit (generic function with 1 method)

julia> @time fit()
  0.551720 seconds (3.00 k allocations: 480.835 MiB, 1.18% gc time)
0

```

In comparison, the Python code takes 0.7 seconds:

```python
In [6]: import time
   ...: import numpy as np
   ...: 
   ...: def fit():
   ...: mask = np.zeros(500_000)
   ...: for i in range(0,1000):
   ...: idxs = np.where(mask == 0)[0]
   ...: return idxs.size
   ...: 
   ...: print(fit())
   ...: tic = time.time()
   ...: fit()
   ...: toc0 = time.time() - tic
   ...: print(toc0)
   ...: 
500000
0.7331986427307129

```

---

<div class="post-metadata">

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

</div>

The version above has an issue. What happens if `mask` contains values that are not `0` or `1`. In that case, we can use `count` which turns out to be even faster.

```julia
julia> function fit()
           local idxs
           mask = zeros(Int, 500_000)
           for i in 1:1000
              num_nz = count(!=(0),mask)
              if num_nz == 0
                 idxs = Int[]
              else
                 idxs = findall(!=(0), mask)
              end
           end
           return length(idxs)
       end
fit (generic function with 1 method)

julia> @time fit()
  0.289683 seconds (1.00 k allocations: 3.891 MiB)
0

```

---

<div class="post-metadata">

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

</div>

I just realized that I inverted the problem in the process of reverse engineering NumPy, here’s the fix:

```julia
julia> function fit()
           local idxs
           mask = zeros(Int, 500_000)
           for i in 1:1000
              num_nz = count(==(0),mask)
              if num_nz == 0
                 idxs = Int[]
              elseif num_nz == length(mask)
                 idxs = eachindex(mask)
              else
                 idxs = findall(==(0), mask)
              end
           end
           return length(idxs)
       end
fit (generic function with 1 method)

julia> @time fit()
  0.288805 seconds (2 allocations: 3.815 MiB)
500000

```

---

<div class="post-metadata">

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

</div>

> [@mkitti](#):
>
> We can implement that shortcut in Julia:

I don’t think you have to, if you use `master`. That version of `findall(==(0), mask)` now ends up calling the version in `bitarray.jl`, which starts like this:

```julia
function findall(B::BitArray)
    nnzB = count(B)
    I = Vector{eltype(keys(B))}(undef, nnzB)
    nnzB == 0 && return I

```

So I believe it’s already similar to `NumPy` by counting non-zeros, [EDIT: my order was wrong] pre-allocating, and shortcutting if there are none.

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [August 17, 2021, 7:33pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/54 "2021-08-17T19:33:00Z")

</div>

> [@mkitti](#):
>
> ```julia
> for i in 1:1000
> num_nz = count(==(0),mask)
> 
> ```

Do you need to `count` for each iteration?

---

<div class="post-metadata">

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

</div>

> [@jzr](#):
>
> Do you need to `count` for each iteration?

I’m assuming that the loop is for benchmarking purposes. Otherwise, the whole operation could be just done once.

---

<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, 8:11pm UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/56 "2021-08-17T20:11:49Z")

</div>

I really think that benchmarking code should be separated from the code to be benchmarked. When benchmarking loops are mixed into the main code, it makes it hard to understand what could be optimized and improved.

---

<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 18, 2021, 12:00am UTC](https://discourse.julialang.org/t/julia-beginner-from-python-numba-outperforms-julia-in-rewrite-any-tips-to-improve-performance/66414/57 "2021-08-18T00:00:28Z")

</div>

Truely straightforward translation! 🥳

 ![image](https://global.discourse-cdn.com/julialang/original/3X/3/7/378c04b58339baf6bce6dbeba90be03fe57e08ad.jpeg)  
Jupyter notebook: [https://github.com/genkuroki/public/blob/main/0016/apricot/float64\_vector\_version.ipynb](https://github.com/genkuroki/public/blob/main/0016/apricot/float64_vector_version.ipynb)

- Python `mask = np.zeros(n)` → Julia `mask = zeros(n)`
- Python `mask[best_idx] = 1` → Julia `mask[best_idx] = 1`
- Python `idxs = np.where(mask == 0)[0]` → `idxs = findall(mask .== 0)`

The last one is the essential part again.

The results of the execution time are as below:

- Python Numba version: 14-15 sec
- Julia `findall(mask .== 0)` version: about 14 sec

Explanation:

- The type of `mask` is `Vector{Float64}`. (Normally, masking is done with `Bool` values and not with `Float64` ones.)
- `mask .== 0` becomes of type `BitVector`.
- `findall(x::BitVector)` is very fast. 😊

Conclusion:

- Numba does **not** outperform Julia in the truely straightforward translation.

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