# [ANN]: SortingLab.jl 0.2.2 - 5x faster Sort and Sort Perm for `Vector{Union{Missing, T}}`

Do you want 5x faster `sort` and `sortperm` for `Vector{Union{T, Missing}}`?

You can with SortingLab.jl!

Simply use `SortingLab.jl`'s `fsort` and `fsortperm` to enjoy the benefits.

Benchmarks
Please note that SortingAlgorithms.jl’s radixsort does not support `Union{Missing, T}` and hence the values are shown as 0.

Benchmarking Code

``````x = rand(1:1_000_000, 100_000_000)

using SortingLab

using BenchmarkTools, SortingAlgorithms

base_sort = @belapsed sort(x)
sortinglab_fsort = @belapsed fsort(x)

using Missings: allowmissing
x_w_missing = allowmissing(x)
x_w_missing[rand(1:length(x), 10_000_000)] .= missing

base_sort_wm = @belapsed sort(x_w_missing)
sortingalg_sort_wm = 0
sortingalg_sort_wm = @belapsed sort(x_w_missing, alg=RadixSort) # fails
sortinglab_fsort_wm = @belapsed fsort(x_w_missing)

using StatsPlots

g = groupedbar(
repeat([" Base\n sort(x)", "SortingAlgorithms.jl\n sort(x, alg=RadixSort)", "  SortingLab.jl\n fsort(x)"], outer=2),
[base_sort, sortingalg_sort, sortinglab_fsort,
base_sort_wm, sortingalg_sort_wm, sortinglab_fsort_wm];
group = repeat(["w/o missing", "with missing"], inner=3)
)

title!(g, "Sort 100m integer")

savefig(g, "benchmarks/fsort_missing_100m_int.png")

#######################
# sortperm
#######################

base_sortperm = @belapsed sortperm(x)
sortinglab_fsortperm = @belapsed fsortperm(x)

base_sortperm_wm = @belapsed sortperm(x_w_missing)
sortingalg_sortperm_wm = 0
sortingalg_sortperm_wm = @belapsed sortperm(x_w_missing, alg=RadixSort) # fails
sortinglab_fsortperm_wm = @belapsed fsortperm(x_w_missing)

using StatsPlots

g2 = groupedbar(
repeat([" Base\n sortperm(x)", "SortingAlgorithms.jl\n sortperm(x, alg=RadixSort)", "  SortingLab.jl\n fsortperm(x)"], outer=2),
[base_sortperm, sortingalg_sortperm, sortinglab_fsortperm,
base_sortperm_wm, sortingalg_sortperm_wm, sortinglab_fsortperm_wm];
group = repeat(["w/o missing", "with missing"], inner=3)
)

title!(g2, "SortPerm 100m integer")

savefig(g2, "benchmarks/fsortperm_missing_100m_int.png")
``````
18 Likes

Cool! Any reason we can’t use this to just speed up Base sort/sortperm? What’s the catch?

7 Likes

This is an interesting one. Had a brief discussion with @StefanKarpinski at Juliacon 2019 that is related to this.

Taking a step back first, we know that radix sort is faster for most binary types, but radix sort needs double the amount of RAM. After weighing the pros and cons we can decide to implement radix sort in base. If that happens, then supporting missing is as simple as mapping `missing` to `typemax(T)` where `T` is the non missing type being sorted and add one more pass to handle the edge case where `typemax(T)` also appears in vector being sorted. This works because the radix sort algorithm maps the inputs to `UInt*` while preserving order. And in sorting, missing just comes out last.

The above solution is quite fast for `sort` as shown in my benchmarks.

I am not sure why the base sort is slower when there are missing, but one way I got around that was to not sort the missings at all and instead just count them and then `skipmissing` on the original data and sort that. Once sorted, put all the missings at the end. This is just taking ideas from counting sort.

sortperm

The sort perm case is trickier. I found the fastest way is to implement a `sortandperm` function that sorts the original array and at the same time rearrange the order index. This is the finding of @nalimilan as well. I recall trying to make a PR after digging into the base code but the arguments I made were quite convoluted. I think partly because the base sorting infrastructure is fairly complicated (for me).

1 Like