quicksort_benchmarks.jl

# 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