Skip to content
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

Unexpected allocations in radix sort #47474

Closed
LilithHafner opened this issue Nov 7, 2022 · 0 comments · Fixed by #47383
Closed

Unexpected allocations in radix sort #47474

LilithHafner opened this issue Nov 7, 2022 · 0 comments · Fixed by #47383
Labels
performance Must go faster sorting Put things in order

Comments

@LilithHafner
Copy link
Member

There should be two allocations, one as a scratch space for elements and one as a count vector. There are three:

julia> using BenchmarkTools

julia> v = rand(Int, 1000);

julia> @btime sort!(rand!($v));
21.259 μs (3 allocations: 10.16 KiB)

I tested this on 5dfd6c9 and current master and results are the same.

VSCode's @profview_allocs tracks the third allocation to the iteration in this line:

@inbounds for shift in 0:chunk_size:bits-1

@LilithHafner LilithHafner added the sorting Put things in order label Nov 7, 2022
LilithHafner pushed a commit that referenced this issue Nov 7, 2022
fixes #47474
in this PR rather than separate to avoid dealing with the merge
LilithHafner pushed a commit that referenced this issue Nov 8, 2022
fixes #47474
in this PR rather than separate to avoid dealing with the merge
LilithHafner pushed a commit that referenced this issue Nov 8, 2022
fixes #47474
in this PR rather than separate to avoid dealing with the merge
@brenhinkeller brenhinkeller added the performance Must go faster label Nov 21, 2022
KristofferC pushed a commit that referenced this issue Dec 8, 2022
* create an internal `_sort!` function and use it (rename the existing `_sort!` to `__sort!`)

* test for several of bugs that slipped through test suite

* Give each sorting pass and DEFAULT_STABLE a docstring

* add pretty printing for the new algorithms that are much more flexible than the old ones

* fix unexpected allocations in Radix Sort

fixes #47474
in this PR rather than separate to avoid dealing with the merge

* support and test backwards compatibility with packages that depend in sorting internals

* support 3-, 5-, and 6-argument sort! for backwards compatibility

* overhall scratch space handling

make _sort! return scratch space rather than sorted vector
so that things like IEEEFloatOptimization can re-use the
scratch space allocated on their first recursive call

* test handling -0.0 in IEEEFloatOptimization

* fix and test bug where countsort's correct overflow behavior triggers error due to unexpected promotion to UInt

(cherry picked from commit cee0a04)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
performance Must go faster sorting Put things in order
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants