You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
slices: add Sort, SortStable, IsSorted, BinarySearch, and func variants #47619
This proposal is for use with #43651 (and also relies on the accompanying constraints package described in #45458). We propose adding a new generic function for sorting slices in the sort package and using this code to implement sort.Ints, sort.Float64s and sort.Strings much more efficiently. Similarly, we will do this for other functionality in the sort package.
If this proposal is accepted, the changes will be included with the first release of Go that implements #43651 (we currently expect that that will be Go 1.18).
Part 1 - exposing generic sort functions in the sort package API
We propose exposing a generic sort function for sorting a slice as part of the public API of the sort package. Specifically, a new exported function:
func SliceOf[T constraints.Ordered](x []T)
Typical invocation for some slice of an ordered type (like []int64) will look like this (type inference will obviate the need to specify a type):
sort.SliceOf(s)
Sorts the provided slice in-place, similarly to today’s sort.Slice. The name of this function is subject to discussion.
With this function in the sort package, we can add deprecation notices to existing concrete sort functions: sort.Ints, sort.Float64s, sort.Strings - though these functions will remain in the package in line with Go 1 compatibility guarantee.
Part 2 - generic functions for additional sort package functionality
We propose to provide a generic version of the current sort.IsSorted function:
func SearchSliceOf[T constraints.Ordered](what T, x []T) int
Background - generic sort implementation
An internal sorting function:
func orderedSort[T constraints.Ordered](x []T)
Can be using the same implementation as the internal quickSort_func today, with the type parameter replacing the interface{} and having to provide a less function. Early benchmarks show that this approach is 3-4x faster than the current sort.Ints. This function can be added and used to implement exported functions like sort.Ints or sort.Strings even if we decide not to add new APIs via this proposal.
Reacted by Caleb Spare, Carlana, Mikhail Balabin, Quentin Quaadgras, Aaron Cannon, Oleg Kovalov, Amnon, Nato Boram, Akshit Garg, Yevhen Radionov and 20 more
and using this code to implement sort.Ints, sort.Float64s and sort.Strings much more efficiently.
Changes that speed up the internal implementation probably don't need to go through the proposal process. I think this proposal should focus exclusively on the API additions.
SearchSliceOf should return an int (I assume this was a typo).
SliceOf would cover the most common use cases, and would become the main sort function that people would use, but sort.Slice, sort.Sort, and others permit the use of custom comparison logic. I think it's natural to extend that to the generic versions (better naming welcomed):
func SliceWith[T any](s []T, less func(T, T) bool)
Similarly, I think a generic counterpart to SliceStable taking a less func should also be included.
At that point, I think it would be reasonable to further deprecate Slice, SliceIsSorted, and SliceStable.
Similar to the above, I think we should include a search function which operates on a slice but uses a custom comparison func (again, better naming needed).
func SearchWith[T any](s []T, less func(T, T) bool) int
The majority of my use cases for sort.Search are operating on slices of compound types, and this would make that code more readable.
If we do all that, then the shape of the (non-deprecated) sorting API essentially looks like this:
Functions for sorting/searching slices of comparable elements (e.g., SliceOf).
Functions for sorting/searching slices using arbitrary comparison functions (e.g., my SliceWith)
Functions for sorting/searching any abstract collection of values (e.g., Sort, Search)
Finally, even without my suggested modifications, this proposal will leave the sort API in a fairly messy state: something like ~half of the functions/types will be deprecated, and it's hard to come up with good names for the new functions because all the good names are already used by the old ones. I wonder if we should consider deprecating the entire package and introducing a new sorting package instead.
Reacted by Carlana, Viktor Kojouharov, maja, Axel Wagner, Jérôme Laforge, John Jannotti and Ivan Voras
and using this code to implement sort.Ints, sort.Float64s and sort.Strings much more efficiently.
Changes that speed up the internal implementation probably don't need to go through the proposal process. I think this proposal should focus exclusively on the API additions.
SearchSliceOf should return an int (I assume this was a typo).
Thanks, fixed.
SliceOf would cover the most common use cases, and would become the main sort function that people would use, but sort.Slice, sort.Sort, and others permit the use of custom comparison logic. I think it's natural to extend that to the generic versions (better naming welcomed):
func SliceWith[T any](s []T, less func(T, T) bool)
Similarly, I think a generic counterpart to SliceStable taking a less func should also be included.
At that point, I think it would be reasonable to further deprecate Slice, SliceIsSorted, and SliceStable.
Similar to the above, I think we should include a search function which operates on a slice but uses a custom comparison func (again, better naming needed).
func SearchWith[T any](s []T, less func(T, T) bool) int
The majority of my use cases for sort.Search are operating on slices of compound types, and this would make that code more readable.
If we do all that, then the shape of the (non-deprecated) sorting API essentially looks like this:
Functions for sorting/searching slices of comparable elements (e.g., SliceOf).
Functions for sorting/searching slices using arbitrary comparison functions (e.g., my SliceWith)
Functions for sorting/searching any abstract collection of values (e.g., Sort, Search)
These are reasonable suggestions, and I'd like to see what others think. It's also reasonable to start with a minimal approach, adding just the APIs presented in this proposal, and then add more variants in later releases when we have gained more experience with generics in the stdlib (and perhaps some naming conventions emerge).
Finally, even without my suggested modifications, this proposal will leave the sort API in a fairly messy state: something like ~half of the functions/types will be deprecated, and it's hard to come up with good names for the new functions because all the good names are already used by the old ones. I wonder if we should consider deprecating the entire package and introducing a new sorting package instead.
This is a good point and something we considered, but it seems like a large step to take in 1.18; I'll be happy to hear other opinions as well, of course.
One thing Python has that's there is not a great way to do in Go is sort with a key func. If you're sorting using some expensive transform, it might be nice to run the transform O(N) times instead of O(N log N) times.
I am not convinced about the Of suffix convention when the T is not essentially required. sort.SliceOf(s) sounds like it is a slice of s.
Package sort is the completely general sort.
The title of this issue is "generic functions in the sort package",
but they are not actually generic (in the sense of general) - they are specific to slices.
It seems like sort of slices would fit better in package slices - slices.Sort.
There's going to be a slice-specific implementation anyway, so it's not like being in sort helps share code.
Also, although sorting an ordered slice will be common,
sorting an unordered one will too, and we should provide that.
What about:
package slices
func Sort[Elem any](x []Elem, less func(a, b Elem) bool)
func Search[Elem any](x []Elem, ok func(Elem) bool) int
func SortOrdered[Elem constraints.Ordered](x []Elem)
func SearchOrdered[Elem constraints.Ordered](x Slice, target Elem) int
?
Reacted by Carlana, Slava Dzyba, Andrew LeFevre , Beoran, Shoshin Nikita, Quentin Quaadgras, John, Aurélien Rainone, maja, Michal Bohuslávek and 25 more
Reacted by Gary Willoughby, pankdev, ayyildiz, Openweb, Alexey Ivanov and JMD
Maybe a third package like sort/sortslice so the functions can have shorter names (somewhat unwieldy package name aside) and slices doesn't need to pull in a dependency to sort?
Ah, missed the part about it having a separate implementation. Still, putting it in slices doesn't feel right. I would expect to find it in or around sort. I suppose there would be a lot of deprecation messages pointing to the new location regardless.
To add an additional 👍 to the Key request I've written a lot of less functions that were just return a.Field < b.Field.
Reacted by Nato Boram and Camilo E. Hidalgo Estevez
I am not convinced about the Of suffix convention when the T is not essentially required. sort.SliceOf(s) sounds like it is a slice of s.
Package sort is the completely general sort.
The title of this issue is "generic functions in the sort package",
but they are not actually generic (in the sense of general) - they are specific to slices.
It seems like sort of slices would fit better in package slices - slices.Sort.
There's going to be a slice-specific implementation anyway, so it's not like being in sort helps share code.
Also, although sorting an ordered slice will be common,
sorting an unordered one will too, and we should provide that.
What about:
package slices
func Sort[Elem any](x []Elem, less func(a, b Elem) bool)
func Search[Elem any](x []Elem, ok func(Elem) bool) int
func SortOrdered[Elem constraints.Ordered](x []Elem)
func SearchOrdered[Elem constraints.Ordered](x Slice, target Elem) int
?
This is a good point, Russ. It will, though, put us in the uncomfortable (IMHO) situation of having both sort.Slice and slices.Sort
Reacted by jimmyfrasche
Reacted by Carlana, deef, Nato Boram and Mike Schinkel
One caveat: we chose to exclude SortStable based on @dsnet 's comments; the version with constraints.Ordered is indistinguishable from Sort because two elements that sort equal are otherwise indistinguishable for practical purposes.
Should this proposal remain open until x/exp/slices makes it into the stdlib at some future Go release, or should it be closed and a separate proposal should be made for graduating the package when the time comes?
One caveat: we chose to exclude SortStable based on @dsnet 's comments; the version with constraints.Ordered is indistinguishable from Sort because two elements that sort equal are otherwise indistinguishable for practical purposes.
Should this proposal remain open until x/exp/slices makes it into the stdlib at some future Go release, or should it be closed and a separate proposal should be made for graduating the package when the time comes?
@PeterRK That makes calls quite bulky. It seems inadvisable to have the common case pay the readability cost for a small performance benefit in the uncommon one.
It's common to sort struct array in my experience. In such case, generic func api can be slower than legacy api on AMD CPU.
I have opened a new proposal #57433 to move golang.org/x/exp/slices into the standard library. Closing this proposal as completed. Thanks for all the discussion.
Activity
randall77 commentedon Aug 10, 2021
eliben commentedon Aug 10, 2021
cespare commentedon Aug 10, 2021
Changes that speed up the internal implementation probably don't need to go through the proposal process. I think this proposal should focus exclusively on the API additions.
SearchSliceOfshould return anint(I assume this was a typo).SliceOfwould cover the most common use cases, and would become the mainsortfunction that people would use, butsort.Slice,sort.Sort, and others permit the use of custom comparison logic. I think it's natural to extend that to the generic versions (better naming welcomed):Similarly, I think a generic counterpart to
SliceStabletaking alessfunc should also be included.At that point, I think it would be reasonable to further deprecate
Slice,SliceIsSorted, andSliceStable.Similar to the above, I think we should include a search function which operates on a slice but uses a custom comparison func (again, better naming needed).
The majority of my use cases for
sort.Searchare operating on slices of compound types, and this would make that code more readable.If we do all that, then the shape of the (non-deprecated) sorting API essentially looks like this:
SliceOf).SliceWith)Sort,Search)Finally, even without my suggested modifications, this proposal will leave the sort API in a fairly messy state: something like ~half of the functions/types will be deprecated, and it's hard to come up with good names for the new functions because all the good names are already used by the old ones. I wonder if we should consider deprecating the entire package and introducing a new sorting package instead.
eliben commentedon Aug 11, 2021
Thanks, fixed.
These are reasonable suggestions, and I'd like to see what others think. It's also reasonable to start with a minimal approach, adding just the APIs presented in this proposal, and then add more variants in later releases when we have gained more experience with generics in the stdlib (and perhaps some naming conventions emerge).
This is a good point and something we considered, but it seems like a large step to take in 1.18; I'll be happy to hear other opinions as well, of course.
earthboundkid commentedon Aug 11, 2021
🚴 :
SliceIsSortedOf→ sort.IsSortedSliceOfSliceStableOf→ sort.StableSliceOfThe other name suggestions seem fine.
earthboundkid commentedon Aug 11, 2021
One thing Python has that's there is not a great way to do in Go is sort with a key func. If you're sorting using some expensive transform, it might be nice to run the transform O(N) times instead of O(N log N) times.
rsc commentedon Aug 11, 2021
I am not convinced about the Of suffix convention when the T is not essentially required.
sort.SliceOf(s)sounds like it is a slice of s.Package sort is the completely general sort.
The title of this issue is "generic functions in the sort package",
but they are not actually generic (in the sense of general) - they are specific to slices.
It seems like sort of slices would fit better in package slices - slices.Sort.
There's going to be a slice-specific implementation anyway, so it's not like being in sort helps share code.
Also, although sorting an ordered slice will be common,
sorting an unordered one will too, and we should provide that.
What about:
?
jimmyfrasche commentedon Aug 11, 2021
Maybe a third package like
sort/sortsliceso the functions can have shorter names (somewhat unwieldy package name aside) andslicesdoesn't need to pull in a dependency to sort?rsc commentedon Aug 11, 2021
I don't think slices would have a dependency on sort at all.
jimmyfrasche commentedon Aug 11, 2021
Ah, missed the part about it having a separate implementation. Still, putting it in slices doesn't feel right. I would expect to find it in or around sort. I suppose there would be a lot of deprecation messages pointing to the new location regardless.
To add an additional 👍 to the Key request I've written a lot of less functions that were just
return a.Field < b.Field.eliben commentedon Aug 11, 2021
This is a good point, Russ. It will, though, put us in the uncomfortable (IMHO) situation of having both
sort.Sliceandslices.Sortcespare commentedon Aug 11, 2021
If
sort.Sliceis documented as being deprecated in favor orslices.Sortandslices.SortOrderedit shouldn't be too confusing.66 remaining items
eliben commentedon Jan 21, 2022
With https://go-review.googlesource.com/c/exp/+/378134, the functions outlined in #47619 (comment) are now implemented in the
slicespackage inx/exp.One caveat: we chose to exclude
SortStablebased on @dsnet 's comments; the version withconstraints.Orderedis indistinguishable fromSortbecause two elements that sort equal are otherwise indistinguishable for practical purposes.Should this proposal remain open until
x/exp/slicesmakes it into the stdlib at some future Go release, or should it be closed and a separate proposal should be made for graduating the package when the time comes?ianlancetaylor commentedon Jan 21, 2022
Let's leave this open for consideration for 1.19. I'll put it on hold for now.
PeterRK commentedon Jan 22, 2022
I ran a detail benchmark including this implement.
PeterRK commentedon Jan 28, 2022
It's common to sort struct array in my experience. In such case, generic func api can be slower than legacy api on AMD CPU.
See benchmark result on EPYC-7K83 machine.
Performance benefit of reference compare fcunc is significant.
Pointer array will be sorted faster than struct array only when size is small engouth to cache.
sort: use a different codegen strategy
ianlancetaylor commentedon Dec 21, 2022
I have opened a new proposal #57433 to move golang.org/x/exp/slices into the standard library. Closing this proposal as completed. Thanks for all the discussion.