Skip to content

Instantly share code, notes, and snippets.

@LilithHafner
Last active July 19, 2022 17:01
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save LilithHafner/56fa5b3e4ed984bcd5af086adbcb98b8 to your computer and use it in GitHub Desktop.
# Instructions:
# Run before() on an old version, then run after() on a new version
# Command line on my computer:
# cd ~/.julia && julia-1.9 -e 'import Pkg; Pkg.activate("environments/plots"); include("dev/quicksort_benchmarks.jl"); before()' && dev/julia/julia -e 'import Pkg; Pkg.activate("environments/plots"); include("dev/quicksort_benchmarks.jl"); after(); println("Press enter to exit"); readline(stdin)' && echo "Done"
using Printf, GLMakie, DataFrames, BenchmarkTools, Serialization, Random
function time_sorting(m=5*10^5, Alg=QuickSort)
data = DataFrame(length=Int[], var"1:n"=Float64[], Int=Float64[], Float64=Float64[],
Vector=Float64[], Int32=Float64[], var"3-Tuple"=Float64[], Sorted=Float64[],
Reverse=Float64[], By=Float64[], var"All same"=Float64[], var"Few unique (4)"=Float64[],
var"partial 10"=Float64[], var"partial 100:200"=Float64[],
var"partial end-1000:end"=Float64[], var"nonconsecutive memory"=Float64[],
var"sortslices dims=1"=Float64[], var"sortslices dims=2"=Float64[],
var"vcat(1:n, -n:0)"=Float64[], var"strings"=Float64[],)
println(Alg)
println(join(names(data), "\t"))
for n in [10, 30, 100, 300, 1000, 3000, 10000, 30000, 100000]
Alg===InsertionSort && n > 1000 && break
t = zeros(length(names(data)))
samples = round(Int, m ÷ n)
t[2] = @belapsed sort!(x, alg=$Alg) setup=(x=rand(1:$n, $n)) evals=1 samples=samples
t[3] = @belapsed sort!(x, alg=$Alg) setup=(x=rand(Int, $n)) evals=1 samples=samples
t[4] = @belapsed sort!(x, alg=$Alg) setup=(x=rand(Float64, $n)) evals=1 samples=samples
t[5] = @belapsed sort!(x, alg=$Alg) setup=(x=[rand(1:10, 10) for _ in 1:$n]) evals=1 samples=samples
t[6] = @belapsed sort!(x, alg=$Alg) setup=(x=rand(Int32, $n)) evals=1 samples=samples
t[7] = @belapsed sort!(x, alg=$Alg, by=last) setup=(x=[ntuple(_ -> rand(Int64), 3) for _ in 1:$n]) evals=1 samples=samples
t[8] = @belapsed sort!(x, alg=$Alg) setup=(x=sort!(rand($n))) evals=1 samples=samples
t[9] = @belapsed sort!(x, alg=$Alg) setup=(x=sort!(rand($n), rev=true)) evals=1 samples=samples
t[10] = @belapsed sort!(x, alg=$Alg, by=x->round(Integer, x)) setup=(x=rand($n).*1000) evals=1 samples=samples
t[11] = @belapsed sort!(x, alg=$Alg) setup=(x=zeros($n)) evals=1 samples=samples
t[12] = @belapsed sort!(x, alg=$Alg) setup=(x=rand(rand(4), $n)) evals=1 samples=samples
if Alg == QuickSort
t[13] = @belapsed partialsort!(x, min($n, 10)) setup=(x=rand(Int, $n)) evals=1 samples=samples
t[14] = n < 200 ? NaN : @belapsed partialsort!(x, 100:200) setup=(x=rand(Int, $n)) evals=1 samples=samples
t[15] = @belapsed partialsort!(x, max(1, $n-1000):$n) setup=(x=rand(Int, $n)) evals=1 samples=samples
else
t[13:15] .= NaN
end
t[16] = @belapsed sort!(@view(x[begin:3:end]), alg=$Alg) setup=(x=rand(Int, $(3n))) evals=1 samples=samples
t[17] = @belapsed sortslices(x, alg=$Alg, dims=1) setup=(x=rand(Int, $n, 10)) evals=1 samples=samples
t[18] = @belapsed sortslices(x, alg=$Alg, dims=2) setup=(x=rand(Int, 10, $n)) evals=1 samples=samples
t[19] = @belapsed sort!(x, alg=$Alg) setup=(x=vcat(1:$n÷2, -$n÷2:1)) evals=1 samples=samples
t[20] = @belapsed sort!(x, alg=$Alg) setup=(x=[randstring(4) for _ in 1:$n]) evals=1 samples=samples
t .*= 1e9/n
t[1] = n
println(join(vcat([n], [@sprintf("%.2f", i) for i in t[2:end]]), "\t"))
push!(data, t)
end
data
end
# Makie
function plot_sorting_times(data; kw...)
f = Figure()
f[1,1:5] = Label(f, "Runtime in ns per element Vs. collection size", textsize=30)
plots = [Axis(f[(i-1) ÷ 5 + 2, (i-1) % 5 + 1]; title=name, xscale=log10)
for (i, name) in enumerate(names(data)[2:end])]
for (plt, y) in zip(plots, eachcol(data)[2:end])
ylims!(plt, (0,max(100, last(y)*1.1)))
end
colsize!(f.layout, 1, Relative(1))
plot_sorting_times((f, plots), data; kw...)
end
function plot_sorting_times(fplots, data; kw...)
x = data.length
for (plt, y) in zip(fplots[2], eachcol(data)[2:end])
lines!(plt, x, y; kw...)
end
fplots
end
function display_sorting_times(fplots)
f, plots = fplots
Legend(f[5,5], first(plots))
for i in 1:5
colsize!(f.layout, i, Relative(1/5))
end
display(f)
end
function before(m=5*10^5)
global old_quick = time_sorting(m, QuickSort)
global old_default = time_sorting(m, Base.DEFAULT_STABLE)
global insertion = time_sorting(m, InsertionSort)
global merge = time_sorting(m, MergeSort)
serialize("data", (old_quick, old_default, insertion, merge))
end
function after(m=5*10^5)
global old_quick, old_default, insertion, merge = deserialize("data")
global new_quick = time_sorting(m, QuickSort)
global new_default = time_sorting(m, Base.DEFAULT_STABLE)
plot_all()
nothing
end
function plot_all()
p = plot_sorting_times(new_quick, label="new QuickSort", linewidth=3, color="red")
plot_sorting_times(p, old_quick, label="old QuickSort", linewidth=3, color="black")
plot_sorting_times(p, new_default, label="new default", color="red")
plot_sorting_times(p, old_default, label="old default", color="black")
plot_sorting_times(p, merge, label="MergeSort", linestyle=:dot, color="blue")
plot_sorting_times(p, insertion, label="InsertionSort", linestyle=:dot, color="orange")
display_sorting_times(p)
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment