# Faster default Base.sort! for Julia

**URL:** <https://discourse.julialang.org/t/faster-default-base-sort-for-julia/65508>\
**Category:** Performance\
**Tags:** sort\
**Created:** [July 29, 2021, 5:37pm UTC](https://discourse.julialang.org/t/faster-default-base-sort-for-julia/65508 "2021-07-29T17:37:34Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![viraltux](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/viraltux/32/15236_2.png) [@viraltux](https://discourse.julialang.org/u/viraltux)\
**Post date:** [July 29, 2021, 5:37pm UTC](https://discourse.julialang.org/t/faster-default-base-sort-for-julia/65508/1 "2021-07-29T17:37:34Z")

</div>

There are functions like `factorial` where Julia uses a `factorial_lookup` function to directly return results from a table when the value is lower or equal to 20.

Playing around with sorting algorithms I built a simple one that takes into account the size of the vector to sort just like `factorial` takes into a account the value passed to calculate its factorial.

As it turns out the algorithm taking into account size is consistently faster than the default for Julia up to a size of five elements, hence my question, **why does not Julia uses the same strategy for `sort!` as for `factorial` considering how critical sorting algorithms are in computing?**

Below follows the code and some benchmarks:

```julia
function sort2!(x)
    swap(i,j) = x[j], x[i] = x[i], x[j]
    x[1]>x[2] && swap(1,2)
end

function sort3!(x)
    swap(i,j) = x[j], x[i] = x[i], x[j]
    if x[1]>x[2] sort2!(x) end
    if x[2]>x[3] swap(2,3); sort2!(x) end
end

function sort4!(x)
    swap(i,j) = x[j], x[i] = x[i], x[j]
    if x[1]>x[2] sort2!(x) end
    if x[2]>x[3] swap(2,3); sort2!(x) end
    if x[3]>x[4] swap(3,4); sort3!(x) end
end

function sort5!(x)
    swap(i,j) = x[j], x[i] = x[i], x[j]
    if x[1]>x[2] sort2!(x) end
    if x[2]>x[3] swap(2,3); sort2!(x) end
    if x[3]>x[4] swap(3,4); sort3!(x) end
    if x[4]>x[5] swap(4,5); sort4!(x) end
end

```

I am just using this algorithm to test the “factorial” idea, I haven’t done any theoretical work on it to guarantee it is sound, to make sure it works I compared its results multiple times with Base.sort!

Comparing benchmarks for vector of length 3 we have:

```julia
sort!: 117.439 ns ± 42.243 ns
sort3!: 103.014 ns ± 76.325 ns

```

Comparing benchmarks for vector of length 5 we have:

```julia
sort!: 135.428 ns ± 43.606 ns
sort5!: 128.527 ns ± 60.103 ns

```

Comparing benchmarks for vector of length 6 we have:

```julia
sort!: 148.199 ns ± 45.349 ns
sort6!: 151.984 ns ± 59.283 ns

```

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [July 29, 2021, 6:19pm UTC](https://discourse.julialang.org/t/faster-default-base-sort-for-julia/65508/2 "2021-07-29T18:19:29Z")

</div>

If I’m not mistaken, you’ve basically rediscovered [sorting networks](https://en.wikipedia.org/wiki/Sorting_network).

I guess the simple reason is that when sorting vectors of such short length, 17 nano seconds difference is basically a rounding error, especially with other noise going on in a real-life workload. It’s more important to do these kinds of optimizations with e.g. factorial or fibonacci implementations, because it vastly reduces the time common calls take. In contrast, most calls to `sort!` have much longer arguments so this would be optimizing the very rare case.

---

<div class="post-metadata">

**Author:** ![viraltux](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/viraltux/32/15236_2.png) [@viraltux](https://discourse.julialang.org/u/viraltux)\
**Post date:** [July 29, 2021, 8:43pm UTC](https://discourse.julialang.org/t/faster-default-base-sort-for-julia/65508/3 "2021-07-29T20:43:30Z")

</div>

> [@Sukera](#):
>
> If I’m not mistaken, you’ve basically rediscovered [sorting networks](https://en.wikipedia.org/wiki/Sorting_network).

Oh, wow, I didn’t know about this, very interesting. Thank you for sharing!

> [@Sukera](#):
>
> 17 nano seconds difference is basically a rounding error, especially with other noise going on in a real-life workload.

The difference is consistent, they’re faster, also I just read in the article you provided that sorting networks can be parallelized! In the article we can also read:

> An optimal network for size 11 was found in December 2019 by Jannis Harder

Why don’t we parallelize and use that one in Julia?

> [@Sukera](#):
>
> In contrast, most calls to `sort!` have much longer arguments so this would be optimizing the very rare case.

That depends on what field of science you’re working on, what is rare for some might be common for some others… also, we can always challenge other languages to see how fast they sort short vectors 😄

---

<div class="post-metadata">

**Author:** ![blackeneth](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/blackeneth/32/10353_2.png) [@blackeneth](https://discourse.julialang.org/u/blackeneth)\
**Post date:** [July 29, 2021, 9:15pm UTC](https://discourse.julialang.org/t/faster-default-base-sort-for-julia/65508/4 "2021-07-29T21:15:50Z")

</div>

That can be a nice micro optimization.

It looks like you’ve been bitten by the [sorting bug](https://bits.houmus.org/2020-01-28/this-goes-to-eleven-pt1). For more on sorting algorithms, see [this thread](https://discourse.julialang.org/t/why-does-base-only-have-merge-insertion-and-quick-sorting-algorithms/65210). I posted 4 links you might find of interest.

At the bottom of the referenced link, I post a couple of links to algorithms that use SIMD and multiple threads. That would be the ultimate sort right now for primitive types. The way to get such a sort incorporated into base would be to first release a package with it. After a while, once it’s been debugged, and lots of people are finding it useful, there is a chance it could be pulled into base.

Or … maybe it just stays in a package. Packages work great. Although it can be tedious to load two dozen packages and re-add them for Julia releases. I can’t say I know of a better alternative. Package compiler can help somewhat.

It also depends on the philosophy of Julia. I created a [post asking about that](https://discourse.julialang.org/t/julia-philosophical-direction/64905), but it didn’t get much traction. Do we want everything to be eventually SIMD and multithreaded? Or do people get annoyed when functions launch threads and prefer to have single threaded, unless they ask otherwise?

---

<div class="post-metadata">

**Author:** ![viraltux](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/viraltux/32/15236_2.png) [@viraltux](https://discourse.julialang.org/u/viraltux)\
**Post date:** [July 29, 2021, 9:46pm UTC](https://discourse.julialang.org/t/faster-default-base-sort-for-julia/65508/5 "2021-07-29T21:46:21Z")

</div>

> [@blackeneth](#):
>
> That can be a nice micro optimization.

Micro optimization would be _low-level optimizations that do not change the overall structure of the program_.

Sorting Networks _do_ change the structure of the program, sure we can then micro optimize them as well, but we’re not talking anything low level now, we are talking about adding a faster algorithm for short arrays than the Julia `sort!` function is using and dispatch those algorithms based on the size of the vector.