Feature request: Non allocating sort for tuple #54489
Comments
nsajko
added
feature
|
We had support for this in #46104. The whole thing got reverted on the grounds of making it harder to define custom sorting functions in a package in a nonbreaking way, but |
Merged
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 3, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 3, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 3, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 3, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 3, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 3, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 8, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 8, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 8, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 8, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 8, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 9, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 10, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
nsajko
added a commit
to nsajko/julia
that referenced
this issue
Nov 10, 2024
Uses merge sort, as an obvious choice for a stable sort of tuples. A recursive data structure of singleton type, representing Peano natural numbers, is used to help with splitting a tuple into two halves in the merge sort. An alternative design would use a reference tuple, but this would require relying on `tail`, which seems more harsh on the compiler. With the recursive datastructure the predecessor operation and the successor operation are both trivial. Allows inference to preserve inferred element type even when tuple length is not known. Follow-up PRs may add further improvements, such as the ability to select an unstable sorting algorithm. The added file, typedomainnumbers.jl is not specific to sorting, thus making it a separate file. Xref JuliaLang#55571. Fixes JuliaLang#54489
LilithHafner
added a commit
that referenced
this issue
Dec 8, 2024
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I think it would be very cool if one could do e.g.
and it would return a sorted tuple blazing fast without allocs. There are packages in the ecosystem like
SortingNetworks.jl that can do this, but they cannot overload
Base.sortwithout piracy. So if sort is used inside some other function it is still slow even on tuples.Would it makes sense to add fast NTuple sort to Base?
The text was updated successfully, but these errors were encountered: