# Dispatching by values is very slow - Feature or Problem?

**URL:** <https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586>\
**Category:** Performance\
**Tags:** dispatch\
**Created:** [July 31, 2021, 8:33am UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586 "2021-07-31T08:33:27Z")\
**Posts on this page:** 11\
**Page:** 2

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [July 31, 2021, 12:37pm UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586/21 "2021-07-31T12:37:23Z")

</div>

your argument is “but it’s pointless because it doesn’t sort Vector!”, and the counterargument is exactly: because there’s niche!

---

<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 31, 2021, 12:42pm UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586/22 "2021-07-31T12:42:15Z")

</div>

> [@jling](#):
>
> your argument is “but it’s pointless because it doesn’t sort Vector!”, and the argument is exactly: because there’s niche!

I am not sure where you see a disagreement here. Do we agree that not using dispatching by value makes it much faster in this case? Therefore either we do not allow Base Vector if you want to dispatch by value because of the performance hit, or we do allow them to gain performance and you do not dispatch by value.

I don’t see the sense of allowing something if you know it is slower than Base. That’s my opinion though.

Let me nonetheless thank you @jling again for your comments they were very helpful.

---

<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 31, 2021, 12:42pm UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586/23 "2021-07-31T12:42:15Z")

</div>

I think you’re talking past each other.

