# Sorting a vector of fixed size

**URL:** <https://discourse.julialang.org/t/sorting-a-vector-of-fixed-size/71766>\
**Category:** Performance\
**Tags:** sort, staticarrays\
**Created:** [November 19, 2021, 9:37am UTC](https://discourse.julialang.org/t/sorting-a-vector-of-fixed-size/71766 "2021-11-19T09:37:25Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![AdamR](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adamr/32/5109_2.png) [@AdamR](https://discourse.julialang.org/u/AdamR)\
**Post date:** [November 19, 2021, 9:37am UTC](https://discourse.julialang.org/t/sorting-a-vector-of-fixed-size/71766/1 "2021-11-19T09:37:25Z")

</div>

I need to solve a combinatorics problem, that requires, among others, finding and sortperm (a.k.a. argsort) for thousands of millions of vectors of fixed size.

It so happens that the size of the vector is known at the compile time in my setup.  
Since the size of the vectors is expected to be small (single digit), I expect a significant speedup when compiler is given the size of the vectors, because it theoretically can unroll the sort into a hierarchy of “if” statements.

Is this kind of optimization achievable in Julia? If so, how?

Edit: in C++ one can approach the problem like this: [c++ - Very fast sorting of fixed length arrays using comparator networks - Stack Overflow](https://stackoverflow.com/q/19790522/1261153)

---

<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:** [November 19, 2021, 9:59am UTC](https://discourse.julialang.org/t/sorting-a-vector-of-fixed-size/71766/2 "2021-11-19T09:59:30Z")

</div>

One approach is to use `SVector`s from StaticArrays.jl:

```julia
1.7.0-rc1> using BenchmarkTools, StaticArrays

1.7.0-rc1> @benchmark sort(v) setup=(v=rand(8)) # ordinary vectors
BenchmarkTools.Trial: 10000 samples with 988 evaluations.
 Range (min … max): 47.773 ns … 675.911 ns ┊ GC (min … max): 0.00% … 90.25%
 Time (median): 55.466 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 59.278 ns ± 22.770 ns ┊ GC (mean ± σ): 1.54% ± 4.36%

   ▃▅▆▇██▇▆▃▁ ▂
  ▇██████████▇▆▅▆▇▆▅▆▄▆▅▅▂▃▅▃▅▆▆█▇▇▇▆▅▆▆▆▅▆▅▆▆▇▇▇██▇▇▅▆▆▅▆▆▅▅▅ █
  47.8 ns Histogram: log(frequency) by time 125 ns <

 Memory estimate: 128 bytes, allocs estimate: 1.

1.7.0-rc1> @benchmark sort(v) setup=(v=@SVector rand(8)) # static vectors
BenchmarkTools.Trial: 10000 samples with 996 evaluations.
 Range (min … max): 21.586 ns … 256.124 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 23.293 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 24.495 ns ± 6.133 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

  ▇▃▇█▂▁▂▁▁▂▂▁▁▄▁▂ ▂
  ████████████████▄▅▅▅▅▅▅▅▅▆▆▅▄▅▆▆▆▅▇▆▆▆▆▇▆▆▆▅▆▅▆▅▆▆▅▅▄▃▃▅▄▄▁▅ █
  21.6 ns Histogram: log(frequency) by time 55.2 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

```

It’s pretty fast, but the speedup is less than what you will see from other operations, probably.

`SVector`s are statically sized as well as immutable, if you absolutely _have_ to mutate the vectors, there are also `MVector`, but in most cases immutability is not a problem.

---

<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:** [November 19, 2021, 10:03am UTC](https://discourse.julialang.org/t/sorting-a-vector-of-fixed-size/71766/3 "2021-11-19T10:03:16Z")

</div>

( **Edit:** The below benchmarks are not quite reliable, since it probably measures sorting vectors that are already sorted during the benchmark. I’m not sure how to benchmark in-place sorting of short vectors, since using `evals=1` does not work quite well either. Benchmarking of `sort` (not `sort!`) is probably more reliable.)

Hmm, I tried `MVector` as well as sorting in-place:

```julia
1.7.0-rc1> @benchmark sort!(v) setup=(v=@MVector rand(8))
BenchmarkTools.Trial: 10000 samples with 996 evaluations.
 Range (min … max): 18.273 ns … 89.157 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 18.976 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 19.758 ns ± 3.703 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

  ▃█▇▆▃▃▁▂ ▁ ▂ ▂ ▂
  ██████████▇████▄█▇█▇███▇▄▅▄▄▃▄▁▁▁▃▄▄▃▁▄▁▁▃▁▁▄▄▆▅▅▅▄▄▅▅▅▄▄▅▄ █
  18.3 ns Histogram: log(frequency) by time 37 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

1.7.0-rc1> @benchmark sort!(v) setup=(v=rand(8))
BenchmarkTools.Trial: 10000 samples with 996 evaluations.
 Range (min … max): 19.679 ns … 130.924 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 21.084 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 22.022 ns ± 5.150 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

  ▄▇█▆▄▂▁▃▁▁ ▂▃ ▂
  ███████████▇███▇▅▄▅▅▅▄▄▁▃▁▁▁▁▅▇▇▇▅▅▅▅▅▅▅▅▆▆▇▅▆▆▆▆▅▄▄▅▄▄▃▃▅▄▄ █
  19.7 ns Histogram: log(frequency) by time 49.1 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

```

Sorting in-place with `sort!` is actually faster than `sort`ing `SVector`s, which surprises me a bit. Keep in mind, though, that `SVector`s have many other performance benefits that you should consider.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [November 19, 2021, 10:08am UTC](https://discourse.julialang.org/t/sorting-a-vector-of-fixed-size/71766/4 "2021-11-19T10:08:55Z")

</div>

You could try to use [https://github.com/JeffreySarnoff/SortingNetworks.jl](https://github.com/JeffreySarnoff/SortingNetworks.jl) or [https://github.com/nlw0/ChipSort.jl](https://github.com/nlw0/ChipSort.jl)

---

<div class="post-metadata">

**Author:** ![AdamR](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adamr/32/5109_2.png) [@AdamR](https://discourse.julialang.org/u/AdamR)\
**Post date:** [November 19, 2021, 10:15am UTC](https://discourse.julialang.org/t/sorting-a-vector-of-fixed-size/71766/5 "2021-11-19T10:15:03Z")

</div>

These are great libraries, but none provides a sortperm/argsort, just sort.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [November 19, 2021, 10:25am UTC](https://discourse.julialang.org/t/sorting-a-vector-of-fixed-size/71766/6 "2021-11-19T10:25:17Z")

</div>

There is also [https://github.com/xiaodaigh/SortingLab.jl](https://github.com/xiaodaigh/SortingLab.jl), although they don’t seem to use sorting networks…