Benchmarks

The benchmark results are generated by the GitHub Actions.

julia> versioninfo()Julia Version 1.10.8
Commit 4c16ff44be8 (2025-01-22 10:06 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 4 × AMD EPYC 7763 64-Core Processor
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, znver3)
Threads: 1 default, 0 interactive, 1 GC (on 4 virtual cores)
julia> Pkg.status()Status `~/work/SwapSort.jl/SwapSort.jl/docs/Project.toml`
  [6e4b80f9] BenchmarkTools v1.6.0
  [e30172f5] Documenter v1.8.1
  [682c06a0] JSON v0.21.4
  [9b90f1cd] PlotlyDocumenter v0.2.0
⌅ [ca7969ec] PlotlyLight v0.8.2
  [90137ffa] StaticArrays v1.9.13
  [518c31a9] SwapSort v1.2.0 `~/work/SwapSort.jl/SwapSort.jl`
  [36e64239] Unroll v0.1.0
  [9a3f8284] Random
Info Packages marked with ⌅ have new versions available but compatibility constraints restrict them from upgrading. To see why use `status --outdated`

Package loading

The precompilation is very slow since the package reads many json files and generate sorting methods based on them. The current bottleneck is JSON.parsefile. A specialized reading method could make great improvement on precompilation speed.

julia> @time include("../../src/SwapSort.jl") 14.236179 seconds (3.20 M allocations: 170.137 MiB, 0.81% gc time, 2.33% compilation time)
Main.SwapSort

Same type (type-stable)

When sorting variables of the same type, swapsort has longer compilation time but from .01x to .2x runtime depending on the sorting size.

We first generate 64 random variables:

a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,Ja,Fe,Ma,Ap,My,Ju,Jl,Au,Se,Oc,No,De = rand(64)

Then we sort $N$ of them, where $N=1,...,64$. To save the build time of the doc, this section only benchmarks $N=1,2,4,8,16,32,64$. 3 sorting routines are benchmarked:

SwapSort: use SwapSort.swapsort to sort variables. Returns a sorted Tuple.
StaticArrays: use StaticArrays.SVector to pack the variables and then sort the SVector. StaticArrays.jl has a built-in bitonic sort for the purpose. Returns a sorted SVector which has a field of sorted NTuple.
Base: pack the variables into a Vector and use Base.sort!. Returns a sorted Vector.

The full benchmark can run from this script. We use @elapsed to get the first-time sort which is mostly compilation time. Then we use BenchmarkTools.@belapsed to get the actual runtime.

Compilation

Runtime

Different types (type-unstable)

When sorting across different types, methods based on Tuple or Vararg suffer from type inference as different orders have different types. As a result, the compilation time can be a lot longer. In this benchmark, we consider up to 23 variables of different types, including

7 Number types: Int, Float, Irrational, Complex, Rational, BigInt, BigFloat
8 Collection types: Tuple, Set, Dict, Matrix, Vector, sizeof, Range, NamedTuple
8 Other types: CartesianIndex, Pair, Function, Symbol, Type, Module, Nothing, Char

Sorting across different types is not supported by StaticArrays.jl, so the benchmark only contains SwapSort and Base. We compare different types by sizeof.

using Random, SwapSort, PlotlyLight, BenchmarkTools, StaticArrays, PlotlyDocumenter
a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w = shuffle(
    [rand(Int), rand(), π, im, 1//2, BigInt(rand(Int128)), rand(BigFloat),
    (1,2), Set([1,2]), Dict(1=>2), rand(2,2), rand(Int, 10), randstring(), 1:10, (a=1,b=2),
    CartesianIndex(1,2), 1=>2, sin, :sin, typeof(sin), SwapSort, nothing, 'a'])