# When appllying roll rank function, how much faster Julia can be compared to Python?

**URL:** <https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066>\
**Category:** New to Julia\
**Created:** [March 18, 2022, 5:10am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066 "2022-03-18T05:10:31Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Brian1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/brian1/32/49250_2.png) [@Brian1](https://discourse.julialang.org/u/Brian1)\
**Post date:** [March 18, 2022, 5:10am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/1 "2022-03-18T05:10:31Z")

</div>

In Python, I tried many ways to apply roll rank function to a list, the speed is too slow. When the list length is about 100000, the fastest way in Python I tried takes more than 100ms.

Then in Juila, I tried the similar way used in Python, It still takes 80ms to the calculation.

So, my question is, Is there some way I am missing in using Julia, or is it just a matter of Julia limitation?  
Here is my test code (I test it in Julia 1.8-beta1):

```julia
partslice(x::Int,window::Int,step::Int)=begin
    partitionsize=div(x-window,step)+1+1
    res=Vector{NTuple{3,Int}}(undef,partitionsize)
    for i=1:partitionsize
        if i==1
            startloc=1
            endloc=window
            starti=1
        elseif i==partitionsize
            startloc=x-window+1
            endloc=x
            starti=res[i-1][2]-startloc+2
        else
            startloc=(i-1)step+1
            endloc=startloc+window-1
            starti=res[i-1][2]-startloc+2
        end
        res[i]=(startloc,endloc,starti)
    end
    res
end

function rollRank(arr::AbstractArray,starti::Int=1)
    res=Vector{Float32}(undef,size(arr))
    sorted_res=sort(arr[1:starti-1])
    for i=starti:size(res,1)
        iloc=searchsortedfirst(sorted_res,arr[i])
        insert!(sorted_res,iloc,arr[i])
        res[i]=100*(iloc-1)/size(sorted_res,1)
    end
    res[starti:end]
end

rollRankVec(arr::Vector,window::Int,n::Int)=begin
    res=Vector{Float32}(undef,size(arr))
    slicevec=partslice(size(arr,1),window,n)
    @inbounds for (startloc,endloc,starti) in slicevec
        res_=rollRank(@view(arr[startloc:endloc]),starti)
        slicerange=startloc+starti-1:endloc
        res[slicerange]=res_
    end
    res
end

#TEST:

testdata=rand(100_000)

#first time

@time rollRankVec(testdata,3000,1000);

#0.089189 seconds (965.58 k allocations: 18.778 MiB)

```

---

<div class="post-metadata">

**Author:** ![amrods](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/amrods/32/2543_2.png) [@amrods](https://discourse.julialang.org/u/amrods)\
**Post date:** [March 18, 2022, 5:37am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/2 "2022-03-18T05:37:20Z")

</div>

is `sorted_res` always the same size as `res` in `rollRank()`? perhaps you can initialize it with a given size rather than inserting elements.

---

<div class="post-metadata">

**Author:** ![Brian1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/brian1/32/49250_2.png) [@Brian1](https://discourse.julialang.org/u/Brian1)\
**Post date:** [March 18, 2022, 5:57am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/3 "2022-03-18T05:57:57Z")

</div>

Sorry, there is something wrong in the code,  
I have changed `sorted_res=[]` to `sorted_res=sort(arr[1:starti-1])`.  
As you said,

> [@amrods](#):
>
> is `sorted_res` always the same size as `res` in `rollRank()`

it is. But it can not be initialized, in the text inline, I use function

> [@Brian1](#):
>
> `searchsortedfirst`

If I initialize sorted\_res, this function wil return wired value:

```julia
sorted_res=Vector{Float32}(undef,1000)

searchsortedfirst(sorted_res,10)

#995

```

---

<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 18, 2022, 5:58am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/4 "2022-03-18T05:58:23Z")

</div>

It’s a bit too much to look into at the moment, but this immediately caught my eye:

> [@Brian1](#):
>
> `res=Vector{Tuple}(undef,partitionsize)`

That’s a vector with an abstract element type. Make sure to make it concrete, as in `Vector{NTuple{3, Int}}`, or whatever is appropriate.

Repeated `insert!`s seems expensive. Is that necessary?

> [@Brian1](#):
>
> `res=Vector{Float32}(undef,size(arr))`

It’s not clear how you can assume that this should be `Float32`.

You’re kind of abusing short-form function notation. The idiomatic way is to write

```julia
function foo(...) 
    # code
end

```

---

<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 18, 2022, 6:12am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/5 "2022-03-18T06:12:52Z")

</div>

BTW, would you mind explaining what these functions do? It’s easier to review code when you know what it’s supposed to be doing.

---

<div class="post-metadata">

**Author:** ![sylvaticus](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sylvaticus/32/203883_2.png) [@sylvaticus](https://discourse.julialang.org/u/sylvaticus)\
**Post date:** [March 18, 2022, 6:26am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/6 "2022-03-18T06:26:10Z")

</div>

Seems related to sorting a multidimensional arrays…

> **[RANK function](https://www.ibm.com/docs/en/informix-servers/12.10?topic=expressions-rank-function)**
>
> The RANK function is an OLAP ranking function that calculates a ranking value for each row in an OLAP window. The return value is an ordinal number, which is based on the required ORDER BY expression in the OVER clause.

---

<div class="post-metadata">

**Author:** ![amrods](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/amrods/32/2543_2.png) [@amrods](https://discourse.julialang.org/u/amrods)\
**Post date:** [March 18, 2022, 6:26am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/7 "2022-03-18T06:26:16Z")

</div>

> [@DNF](#):
>
> That’s a vector with an abstract element type. Make sure to make it concrete, as in `Vector{NTuple{3, Int}}` , or whatever is appropriate.

Wouldn’t it be even faster to work with an array of numbers rather than a vector of tuples?

> [@Brian1](#):
>
> I have changed `sorted_res=[]` to `sorted_res=sort(arr[1:starti-1])` .

Isn’t that the same when `starti == 1` (which is the default value)?

---

<div class="post-metadata">

**Author:** ![Brian1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/brian1/32/49250_2.png) [@Brian1](https://discourse.julialang.org/u/Brian1)\
**Post date:** [March 18, 2022, 6:39am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/8 "2022-03-18T06:39:55Z")

</div>

Yes, I changed the

> [@Brian1](#):
>
> res=Vector{Tuple}(undef,partitionsize)

to more crrect way, but it seems has no fluence in performance.

So far, in my opinion, `insert!` is necessary.

> [@DNF](#):
>
> It’s not clear how you can assume that this should be `Float32` .

Yeah I use Float32 because it nees less memory.

---

<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 18, 2022, 6:42am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/9 "2022-03-18T06:42:53Z")

</div>

> [@amrods](#):
>
> Wouldn’t it be even faster to work with an array of numbers rather than a vector of tuples?

I don’t think so. Depends on what you are using it for. Vectors of tuples shouldn’t have any performance issues.

But vectors of an _abstract_ tuple type is definitely bad.

> [@amrods](#):
>
> Isn’t that the same when `starti == 1` (which is the default value)?

It’s not the same, since the former creates a `Vector{Any}`, and the latter creates a correctly typed vector.

---

<div class="post-metadata">

**Author:** ![Brian1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/brian1/32/49250_2.png) [@Brian1](https://discourse.julialang.org/u/Brian1)\
**Post date:** [March 18, 2022, 6:56am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/10 "2022-03-18T06:56:30Z")

</div>

I am targeting to calculate the rank value compared to it’s preceedents, which is a subvector with fixed window.  
For exsample:  
I have a vector named myvec containing 100 elements. If I set the window 20 and step 10;

1. for i=1:20, I calculate percentofscore(myvec[i], myvec[1:i-1])
2. step 10 foreward, for i=20:30, I calculate percentofscore( myvec[i], myvec[10:i-1])  
.  
.  
.  
At last, concatenate these.

---

<div class="post-metadata">

**Author:** ![Brian1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/brian1/32/49250_2.png) [@Brian1](https://discourse.julialang.org/u/Brian1)\
**Post date:** [March 18, 2022, 7:03am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/11 "2022-03-18T07:03:21Z")

</div>

It is the same when `starti==1`, but starti is changing.

---

<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 18, 2022, 7:33am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/12 "2022-03-18T07:33:36Z")

</div>

> [@Brian1](#):
>
> It is the same when `starti==1`

No, the types are different, as mentioned.

---

<div class="post-metadata">

**Author:** ![Brian1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/brian1/32/49250_2.png) [@Brian1](https://discourse.julialang.org/u/Brian1)\
**Post date:** [March 18, 2022, 8:17am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/13 "2022-03-18T08:17:08Z")

</div>

Yes, types diference.  
But It seems still no performance influence. Even worse, I test it, it takes 180ms, more than Python. Where is wrong?

---

<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 18, 2022, 8:47am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/14 "2022-03-18T08:47:14Z")

</div>

Did you time your code twice, to avoid timing compilation? Because I get this when running your code:

```julia
1.7.2> @time rollRankVec(testdata,3000,1000); # first run, includes compilation
  0.215553 seconds (386.24 k allocations: 28.302 MiB, 4.52% gc time, 88.10% compilation time)

1.7.2> @time rollRankVec(testdata,3000,1000); # second run
  0.028715 seconds (504 allocations: 8.202 MiB)

```

So, 28ms, which seems, well, I dunno, but less bad. Notice the difference in memory allocations, and that 88% of the time is compilation in the first run.

---

<div class="post-metadata">

**Author:** ![Brian1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/brian1/32/49250_2.png) [@Brian1](https://discourse.julialang.org/u/Brian1)\
**Post date:** [March 18, 2022, 9:10am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/15 "2022-03-18T09:10:06Z")

</div>

Yes, of course. The difference lies in computer. My computer is out of time. Your computer is wonderful, maybe it has the 12th generation cpu?

---

<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 18, 2022, 9:29am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/16 "2022-03-18T09:29:13Z")

</div>

I’m confused. Here’s the timing you showed:

> [@Brian1](#):
>
> ```julia
> @time rollRankVec(testdata,3000,1000);
> 
> #0.089189 seconds (965.58 k allocations: 18.778 MiB)
> 
> ```

It uses 89ms, and it has a lot of allocations, which does not seem right. Is this not up to date? Can you show your latest timing?

Also, what version of Julia are you using?

---

<div class="post-metadata">

**Author:** ![Brian1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/brian1/32/49250_2.png) [@Brian1](https://discourse.julialang.org/u/Brian1)\
**Post date:** [March 18, 2022, 9:37am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/17 "2022-03-18T09:37:27Z")

</div>

It is maybe because the type instability you mentioned above. After correct that, the allocations output is the same to yours.

```julia
@time rollRankVec(testdata,3000,1000);
0.074555 seconds (504 allocations: 8.202 MiB)

```

The Julia version I used is 1.8.0-beta1

---

<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 18, 2022, 9:50am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/18 "2022-03-18T09:50:39Z")

</div>

It looks to me like the most obvious problems are fixed. In order to speed this up, I think a bit more thorough work is needed. Re-using vectors instead of creating new ones all the time. Make sure that `insert!` doesn’t need to re-allocate many times.

---

<div class="post-metadata">

**Author:** ![Brian1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/brian1/32/49250_2.png) [@Brian1](https://discourse.julialang.org/u/Brian1)\
**Post date:** [March 18, 2022, 10:43am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/19 "2022-03-18T10:43:07Z")

</div>

Yes, Thanks.  
It is surprising that your computer is twice faster than mine. Probably, the most direct way is just to upgrade the cpu of my computer. May I ask you what the cpu and os you are using in your computer?

---

<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 18, 2022, 10:55am UTC](https://discourse.julialang.org/t/when-appllying-roll-rank-function-how-much-faster-julia-can-be-compared-to-python/78066/20 "2022-03-18T10:55:42Z")

</div>

I really hope there’s a better way than upgrading the computer 😃

It’s a work laptop, a couple of years old: Intel(R) Core™ i7-9750H CPU @ 2.60GHz in a Dell Precision 5540. Thin and light, but quite pricey, I think.

Windows 10.