# How to prevent type instability in for loops?

**URL:** <https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508>\
**Category:** Performance\
**Tags:** question\
**Created:** [October 30, 2019, 6:11pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508 "2019-10-30T18:11:49Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ronneesley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ronneesley/32/11072_2.png) [@Ronneesley](https://discourse.julialang.org/u/Ronneesley)\
**Post date:** [October 30, 2019, 6:11pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/1 "2019-10-30T18:11:50Z")

</div>

When we create a **for** loop with range, Julia alert a type of instability in the range created.  
Using the code below.

```julia
v = [1, 2, 3]
function f(v::Array{Int, 1})
    s = 0
    for i = 1:length(v)
        s += v[i]
    end
    
    return s
end

@code_warntype f(v)

```

Julia alert:  
@\_4:: **Union{Nothing, Tuple{Int64,Int64}}**

How to speed up this code preventing this type instability?

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [October 30, 2019, 6:24pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/2 "2019-10-30T18:24:18Z")

</div>

AFAIU, this “type instability” is harmless. It is a consequence of the [iterator interface](https://docs.julialang.org/en/latest/manual/interfaces/#) which returns `nothing` when the end of the iterator is reached. Note that the line you cited from the `@code_warntype` output is colored in yellow (not red, which indicates “true” type instabilities).

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [October 30, 2019, 6:29pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/3 "2019-10-30T18:29:05Z")

</div>

The line is even present when making `v` a `SVector` which encodes its length in the type.

```julia
using StaticArrays
sv = @SVector [1,2,3]
@code_warntype f(sv)

Variables
  #self#::Core.Compiler.Const(f, false)
  v::SArray{Tuple{3},Int64,1,3}
  s::Int64
  @_4::Union{Nothing, Tuple{Int64,Int64}}
  i::Int64

Body::Int64
1 ─ (s = 0)
│ %2 = Main.length(v)::Core.Compiler.Const(3, false)
│ %3 = (1:%2)::Core.Compiler.Const(1:3, false)
│ (@_4 = Base.iterate(%3))
│ %5 = (@_4::Core.Compiler.Const((1, 1), false) === nothing)::Core.Compiler.Const(false, false)
│ %6 = Base.not_int(%5)::Core.Compiler.Const(true, false)
└── goto #4 if not %6
2 ┄ %8 = @_4::Tuple{Int64,Int64}::Tuple{Int64,Int64}
│ (i = Core.getfield(%8, 1))
│ %10 = Core.getfield(%8, 2)::Int64
│ %11 = s::Int64
│ %12 = Base.getindex(v, i)::Int64
│ (s = %11 + %12)
│ (@_4 = Base.iterate(%3, %10))
│ %15 = (@_4 === nothing)::Bool
│ %16 = Base.not_int(%15)::Bool
└── goto #4 if not %16
3 ─ goto #2
4 ┄ return s

```

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [October 30, 2019, 6:31pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/4 "2019-10-30T18:31:58Z")

</div>

> [@Ronneesley](#):
>
> v = [1, 2, 3] function f(v::Array{Int, 1}) s = 0 for i = 1:length(v) s += v[i] end return s end @code\_warntype f(v)

It is possible to write your code without type info, with the same type stability:

```julia
function f1(v)                                                
       s = zero(eltype(v))                                           
       for i in eachindex(v)                                         
           s += v[i]                                                     
       end                                                           
       return s                                                      
end

```

---

<div class="post-metadata">

**Author:** ![Ronneesley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ronneesley/32/11072_2.png) [@Ronneesley](https://discourse.julialang.org/u/Ronneesley)\
**Post date:** [October 30, 2019, 6:36pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/5 "2019-10-30T18:36:51Z")

</div>

Really, I was running a benchmark test with bubblesort algorithm that has two for loops.

It was the first execution that worried me, I know that is the moment that Julia compiles the code, but I forgot to remove it from my analysis.

When I remove the first time using for or while (that no have warnings from @code\_warntype) both have the same performance.

Thank you.

---

<div class="post-metadata">

**Author:** ![Ronneesley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ronneesley/32/11072_2.png) [@Ronneesley](https://discourse.julialang.org/u/Ronneesley)\
**Post date:** [October 30, 2019, 6:41pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/6 "2019-10-30T18:41:01Z")

</div>

Thank @PetrKryslUCSD, eachindex() is a nice tip for this case, but it was a simplified version of my real problem:

```julia
function trocar!(V::Array, i::Int, j::Int)
    t = V[i]
    V[i] = V[j]
    V[j] = t
end

function bubblesort!(numeros::Array{T, 1}) where T <: Number
    for i = length(numeros):-1:2
        for j = 1:i - 1
            if (numeros[j] > numeros[j + 1])
                trocar!(numeros, j, j + 1)
            end
        end
    end

    return numeros
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:** [October 30, 2019, 6:45pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/7 "2019-10-30T18:45:31Z")

</div>

> [@Ronneesley](#):
>
> ```julia
> function trocar!(V::Array, i::Int, j::Int) 
> t = V[i] 
> V[i] = V[j] 
> V[j] = t 
> end
> 
> ```

You can write this more elegantly like this

```julia
V[i], V[j] = V[j], V[i] 

```

---

<div class="post-metadata">

**Author:** ![Ronneesley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ronneesley/32/11072_2.png) [@Ronneesley](https://discourse.julialang.org/u/Ronneesley)\
**Post date:** [October 30, 2019, 6:46pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/8 "2019-10-30T18:46:14Z")

</div>

The second option without warning that I found was:

```julia
function bubblesort_while!(numeros::Array{T, 1}) where T <: Number
    i::Int = length(numeros)
    
    while (i >= 2)
        j::Int = 1
        
        while (j <= i - 1)
            if (numeros[j] > numeros[j + 1])
                trocar!(numeros, j, j + 1)
            end
            
            j += 1
        end
            
        i -= 1
    end

    return numeros
end

```

But like @carstenbauer told us, with a warning and without this warning have the same performance.

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [October 30, 2019, 6:47pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/9 "2019-10-30T18:47:40Z")

</div>

Replace `Array{T, 1}` by `AbstractVector{T}` (or drop it entirely). It is more general and has same performance. Also, drop the `::Int` annotations in the code. They are not necessary.

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [October 30, 2019, 6:50pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/10 "2019-10-30T18:50:38Z")

</div>

Also, be aware that `1:i - 1` means `1:(i-1)` and not `(1:i) - 1`. Maybe that is what you want (I don’t know). Just wanted to point it out because it might not be obvious.

---

<div class="post-metadata">

**Author:** ![Ronneesley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ronneesley/32/11072_2.png) [@Ronneesley](https://discourse.julialang.org/u/Ronneesley)\
**Post date:** [October 30, 2019, 6:54pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/11 "2019-10-30T18:54:44Z")

</div>

I saw this style in: [https://rosettacode.org/wiki/Sorting\_algorithms/Bubble\_sort#Julia](https://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort#Julia)

The suggested algorithm is slower than the code I posted here. I thought that was this syntax, but is the loop suggested at [rosettacode.org](http://rosettacode.org) that is slower.

It’s a nice tip too, thanks @DNF

---

<div class="post-metadata">

**Author:** ![Ronneesley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ronneesley/32/11072_2.png) [@Ronneesley](https://discourse.julialang.org/u/Ronneesley)\
**Post date:** [October 30, 2019, 6:55pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/12 "2019-10-30T18:55:43Z")

</div>

Yep. At the code 1:i - 1 means 1:(i - 1).

---

<div class="post-metadata">

**Author:** ![Ronneesley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ronneesley/32/11072_2.png) [@Ronneesley](https://discourse.julialang.org/u/Ronneesley)\
**Post date:** [October 30, 2019, 7:04pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/13 "2019-10-30T19:04:25Z")

</div>

In a nutshell the best I can do without change the bubble sort algorithm is:

```julia
swap!(V::AbstractVector, i::Int, j::Int) = V[i], V[j] = V[j], V[i] 

function bubblesort!(numbers::AbstractVector{T}) where T <: Number
    for i = length(numbers):-1:2
        for j = 1:i - 1
            if (numbers[j] > numbers[j + 1])
                swap!(numbers, j, j + 1)
            end
        end
    end

    return numbers
end

```

I tried the second way:

```julia
function bubblesort2!(numbers::AbstractVector{T}) where T <: Number
    for i = length(numbers):-1:2, j = 1:i - 1        
        if (numbers[j] > numbers[j + 1])
            swap!(numbers, j, j + 1)
        end
    end

    return numbers
end

```

Both functions have same performance.  
Can I improve it?

---

<div class="post-metadata">

**Author:** ![jebej](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jebej/32/1784_2.png) [@jebej](https://discourse.julialang.org/u/jebej)\
**Post date:** [October 30, 2019, 10:00pm UTC](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/14 "2019-10-30T22:00:28Z")

</div>

Both functions are the same so it makes sense they have the same performance.

An easy way to increase performance is to tell julia all array indexing operations in the loop are `@inbounds` (which they are here):

```julia
julia> function bubblesort1!(V::AbstractVector{T}) where T <: Number
           for i = length(V):-1:2, j = 1:(i-1)            
               if (V[j] > V[j+1])                                   
                   V[i], V[j] = V[j], V[i]                          
               end                                                  
           end                                                      
       return V                                                     
       end       

julia> @benchmark bubblesort1!(x) setup=x=rand(10000)               
BenchmarkTools.Trial:                                               
  memory estimate: 0 bytes                                         
  allocs estimate: 0                                               
  --------------                                                    
  minimum time: 134.355 ms (0.00% GC)                           
  median time: 136.300 ms (0.00% GC)                           
  mean time: 136.332 ms (0.00% GC)                           
  maximum time: 138.147 ms (0.00% GC)                           
  --------------                                                    
  samples: 37                                              
  evals/sample: 1                                               
                                                                    
julia> function bubblesort2!(V::AbstractVector{T}) where T <: Number
           @inbounds for i = length(V):-1:2, j = 1:(i-1)            
               if (V[j] > V[j+1])                                   
                   V[i], V[j] = V[j], V[i]                          
               end                                                  
           end                                                      
       return V                                                     
       end                                                          
bubblesort2! (generic function with 1 method)                       
                                                                    
julia> @benchmark bubblesort2!(x) setup=x=rand(10000)               
BenchmarkTools.Trial:                                               
  memory estimate: 0 bytes                                         
  allocs estimate: 0                                               
  --------------                                                    
  minimum time: 120.128 ms (0.00% GC)                           
  median time: 121.617 ms (0.00% GC)                           
  mean time: 121.776 ms (0.00% GC)                           
  maximum time: 125.037 ms (0.00% GC)                           
  --------------                                                    
  samples: 42                                              
  evals/sample: 1                                               

```