# Squeeze out the last 10% of performance for a sorting function?

**URL:** <https://discourse.julialang.org/t/squeeze-out-the-last-10-of-performance-for-a-sorting-function/64539>\
**Category:** Performance\
**Tags:** sort\
**Created:** [July 12, 2021, 10:19pm UTC](https://discourse.julialang.org/t/squeeze-out-the-last-10-of-performance-for-a-sorting-function/64539 "2021-07-12T22:19:31Z")\
**Posts on this page:** 7\
**Page:** 2

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 13, 2021, 1:30pm UTC](https://discourse.julialang.org/t/squeeze-out-the-last-10-of-performance-for-a-sorting-function/64539/21 "2021-07-13T13:30:39Z")

</div>

Here, I get:

```julia
% gcc -Ofast -march=native insertion.c -o insertion
% ./insertion 
84019 39439 78310 79845 91165 19756 33523 76823 27778 55397  
Execution time: 1.028668

% julia --math-mode=fast --check-bounds=no insertion.jl 
  977.059 ms (0 allocations: 0 bytes)

% julia --math-mode=fast insertion.jl 
  1.011 s (0 allocations: 0 bytes)

% julia --check-bounds=no insertion.jl 
  983.802 ms (0 allocations: 0 bytes)

% julia insertion.jl 
  1.255 s (0 allocations: 0 bytes)

```

I don’t understand why `--check-bounds=no` makes such a difference, given that I am using `@inbounds`:

```julia
function insertion_sort!(x)
    @inbounds for i = 2:length(x)
        c = x[i]
        j = i
        while j > 1 && c < x[j-1] 
            x[j] = x[j-1]
            j -= 1
        end
        x[j] = c
    end
end
m = 10^5
using BenchmarkTools
@btime insertion_sort!(y) setup = (y = rand(1:m,m));

```

---

<div class="post-metadata">

**Author:** ![Seif\_Shebl](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)\
**Post date:** [July 13, 2021, 5:28pm UTC](https://discourse.julialang.org/t/squeeze-out-the-last-10-of-performance-for-a-sorting-function/64539/22 "2021-07-13T17:28:19Z")

</div>

I’m surprized you find any differences at all. On my computer, all combinations have the same performance. BTW, in recent versions of Julia `--math-mode=fast` has no effect, it’s overriden by the `@fastmath` macro. On the other hand, `--check-bounds=no` sets `@inbounds` globally everywhere.  
My results on Windows 10 and WSL2:

```julia
Windows 10
  # 1.095 s (0 allocations: 0 bytes) : @inbounds, "--check-bounds=no"
  # 1.096 s (0 allocations: 0 bytes) : "--check-bounds=no"
  # 1.094 s (0 allocations: 0 bytes) : @inbounds
  # 1.093 s (0 allocations: 0 bytes) : @inbounds @fastmath
  # 1.093 s (0 allocations: 0 bytes) : "--check-bounds=no --math-mode=fast"
WSL2
  # 1.094 s (0 allocations: 0 bytes) : @inbounds, "--check-bounds=no"
  # 1.094 s (0 allocations: 0 bytes) : "--check-bounds=no"
  # 1.095 s (0 allocations: 0 bytes) : @inbounds
  # 1.096 s (0 allocations: 0 bytes) : @inbounds @fastmath
  # 1.093 s (0 allocations: 0 bytes) : "--check-bounds=no --math-mode=fast"

```

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [July 13, 2021, 5:38pm UTC](https://discourse.julialang.org/t/squeeze-out-the-last-10-of-performance-for-a-sorting-function/64539/23 "2021-07-13T17:38:04Z")

</div>

Whether you use `@inbounds` or `--check-bounds=no` really shouldn’t make a difference. (Can confirm it locally, similar to what @Seif_Shebl posted.)

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 13, 2021, 5:49pm UTC](https://discourse.julialang.org/t/squeeze-out-the-last-10-of-performance-for-a-sorting-function/64539/24 "2021-07-13T17:49:17Z")

</div>

Yes, that is strange. But here it does (Linux Mint 20.2 on a Samsung i7):

```julia
% julia insertion.jl 
  1.254 s (0 allocations: 0 bytes)

% julia --check-bounds=no insertion.jl 
  1.004 s (0 allocations: 0 bytes)

% julia insertion.jl 
  1.266 s (0 allocations: 0 bytes)

% julia --check-bounds=no insertion.jl 
  975.647 ms (0 allocations: 0 bytes)

% more insertion.jl 
function insertion_sort!(x)
    @inbounds for i = 2:length(x)
        c = x[i]
        j = i
        while j > 1 && c < x[j-1] 
            x[j] = x[j-1]
            j -= 1
        end
        x[j] = c
    end
end
m = 10^5
using BenchmarkTools
@btime insertion_sort!(y) setup = (y = rand(1:m,m));

% julia --version
julia version 1.6.1

```

---

<div class="post-metadata">

**Author:** ![apo383](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/apo383/32/11272_2.png) [@apo383](https://discourse.julialang.org/u/apo383)\
**Post date:** [July 13, 2021, 7:18pm UTC](https://discourse.julialang.org/t/squeeze-out-the-last-10-of-performance-for-a-sorting-function/64539/25 "2021-07-13T19:18:56Z")

</div>

This is kind of a naive question, but could this have anything to do with the type of integer for `i` and `j`? I believe Julia `Int` is defined by machine, e.g.

```julia
julia> typeof(1)
Int64

```

whereas gcc might default to 32-bit `int`?

These are kind of trivial operations with `i` and `j`, but everything is trivial here, so maybe it matters? I am at least a couple decades out of date, but it used to be that `Int32` was faster for many operations. No idea about modern architectures and compilers though. It might even go the other way?

---

<div class="post-metadata">

**Author:** ![Seif\_Shebl](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)\
**Post date:** [July 14, 2021, 12:28am UTC](https://discourse.julialang.org/t/squeeze-out-the-last-10-of-performance-for-a-sorting-function/64539/26 "2021-07-14T00:28:01Z")

</div>

For C and Flang, it makes no difference if I use `int64` for all `int`s, but gfortran is now the same as Julia and Julia now beats Nim. So now, only the C compiler and Fortran’s LLVM Flang beat Julia.

Times using `int64` in all languages.

```julia
Nim : Execution time: 1.255711317062378
gfortran : Time: 1.09300
Julia : 1.09400 s (0 allocations: 0 bytes)
Flang : Time: 1.02821
C : Execution time: 0.984375

```

---

<div class="post-metadata">

**Author:** ![Seif\_Shebl](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)\
**Post date:** [July 18, 2021, 11:55pm UTC](https://discourse.julialang.org/t/squeeze-out-the-last-10-of-performance-for-a-sorting-function/64539/27 "2021-07-18T23:55:42Z")

</div>

Well, defining `x` as an `MVector` eliminated that gap to C and Fortran completely. I was hesitant to try `StaticArrays` at first because the vector length is big, but was surprised that encoding the vector length besides the element type as the `MVector` does made all the difference. Thank you all for the valuable feedback in this thread.

```julia
using StaticArrays

function insertion_sort!(x)
    for i = 2:length(x)
        c = x[i]
        j = i
        while j > 1 && c < x[j-1] 
            x[j] = x[j-1]
            j -= 1
        end
        x[j] = c
    end
end

m = 10^5
x = MVector{m,Int}(undef)
@btime insertion_sort!(y) setup = (y = rand!(x,1:m)) 
  1.028 s (0 allocations: 0 bytes)

```

[Previous page](https://discourse.julialang.org/t/squeeze-out-the-last-10-of-performance-for-a-sorting-function/64539.md?page=1)