Yes, sorting small vectors is something some fields require. That doesn’t mean that the default implementation for Vectors should be able to handle that case perfectly (I happen to think it should too, but there are other problems that are more time consuming than sorting such short vectors, e.g. creating that vector in the first place). That’s why the usual recommendation for such small vectors is “use `StaticArrays`”, because the core language can’t iterate on implementation details as fast as a package can. I’ve [opened a PR](https://github.com/JeffreySarnoff/SortingNetworks.jl/pull/11) to allow `SortingNetworks.jl` to work with `StaticArrays.jl` and I’ve checked the compiled code - just passing in an `SVector` (e.g. `swapsort(rand(SVector{4,Float64}))`) inlines all branches, gets rid of all length checking etc. and _is just as fast as using a Tuple_. I can’t compare with your `sortn!` because I don’t have the fastest memory, i.e. I’m IO bound anyway and the fastest timing I can achieve is 1.3µs (which is the same for _all_ variants of that size! `sort!`, `sortn!`, `swapsort` etc).

I’d encourage you to check out that PR and see with your machine whether `swapsort` on an `SVector` is faster than your branching version or not.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [July 31, 2021, 2:53pm UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586/24 "2021-07-31T14:53:49Z")

</div>

Here is a benchmark that supports the claim that sorting networks are faster for tuples:

```julia
n = 4
@benchmark sort!(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 96 ns
@benchmark sortn!(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 97 ns
@benchmark sort(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 145 ns
@benchmark swapsort(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 212 ns
@benchmark swapsort(x) setup=(x=Tuple(rand(n))) evals=1 samples=100000 #median = 69 ns

```

full code:

```julia
using SortingNetworks, BenchmarkTools, Statistics

function sortn!(x::Vector)
    n = length(x)
    n == 2 && return sort2!(x)
    n == 3 && return sort3!(x)
    n == 4 && return sort4!(x)
end

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

@benchmark sort!(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 96 ns
@benchmark sortn!(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 97 ns
@benchmark sort(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 145 ns
@benchmark swapsort(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 212 ns
@benchmark swapsort(x) setup=(x=Tuple(rand(n))) evals=1 samples=100000 #median = 69 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 31, 2021, 3:00pm UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586/25 "2021-07-31T15:00:02Z")

</div>

Thank you for those benchmarks! Seems like I really do have to upgrade my machine 😅

Now if only the PR to `SortingNetworks.jl` for allowing any `AbstractVector` to be passed in would be merged 🙂 Until then, would you mind cloning the branch in question from my fork (found [here](https://github.com/Seelengrab/SortingNetworks.jl/tree/static_arrays_support)), `dev`ing it into an environment and checking the speed when putting in `StaticArrays`? I’d expect the speed to be the same as for tuples, since that’s what `StaticArrays` is using internally.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [July 31, 2021, 3:21pm UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586/26 "2021-07-31T15:21:41Z")

</div>

Perhaps the compiler was already able to figure this out?

```julia
#add/free SortingNetworks
@benchmark sort!(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 96 ns
@benchmark sortn!(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 83 ns
@benchmark sort(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 140 ns
@benchmark swapsort(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 212 ns
@benchmark swapsort(x) setup=(x=Tuple(rand(n))) evals=1 samples=100000 #median = 88 ns
@benchmark swapsort(x) setup=(x=StaticArray(rand(n))) evals=1 samples=100000) #median = 73 ns

#dev https://github.com/Seelengrab/SortingNetworks.jl.git
@benchmark sort!(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 96 ns
@benchmark sortn!(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 87 ns
@benchmark sort(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 143 ns
@benchmark swapsort(x) setup=(x=rand(n)) evals=1 samples=100000 #median = 206 ns
@benchmark swapsort(x) setup=(x=Tuple(rand(n))) evals=1 samples=100000 #median = 69 ns
@benchmark swapsort(x) setup=(x=StaticArray(rand(n))) evals=1 samples=100000) #median = 68 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 31, 2021, 3:25pm UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586/27 "2021-07-31T15:25:41Z")

</div>

No, there’s just a fallback method:

```julia
julia> using StaticArrays, SortingNetworks                                           
                                                                                     
julia> swapsort(rand(SVector{4,Float64}))                                            
([0.30452790929831275, 0.17044971202350268, 0.5731354773789699, 0.7998330355999902],)
                                                                                     
julia> swapsort(rand(SVector{4,Float64})) |> typeof                                  
Tuple{SVector{4, Float64}}                                                           

```

The returned object should be a tuple of numbers, but this is a tuple of a single array (which isn’t sorted at all). Compare with the output of a tuple:

```julia
julia> swapsort(Tuple(rand(4)))                                                  
(0.31303063934598596, 0.8332144225773782, 0.8612756394938614, 0.9229322452749227)
                                                                                 
julia> swapsort(Tuple(rand(4))) |> typeof                                        
NTuple{4, Float64}                                                               

```

The reason it couldn’t possibly have figured it out in the original code was because the methods in question were taking a `Vector{T}` argument, limiting the possible vectors to the true `Vector` type from Base. In the PR, I changed those signatures to take an `AbstractVector` instead, allowing anything that looks like a vector (like a `SVector` from `StaticArrays`) to be used.

* * *

When using the PR:

```julia
(jl_sJq4si) pkg> st                                                                              
      Status `/tmp/jl_sJq4si/Project.toml`                                                       
  [07e3d4f1] SortingNetworks v0.3.1 `../../d/Documents/Projects/juliaProjects/SortingNetworks.jl`
  [90137ffa] StaticArrays v1.2.9                                                                 
                                                                                                 
julia> using StaticArrays, SortingNetworks                                                       
                                                                                                 
julia> swapsort(rand(SVector{4,Float64}))                                                        
(0.14290259334067623, 0.6245153918717478, 0.6504626079016613, 0.8373470603702046)                
                                                                                                 
julia> swapsort(rand(SVector{4,Float64})) |> typeof                                              
NTuple{4, Float64}                                                                               

```

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [August 2, 2021, 2:45pm UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586/28 "2021-08-02T14:45:19Z")

</div>

Wow! You’re quite right. I had assumed the result would end up sorted. In ordinary code I imagine I’d get a type error from the output.

---

<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:** [August 2, 2021, 2:58pm UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586/29 "2021-08-02T14:58:33Z")

</div>

Well, if it weren’t for that fallback method, you’d have gotten a `MethodError` 🙂 I’m not sure why this fallback exists in the first place 🤷‍♂️

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [August 2, 2021, 3:00pm UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586/30 "2021-08-02T15:00:41Z")

</div>

To support splatting: `swapsort(6, 4) == (4, 6)`.

---

<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:** [August 2, 2021, 3:13pm UTC](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586/31 "2021-08-02T15:13:05Z")

</div>

Well, it’s not technically necessary for splatting to work. I also wouldn’t expect splatting of a single element into `swapsort` to work, there’s nothing to swap after all. It’s also not like the single argument function is some sort of recursion base case.

In any case, it’s been cleared up now 🙂

[Previous page](https://discourse.julialang.org/t/dispatching-by-values-is-very-slow-feature-or-problem/65586.md?page=1)