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

Package Announcements
,
1

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.

fsort_missing_100m_int fsortperm_missing_100m_int

Benchmarking Code

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

using SortingLab

using BenchmarkTools, SortingAlgorithms

base_sort = @belapsed sort(x)
sortingalg_sort = @belapsed sort(x, alg=RadixSort)
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)
sortingalg_sortperm = @belapsed sortperm(x, alg=RadixSort)
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
2

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

7 Likes
3

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