-
Notifications
You must be signed in to change notification settings - Fork 4
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
sortperm
algorithm
#124
Comments
It turns out that Numpy uses multithreading by default, whereas Julia uses 1 thread by default. There is no multithreaded MergeSort:
QuickSort:
Currently with both Julia 1.8 and 1.9, using ThreadsX add ~0.4 s to FFTX. Further tests are needed for the new versions. |
bulk1.0001298.vlsv from EGI ( julia> @benchmark cellindex = sortperm($cellid, alg=QuickSort)
BenchmarkTools.Trial: 17 samples with 1 evaluation.
Range (min … max): 302.087 ms … 323.626 ms ┊ GC (min … max): 0.00% … 0.05%
Time (median): 308.169 ms ┊ GC (median): 0.00%
Time (mean ± σ): 309.514 ms ± 5.991 ms ┊ GC (mean ± σ): 0.14% ± 0.26%
▁ ▁ ▁ ▁ ▁ ▁▁▁ █ ▁ █ ▁ ▁ █
█▁▁▁█▁█▁█▁█▁▁███▁█▁▁▁█▁▁█▁█▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
302 ms Histogram: frequency by time 324 ms <
Memory estimate: 30.26 MiB, allocs estimate: 2. julia> @benchmark cellindex = sortperm($cellid)
BenchmarkTools.Trial: 19 samples with 1 evaluation.
Range (min … max): 260.656 ms … 272.919 ms ┊ GC (min … max): 0.98% … 0.10%
Time (median): 268.170 ms ┊ GC (median): 0.12%
Time (mean ± σ): 267.057 ms ± 4.192 ms ┊ GC (mean ± σ): 0.51% ± 0.55%
█ ▁ ▁▁ ▁ ▁ ▁ ▁ ▁ ▁ █▁ ▁ ▁ ▁▁ ▁
█▁█▁▁▁▁▁▁▁██▁█▁▁█▁▁▁▁▁▁▁▁█▁▁▁█▁▁▁▁▁▁▁█▁▁▁▁▁█▁▁██▁▁█▁█▁██▁▁▁▁█ ▁
261 ms Histogram: frequency by time 273 ms <
Memory estimate: 60.53 MiB, allocs estimate: 4. julia> @benchmark cellindex = sortperm($cellid, alg=MergeSort)
BenchmarkTools.Trial: 21 samples with 1 evaluation.
Range (min … max): 237.798 ms … 246.445 ms ┊ GC (min … max): 1.19% … 0.00%
Time (median): 242.145 ms ┊ GC (median): 0.13%
Time (mean ± σ): 241.943 ms ± 2.068 ms ┊ GC (mean ± σ): 0.42% ± 0.49%
▃ █ ▃
▇▁▁▁▁▁▁▁▁▇▁▇▁▁▇▇▇▁▁▇▁▁▁▁▇▇▁▁▁▁█▁▁▁▇▇▁▁▁█▇█▁▇▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▇ ▁
238 ms Histogram: frequency by time 246 ms <
Memory estimate: 45.39 MiB, allocs estimate: 4. Merge sort is still the winner here for serial sorting. |
Some new attempts that might be useful: https://github.com/LSchwerdt/SimultaneousSortperm.jl |
While comparing the metadata loading performance between Julia and Python, I noticed that a large portion of the time is spent in
sortperm
in Julia andargsort
in Numpy. As of Julia 1.8, the default sorting algorithm, unstableQuickSort
, is not so fast: usingMergeSort
has higher memory usage but is faster.argsort
in Numpy is implemented in OpenBlas/MKL/Blas.See JuliaCollections/SortingAlgorithms.jl#33, JuliaLang/julia#939, JuliaLang/julia#47587
The default sorting algorithm is going to change in Julia 1.9. For now, maybe we first use
MergeSort
and then compare with the new sorting algorithm in Julia 1.9 once it's released.The text was updated successfully, but these errors were encountered: