How to prevent type instability in for loops?

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

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?

AFAIU, this β€œtype instability” is harmless. It is a consequence of the iterator interface 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).

1 Like

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

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
1 Like

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

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

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.

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

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

You can write this more elegantly like this

V[i], V[j] = V[j], V[i] 
1 Like

The second option without warning that I found was:

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 @crstnbr told us, with a warning and without this warning have the same performance.

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.

2 Likes

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.

1 Like

I saw this style in: 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 that is slower.

It’s a nice tip too, thanks @DNF

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

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

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:

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?

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> 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                                               
1 Like