(end - start).count();
duration += time_taken * 1e-06;
}
std::cout << "Average time taken by program is : " << std::fixed
<< duration/cnt << std::setprecision(3) << " ms" << std::endl;
}
```
---
### Author:  [@tbeason](https://discourse.julialang.org/u/tbeason)
#### Post date: [August 10, 2023, 12:42pm UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/3 "2023-08-10T12:42:37Z")
Dang, so Julia is only _exactly as fast as_ C++?
---
### Author:  [@DNF](https://discourse.julialang.org/u/DNF)
#### Post date: [August 10, 2023, 1:43pm UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/4 "2023-08-10T13:43:25Z")
> [@mariusd](#):
>
> So julia is about 25% faster than C++. How is this possible?
You found a flaw in the C++ code, so they’re now the same speed. But there’s no reason why Julia can’t be faster than C++ in some cases, there’s nothing impossible about that.
Well-written (especially non-allocating) Julia code should be roughly the same speed as C++, some times a bit slower, some times a bit faster.
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [August 10, 2023, 7:35pm UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/5 "2023-08-10T19:35:09Z")
I’m not sure this is equivalent even after the type fixes. The C++ `quicksort` takes in a vector of `int` and `int lo` and `int hi`, which is all signed 32-bit integers IIRC. The Julia `qsort!` however was benchmarked with `Vector{Int32}, Int, Int`, the latter two being 64-bit integers on 64-bit systems. I’m not sure how indexing with `Int64` versus `Int32` is handled in Julia vs C++ though.
The `int pivot = a[(lo + hi) / 2];` and `pivot = a[(lo+hi)>>>1]` lines looked different, and it doesn’t seem like the Julia compiler generates the same instructions for `(lo+hi)>>>1` as `div((lo+hi), 2)` given signed integers, so maybe the C++ compiler isn’t either, is it possible to check the instructions like `@code_llvm` or `@code_native` does in Julia?
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [August 10, 2023, 7:43pm UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/6 "2023-08-10T19:43:49Z")
[https://godbolt.org/](https://godbolt.org/) is the C++ equivalent (it also works for julia, but since `@code_native` exists, it’s not as useful there)
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [August 10, 2023, 8:00pm UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/7 "2023-08-10T20:00:01Z")
The output looks different, which is a problem because I’m the opposite of versed in lower level instructions. But it looks like the C++ integer division has an add step that Julia’s `div` has but `>>>` doesn’t. The algorithm is calling for a division by 2, and the benchmark is stated to compare algorithms not hand-optimized code, so maybe it’s fairer to change `_ >>> 1` to `div(_, 2)` in the Julia version.
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [August 10, 2023, 8:02pm UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/8 "2023-08-10T20:02:05Z")
oh the extra instruction is that for negative numbers you need to do something a little different for divide by 2.
---
### Author:  [@Sukera](https://discourse.julialang.org/u/Sukera)
#### Post date: [August 10, 2023, 8:09pm UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/9 "2023-08-10T20:09:42Z")
> [@Oscar\_Smith](#):
>
> [https://godbolt.org/](https://godbolt.org/) is the C++ equivalent (it also works for julia, but since `@code_native` exists, it’s not as useful there)
Only 1.7.3 and 1.8.5 - I tried to get it ready for 1.9+, but ran into an issue with the way they pass arguments to julia:
>
>
> I'm trying to add ASM syntax switching support (since \`code\_native\` also support…s that), but I'm having trouble getting this to run locally with \`make dev\`, since the \`--\` ends up pushed into the \`ARGS\` as the first argument, causing \`FileNotFound\`. I suspect something is going wrong in the TS invocation/argument builder, but even with no changes to the \`julia.defaults.properties\` file, basic local usage doesn't seem to work. What am I doing wrong?
---
### Author:  [@mariusd](https://discourse.julialang.org/u/mariusd)
#### Post date: [August 10, 2023, 11:58pm UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/10 "2023-08-10T23:58:38Z")
I have modified the code on both sides such that they are nearly identical. Julia code uses uint32 indexes and the C++ code to uses int32 indexes. Its 62 ms for Julia vs 65 ms for C++. In my point of view, the difference is minor and I do consider this result as a tie.
I have also tried Julia with int32 indexes and it’s sligthly slower (64ms). C++ with uint32 indexes is slower than int32 (70ms).
The `(lo+hi) >> 1` vs `(lo+hi)/2` do not matter as this instruction is executed less often in our code.
Julia code:
```julia
using BenchmarkTools
# quicksort version with tail recursion: https://stackoverflow.com/questions/19094283/quicksort-and-tail-recursive-optimization
function qsort!(a,lo,hi)
i, j = lo, hi
_1 = eltype(hi)(1)
@inbounds while i < hi
pivot = a[(lo+hi) >> 1]
while i <= j
while a[i] < pivot; i += _1; end
while a[j] > pivot; j -= _1; end
if i <= j
a[i], a[j] = a[j], a[i]
i, j = i+_1, j-_1
end
end
if lo < j; qsort!(a,lo,j); end
lo, j = i, hi
end
return a
end
const N::UInt32 = 1000000
@benchmark qsort!(a, UInt32(1), UInt32(N)) setup=(a = rand(Int32.(1:N), N))
# @benchmark qsort!(a, Int32(1), Int32(N)) setup=(a = rand(Int32.(1:N), N)) # this is for int32 indices
```
C++ code:
```julia
typedef int ind_type;
void quicksort(std::vector& a, ind_type lo, ind_type hi) {
ind_type i = lo;
ind_type j = hi;
while (i < hi) {
int pivot = a[(lo + hi) >> 1];
// Partition
while (i <= j) {
while (a[i] < pivot) {
i = i + 1;
}
while (a[j] > pivot) {
j = j - 1;
}
if (i <= j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
i = i + 1;
j = j - 1;
}
}
// Recursion for quicksort
if (lo < j) {
quicksort(a, lo, j);
}
lo = i;
j = hi;
}
}
int main() {
#..........................................
std::vector d(N+1); # one more element
#..........................................
quicksort(d, 1, N); # sort elements 1 to N; needed in case index type is uint32
#..........................................
}
```
The runtimes are as follows:
Julia:
```julia
BenchmarkTools.Trial: 70 samples with 1 evaluation.
Range (min … max): 59.434 ms … 65.182 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 61.876 ms ┊ GC (median): 0.00%
Time (mean ± σ): 62.056 ms ± 1.364 ms ┊ GC (mean ± σ): 0.00% ± 0.00%
▁▁▄▄ ▁▄ █ ▄█ ▄▁▁▁ ▄ ▁▁ ▁ ▁ ▁ ▄
▆▁▆▁▁▆▆▁▆▁▁████▁▁██▁█▆▁▆██▆▆████▁▆▁█▁▆▁▆▆▆██▁█▆▁▁█▆▆▁▁▁█▁█▆ ▁
59.4 ms Histogram: frequency by time 64.6 ms <
Memory estimate: 0 bytes, allocs estimate: 0.
```
C++
`Average time taken by program is : 65.399590 ms`
---
### Author:  [@Elrod](https://discourse.julialang.org/u/Elrod)
#### Post date: [August 11, 2023, 3:59am UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/11 "2023-08-11T03:59:08Z")
I’d also really recommend Cthulhu for your introspection needs.
It’s great to be able to switch between typed Julia IR, LLVM, and native code, and then descend into non-inlined functions.
It’s really nice when you want to look at functions where the action is hidden behind a function call or two, like `sum`
```julia
using Cthulhu
x = rand(127);
@code_native sum(x)
@descend_code_typed debuginfo = :none annotate_source =
false iswarn = true sum(x)
```
The `@turbo` macro also generally places the interesting code behind a ` __turbo__!`.
I don’t like the “new” `@descend`, so I use my own macro `@d` that’s equivalent to the above.
The important argument is `annotate_source = false`, you can ignore the rest.
It should show `mapreduce_impl` as the only option to descend into. Descend, and then hit `N` to view the native code of `sum`.
I’m not sure how to actually use `@descend` itself to see the code of interest…
---
### Author:  [@Elrod](https://discourse.julialang.org/u/Elrod)
#### Post date: [August 11, 2023, 4:05am UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/12 "2023-08-11T04:05:35Z")
> [@mariusd](#):
>
> I have a Windows10 machine and compiled c++ with VisualStudio2019 in release mode.
Is this using MSVC?
The only experience I have with it is looking at godbolt every now and then.
It’s generally considered to produce worse code than GCC or Clang.
Clang uses LLVM, and will thus likely give comparable results to Julia for similar code.
---
### Author:  [@StatisticalMouse](https://discourse.julialang.org/u/StatisticalMouse)
#### Post date: [August 12, 2023, 7:44am UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/13 "2023-08-12T07:44:37Z")
I’d argue that ”is Julia faster than C++ in a single-threaded Quicksort” is the wrong question.
The right question is “is Julia faster than C++ in sorting an array”.
You can see that I’m opening up multi-threaded execution and GPUs (if any).
---
### Author:  [@greatpet](https://discourse.julialang.org/u/greatpet)
#### Post date: [August 12, 2023, 9:27am UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/14 "2023-08-12T09:27:40Z")
> [@StatisticalMouse](#):
>
> You can see that I’m opening up multi-threaded execution and GPUs (if any).
Or single threaded SIMD… I found some active projects on Google and it looks like a rabbit hole to go down.
---
### Author:  [@Elrod](https://discourse.julialang.org/u/Elrod)
#### Post date: [August 12, 2023, 2:15pm UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/15 "2023-08-12T14:15:54Z")
Note that Julia’s default sort uses a radix sort for large suitable inputs, which is algorithmically better, and should thus win for large enough sizes.
For SIMD c++ sorts, there are:
>
>
> //github.com/google/highway/tree/master/hwy/contrib/sort
> **[GitHub - intel/x86-simd-sort: C++ header file library for high performance...](https://github.com/intel/x86-simd-sort)**
>
> C++ header file library for high performance SIMD based sorting algorithms for primitive datatypes - GitHub - intel/x86-simd-sort: C++ header file library for high performance SIMD based sorting al...
Some comparisons:
>
IIRC, some of vqsort’s small size performance issues have been fixed (vqsort is the first of the two links above).
Has anyone tried implementing a SIMD sort in Julia?
---
### Author:  [@xor0110](https://discourse.julialang.org/u/xor0110)
#### Post date: [August 15, 2023, 3:24pm UTC](https://discourse.julialang.org/t/why-is-julia-faster-than-c-for-quicksort/102669/16 "2023-08-15T15:24:58Z")
I did some work with SIMD sorting, check out my presentation at JuliaCon 2019. [https://www.youtube.com/watch?v=\_bvb8X4DT90&t=402s](https://www.youtube.com/watch?v=_bvb8X4DT90&t=402s)
Code on GitHub: [GitHub - nlw0/ChipSort.jl: Sorting deeds done down the chip](https://github.com/nlw0/ChipSort.jl)
RadixSort really tends to work great when it can be used, which is most cases in my experience. I’m still not sure what makes it so great, though, I suspect some compiler optimizations may be applied (such as vectorization), but I never checked what exactly happens. In my research I found out this CombSort algorithm gets very well optimized, but it can’t beat Radix.
OP might be interested in looking at that work. I’d like to point out that practical quicksort tends to work better if you switch to insertion sort for small lists, so you might like to modify both implementations and see if it gets even faster on both languages.