Open AhmedSalih3d opened 5 months ago
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 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.
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
!
, and note that slower non-allocating alg
s exist.!
does not mean non-allocating.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-allocatingalg
s 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
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.
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
Hi!
Full thread here:
https://discourse.julialang.org/t/why-does-sortperm-allocate-here/112028/3
Doing a small example it is easy to see that sortperm! will allocate:
This is because a scratch-space has not been preallocated. Dan kindly provided the following code which fixes the issue:
I would not have been able to discover this without help since the
? sortperm!
returns:With no mention of scratch-space.
I believe that any
!
function is assumed to be non-allocating, and that this goes against this.I went to check help for
sort!
too and did not find any mention of scratch space either.