Sorting inhomogeneous tuples on 0.62

General Usage Performance
1

I need to sort arrays of inhomogeneous tuples. On julia 0.62, something is bad, performance wise, which was luckily fixed in 0.7.

I wanted to ask whether anyone knows workarounds on 0.6. Sample code below:

rr = [(rand(Int32), rand(Float32)) for i = 1:10_000];
sort(rr); gc(); @time sort(rr);
#  0.014868 seconds (573.58 k allocations: 8.871 MiB)

rr = [(rand(Float32), rand(Float32)) for i = 1:10_000];
sort(rr); gc(); @time sort(rr);
#  0.001878 seconds (9 allocations: 117.641 KiB)
versioninfo()
#Julia Version 0.6.2
#Commit d386e40 (2017-12-13 18:08 UTC)

Look at the number of allocations, and also the 10x runtime difference. This went away in 0.7:

rr = [(rand(Int32), rand(Float32)) for i = 1:10_000];
sort(rr); GC.gc(); @time sort(rr);
#   0.000960 seconds (8 allocations: 117.563 KiB)
rr = [(rand(Float32), rand(Float32)) for i = 1:10_000];
sort(rr); GC.gc(); @time sort(rr);
#    0.001417 seconds (8 allocations: 117.563 KiB)
versioninfo()
#Julia Version 0.7.0-DEV.4740
#Commit 049b9bc912* (2018-04-03 17:11 UTC)
2

Really ugly solution but I am in a hurry :slightly_smiling_face:

@generated function lt_tup(x::NTuple{N, Any}, y::NTuple{N, Any}) where {N}
	ex = Expr(:block)
	for i in 1:N
		push!(ex.args, :(x[$i] < y[$i] && return true))
		push!(ex.args, :(x[$i] > y[$i] && return false))
	end
	push!(ex.args, :(return false))
	return ex
end

julia> @btime sort(rr_hetero, lt = lt_tup)
  1.002 ms (11 allocations: 117.78 KiB)

julia> @btime sort(rr_homo)
  1.237 ms (5 allocations: 117.48 KiB)

julia> sort(rr_hetero, lt = lt_tup) == sort(rr_hetero)
true

Hopefully didn’t make some obvious bug…

2 Likes
3

Thanks a lot! That solved my problem.