# Taking sorting & ordering seriously

**URL:** <https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975>\
**Category:** Internals & Design\
**Tags:** sort\
**Created:** [September 14, 2018, 7:26pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975 "2018-09-14T19:26:27Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![stabbles](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stabbles/32/946_2.png) [@stabbles](https://discourse.julialang.org/u/stabbles)\
**Post date:** [September 14, 2018, 7:26pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/1 "2018-09-14T19:26:27Z")

</div>

Hi all,

I’m happy to share this proof of concept about refactoring the sorting and ordering API in Julia:

## [**SortingSortingOut.jl**](https://github.com/haampie/SortingSortingOut.jl)

The basic ideas are:

1. To make `Ordering` objects more composable and reusable
2. To figure out a better way to dispatch on efficient sorting algorithms.

The following is one of the motivating examples where `sort!` does not dispatch on an efficient floating point sorting algorithm, because the signature is `sort!(::Vector{Product}, ...)` rather than `sort!(::Vector{Float64})`. In my package I try to dispatch on the inferred type that is being compared / sorted, which allows me to use the efficient floating point sorting algorithm 🙂.

## Results

| n | `sort!` | `sortsort!` | x faster |
| --- | --- | --- | --- |
| 10\_000 | 1.113 ms | 560.6 μs | 2.0x |
| 1\_000 | 66.00 μs | 11.66 μs | 5.7x |
| 100 | 2.021 μs | 615.6 ns | 3.3x |

## Benchmark

```julia
using SortingSortingOut, BenchmarkTools

struct Product
    price::Int
    weight::Float64
end

weight(p::Product) = p.weight

function sort_products(n = 100)
    products = [Product(rand(1:100), 100rand()) for i = 1 : n]

    fst = @benchmark sort!(ps, by = $weight) setup = (ps = copy($products))
    snd = @benchmark sortsort!(ps, $(By(weight))) setup = (ps = copy($products))

    fst, snd
end

```

I’m hoping people could give feedback on this idea 😃

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [September 14, 2018, 7:41pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/2 "2018-09-14T19:41:48Z")

</div>

Strongly approve. This stuff could really use some love. Improving the performance of `sortperm` would also be a great thing.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [September 14, 2018, 10:21pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/3 "2018-09-14T22:21:53Z")

</div>

Also happy to contribute my string sort algorithms [WIP: faster string sort - #74 by xiaodai](https://discourse.julialang.org/t/wip-faster-string-sort/7671/74)

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [September 14, 2018, 10:25pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/4 "2018-09-14T22:25:30Z")

</div>

Well, since you asked for feedback… I was really hoping for something more than 80% faster. 😉

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 15, 2018, 6:03am UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/5 "2018-09-15T06:03:40Z")

</div>

So, is it 80% faster, or 5x as fast?

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [September 15, 2018, 7:25am UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/6 "2018-09-15T07:25:54Z")

</div>

I wrote this a while back: [https://github.com/JeffreySarnoff/SortingNetworks.jl](https://github.com/JeffreySarnoff/SortingNetworks.jl)  
(use master for faster tuple handling)

---

<div class="post-metadata">

**Author:** ![andyferris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/andyferris/32/235_2.png) [@andyferris](https://discourse.julialang.org/u/andyferris)\
**Post date:** [September 15, 2018, 11:46am UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/7 "2018-09-15T11:46:40Z")

</div>

Very nice 🙂 I also agree that we could clean up this area a bit.

One thing I would to see is some way of indicating that a data source is already sorted appropriately, so that `findall`, `findfirst` and so-on will just use `searchsorted`, `searchsortedfirst`, etc. I think I’ve seen this rough idea mentioned before, somewhere. (This also came up in one of my side projects more recently, the `SortIndex` in [AcceleratedArrays.jl](https://github.com/andyferris/AcceleratedArrays.jl) does exactly this).

---

<div class="post-metadata">

**Author:** ![nalimilan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nalimilan/32/147_2.png) [@nalimilan](https://discourse.julialang.org/u/nalimilan)\
**Post date:** [September 15, 2018, 12:34pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/8 "2018-09-15T12:34:16Z")

</div>

> [@andyferris](#):
>
> One thing I would to see is some way of indicating that a data source is already sorted appropriately, so that `findall` , `findfirst` and so-on will just use `searchsorted` , `searchsortedfirst` , etc. I think I’ve seen this rough idea mentioned before, somewhere.

> <https://github.com/JuliaCollections/DataStructures.jl/pull/290>
>
> Since I needed a SortedVector type, here it is.
> 
> The hardest part was writing …the binary search.
> A simpler implementation would be to just to push the new element onto the end and then use \`sort!\`, but that seemed to be slightly slower in my not-extensive-nor-rigorous tests.

---

<div class="post-metadata">

**Author:** ![andyferris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/andyferris/32/235_2.png) [@andyferris](https://discourse.julialang.org/u/andyferris)\
**Post date:** [September 15, 2018, 1:28pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/9 "2018-09-15T13:28:30Z")

</div>

That was probably it 🙂

---

<div class="post-metadata">

**Author:** ![stabbles](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stabbles/32/946_2.png) [@stabbles](https://discourse.julialang.org/u/stabbles)\
**Post date:** [September 15, 2018, 5:07pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/10 "2018-09-15T17:07:46Z")

</div>

Thanks all!

> [@StefanKarpinski](#):
>
> Improving the performance of `sortperm` would also be a great thing.

One of the things that makes `sortperm` slower is that it guarantees stability (indices of repeated values appear in ascending order). If that requirement is dropped, the implementation would just be

```julia
sortperm(xs, ord) = sortsort!(Vector(OneTo(length(xs))), By(i -> @inbounds(xs[i]), ord))

```

and it could automatically dispatch to specialized sorting algorithms in my proof of concept code 🙂.

> [@xiaodai](#):
>
> Also happy to contribute my string sort algorithms [WIP: faster string sort](https://discourse.julialang.org/t/wip-faster-string-sort/7671/74)

That looks really nice! After reading the discussion [on Github](https://github.com/JuliaCollections/SortingAlgorithms.jl/pull/27), I’m sure you have some ideas about what `sort!` should really dispatch on.

> [@DNF](#):
>
> So, is it 80% faster, or 5x as fast?

> [@tbeason](#):
>
> Well, since you asked for feedback… I was really hoping for something more than 80% faster. 😉

This took me a bit too long 😛. Fortunately there are the absolute numbers as well ^^.

> [@JeffreySarnoff](#):
>
> I wrote this a while back: [https://github.com/JeffreySarnoff/SortingNetworks.jl](https://github.com/JeffreySarnoff/SortingNetworks.jl)  
> (use master for faster tuple handling)

So should this eventually dispatch on `sort(::NTuple)`?

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [September 15, 2018, 5:11pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/11 "2018-09-15T17:11:39Z")

</div>

> [@stabbles](#):
>
> One of the things that makes `sortperm` slower is that guarantees stability

I suspect that stability could be patched up after the fact for `sortperm`: do an unstable sort and then just scan through the indices and sort each equivalence class of indices (equivalent in the sense that `v[i] == v[j]`). Of course, in the worst case, that’s sorting the entire range of indices, but maybe in practice it would be ok. It seems like it should be possible to take advantage of the fact that we know the exact range of index values… seems like the perfect use case for a radix sort.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [September 15, 2018, 5:48pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/12 "2018-09-15T17:48:20Z")

</div>

Re sortperm performance / stability:

One could do it the same way as for normal sorts, i.e. it is only stable when the user requests it via the algorithm keyword.

For small bitstypes (or small results of By) and medium-sized arrays, it might make sense to sort! a temporary of `(idx::Int, compareT::T)` tuples, for better cache locality. I think this is what kills current sortperm performance.

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [September 15, 2018, 6:52pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/13 "2018-09-15T18:52:16Z")

</div>

SortingNetworks master (pending merge into METADATA) already does dispatch on either N args or NTuples where N is in 1:16. And as to `sort` _yes_, only for small N (1…16, which are provably optimal as exchange networks, already ready).

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [September 15, 2018, 10:15pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/14 "2018-09-15T22:15:07Z")

</div>

So after giving it a try, I am very underwhelmed by the cache-local variant. Or, more precisely, I am absolutely shocked at how fast `sortperm` is, even though it should basically have no spatial locality at all.

```julia
julia> function _sortperm(A)
       tmp = [(@inbounds A[i],i) for i=1:length(A)]
       sort!(tmp)
       [t[2] for t in tmp]
       end
julia> v=rand(Int,10^8); sort(v[1:1000]); sortperm(v[1:1000]); _sortperm(v[1:1000]); 
julia> begin
       @time sort(v)
       @time sortperm(v)
       @time _sortperm(v);
       end;
 13.288238 seconds (6 allocations: 762.940 MiB, 0.70% gc time)
 42.778155 seconds (7 allocations: 762.940 MiB, 0.15% gc time)
 23.058652 seconds (13 allocations: 2.980 GiB, 0.47% gc time)

```

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [September 15, 2018, 10:24pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/15 "2018-09-15T22:24:38Z")

</div>

> [@foobar\_lv2](#):
>
> One could do it the same way as for normal sorts, i.e. it is only stable when the user requests it via the algorithm keyword.

Sort is stable by default, which is the opposite.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [September 15, 2018, 11:51pm UTC](https://discourse.julialang.org/t/taking-sorting-ordering-seriously/14975/16 "2018-09-15T23:51:02Z")

</div>

> [@StefanKarpinski](#):
>
> Sort is stable by default, which is the opposite.

Thanks! Then some zip-sort-extract variant is probably worthwhile for small bitstypes (as long as the temporary fits into memory), seeing a 3x speedup:

```julia
julia> function _sortperm(A)
              tmp = [(@inbounds A[i],i) for i=1:length(A)]
              sort!(tmp; alg=QuickSort)
              [t[2] for t in tmp]
              end
_sortperm (generic function with 1 method)

julia> v=rand(Int,10^8); sort(v[1:1000]); sortperm(v[1:1000]); _sortperm(v[1:1000]);

julia> begin
       @time sort(v)
       @time sortperm(v)
       @time _sortperm(v);
       end;
 13.137279 seconds (6 allocations: 762.940 MiB, 0.32% gc time)
 42.627918 seconds (7 allocations: 762.940 MiB, 0.00% gc time)
 16.295594 seconds (11 allocations: 2.235 GiB, 1.01% gc time)

```

PS. ~100KB - 1MB of buffer to sort appears to be an OK cross-over for the copy to amortize.