Missing documentation: sortperm! is not truly non-allocating unless scratchspace is provided about julia HOT 6 OPEN

I believe that any ! function is assumed to be non-allocating, and that this goes against this.

It's a style convention, not something enforced, and it's about modifying at least one of arguments, not being entirely non-allocating.

from julia.

I am programming non-allocating algorithms for simulations

Why must your algorithms not allocate? If it is for performance reasons, remember that unexpected allocations are typically a sign of type instability or other major performance issues, but allocations themselves are not all that slow and can enable faster algorithms.

What are the slower non-allocating algorithms?

On Julia 1.9+, you can use alg=QuickSort. On older versions there are none (QuickSort sometimes does allocate)

julia> VERSION
v"1.8.5"

julia> x = rand(1:10, 100);

julia> @b sort!($x, alg=QuickSort)
248.288 ns (1 allocs: 144 bytes)

I just make a fork of official doc, put some text in and then we take it from there?

Yes! Once you are ready to contribute the changes you've made to the official docs, make a pull request, and feel free to @ me in it.

from julia.

I believe that any ! function is assumed to be non-allocating, and that this goes against this.

It's a style convention, not something enforced, and it's about modifying at least one of arguments, not being entirely non-allocating.

I don't disagree that ! can be simply taking as modify arguments in place but I believe that most instinctively see it as does not allocate. Even if one does not agree with this, I still think it would be beneficial to somewhere in sort functions, to actually mention the scratchspace variable.

from julia.

Scratchspace handling in sorting is okay but not perfect. For example, sometimes it still allocates when passed a scratchspace. I don't want to commit to keeping the current system as is forever. For example, it's possible using Memory might be better. Consequently, I chose not to publicize it (and therefore make it a part of the stable API) when I added it.

I have yet to find a single real-world example where explicitly passing a scratch space to sort! or any of its variants is a good idea or even has a measurable impact on performance. Until someone finds such an example, or scratch space handling is perfect, I'm inclined to think it's premature to publicize & document it.

Actionable things here

• Document that sorting may allocate even when the function ends with an !, and note that slower non-allocating algs exist.
• Document more clearly that ! does not mean non-allocating.

from julia.

I have yet to find a single real-world example where explicitly passing a scratch space to sort! or any of its variants is a good idea or even has a measurable impact on performance. Until someone finds such an example, or scratch space handling is perfect, I'm inclined to think it's premature to publicize & document it.

FWIW, I have experimented with scratch spaces for sort! in my code (repetitive sorting of rows and columns of huge sparse matrices), which gave 1-3% overall speed up in linear algebra for particular "real-world" examples.

So I think it is a nice improvement :), though no idea how useful it is in general

from julia.

Scratchspace handling in sorting is okay but not perfect. For example, sometimes it still allocates when passed a scratchspace. I don't want to commit to keeping the current system as is forever. For example, it's possible using Memory might be better. Consequently, I chose not to publicize it (and therefore make it a part of the stable API) when I added it.

I have yet to find a single real-world example where explicitly passing a scratch space to sort! or any of its variants is a good idea or even has a measurable impact on performance. Until someone finds such an example, or scratch space handling is perfect, I'm inclined to think it's premature to publicize & document it.

Actionable things here

• Document that sorting may allocate even when the function ends with an !, and note that slower non-allocating algs exist.
• Document more clearly that ! does not mean non-allocating.

Thanks for detailed explanation.

Okay, if scratchspace is not part of official/stable API, it does not make sense to document it inside of ? in my opinion - especially if providing a scratch space at times is not enough to avoid allocations. What are the slower non-allocating algorithms ?

I think what you suggest by improving the explanation here, https://docs.julialang.org/en/v1/manual/style-guide/#bang-convention, to highlight that in-place operations does not mean non-allocating. I just make a fork of official doc, put some text in and then we take it from there?

I had a weird edge case, in which if I commented out a line, then sortperm! would not allocate at all, if I commented it in, it would allocate once. I am programming non-allocating algorithms for simulations, so I need to ensure there is truly none - this is why I spotted it in the first place.

Kind regards

from julia.