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).
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
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
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]
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 @carstenbauer 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.
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.
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