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

slices: add Sort, SortStable, IsSorted, BinarySearch, and func variants #47619

Open
eliben opened this issue Aug 10, 2021 · 71 comments
Open

slices: add Sort, SortStable, IsSorted, BinarySearch, and func variants #47619

eliben opened this issue Aug 10, 2021 · 71 comments

Comments

@eliben
Copy link
Member

@eliben eliben commented Aug 10, 2021

Update, Sep 15 2021: the current proposal is at #47619 (comment). - @rsc


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 SliceIsSortedOf[T constraints.Ordered](x []T)

Efficient stable sorts:

func SliceStableOf[T constraints.Ordered](x []T)

Binary search:

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.

@gopherbot gopherbot added this to the Proposal milestone Aug 10, 2021
@randall77

This comment has been minimized.

@seankhliao seankhliao added the generics label Aug 10, 2021
@eliben

This comment has been minimized.

@ianlancetaylor ianlancetaylor added this to Incoming in Proposals Aug 10, 2021
@cespare
Copy link
Contributor

@cespare cespare commented Aug 10, 2021

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:

  1. Functions for sorting/searching slices of comparable elements (e.g., SliceOf).
  2. Functions for sorting/searching slices using arbitrary comparison functions (e.g., my SliceWith)
  3. 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.

@eliben
Copy link
Member Author

@eliben eliben commented Aug 11, 2021

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:

  1. Functions for sorting/searching slices of comparable elements (e.g., SliceOf).
  2. Functions for sorting/searching slices using arbitrary comparison functions (e.g., my SliceWith)
  3. 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.

@carlmjohnson
Copy link
Contributor

@carlmjohnson carlmjohnson commented Aug 11, 2021

🚴 :

  • SliceIsSortedOf → sort.IsSortedSliceOf
  • SliceStableOf → sort.StableSliceOf

The other name suggestions seem fine.

@carlmjohnson
Copy link
Contributor

@carlmjohnson carlmjohnson commented 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.

func SliceByKey[T1 any, T2 comparable](s []T1, key func(T1) T2)

@rsc
Copy link
Contributor

@rsc rsc commented 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:

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

?

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Aug 11, 2021

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?

@rsc
Copy link
Contributor

@rsc rsc commented Aug 11, 2021

I don't think slices would have a dependency on sort at all.

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented 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
Copy link
Member Author

@eliben eliben commented 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:

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

@cespare
Copy link
Contributor

@cespare cespare commented Aug 11, 2021

It will, though, put us in the uncomfortable (IMHO) situation of having both sort.Slice and slices.Sort

If sort.Slice is documented as being deprecated in favor or slices.Sort and slices.SortOrdered it shouldn't be too confusing.

@carlmjohnson
Copy link
Contributor

@carlmjohnson carlmjohnson commented Aug 11, 2021

sync.Map has a similar problem.

Here's a solution that makes no one happy: sort/v2. Why not do it though?

@eliben
Copy link
Member Author

@eliben eliben commented Aug 11, 2021

There's going to be a slice-specific implementation anyway, so it's not like being in sort helps share code.

A note about this: as the background section of this proposal mentions, a generic implementation of slice sorting will be used to reimplement the existing sort.Ints, sort.Strings etc. much more efficiently. So there is some sharing of implementation if we do opt for slices.Sort. I assume this shared implementation can be placed in src/internal then?

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Aug 11, 2021

I opened #47657 for sync.Map and friends.

@rsc rsc changed the title proposal: generic functions in the sort package proposal: sort: generic functions Aug 25, 2021
@rsc rsc moved this from Incoming to Active in Proposals Aug 25, 2021
@rsc
Copy link
Contributor

@rsc rsc commented Aug 25, 2021

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

@dsnet
Copy link
Member

@dsnet dsnet commented Aug 25, 2021

A common operation that I do is iterating over a map in sorted manner (usually of a string key).

#47649 provides:

func Keys[K comparable, V any](m map[K]V) []K

Which we can combine with the above proposal to do:

ks := maps.Keys(m)
sort.SliceOf(ks)
for _, k := range ks {
    ...
}

I wonder if we can simplify this by having SliceOf return the input.

for _, k := range sort.SliceOf(maps.Keys(m)) {
    ...
}

The detriment of returning the slice is that it makes it ambiguous from the function signature whether sort.SliceOf mutates the input in place or copies it.

@carlmjohnson
Copy link
Contributor

@carlmjohnson carlmjohnson commented Aug 25, 2021

A common operation that I do is iterating over a map in sorted manner (usually of a string key).

What about having maps.SortedKeys? Seems like a fairly common need.

@dsnet
Copy link
Member

@dsnet dsnet commented Aug 25, 2021

The maps package is pretty simple, I don't think we would want a dependency on the relatively complicated sort package.

The other direction seems more palatable. We could add sort.MapKeysOf:

func MapKeysOf[K constraints.Ordered, V any](m [K]V) []K

However, it might be weird that it's signature and operation is different than the similarly named sort.SliceOf function.

@cespare
Copy link
Contributor

@cespare cespare commented Aug 25, 2021

@dsnet I also find that I need this a lot. However, returning the input just to allow fewer newlines to be typed (which I guess would be called "chaining" if we were talking about methods) isn't the prevailing style. Also, as you say, it makes the signature less obvious; people will be much more likely to call SliceOf incorrectly, assuming it doesn't mutate the input.

Personally, your second example seems pretty good to me:

ks := maps.Keys(m)
sort.SliceOf(ks)
for _, k := range ks {
    ...
}

If we want to shorten it, I agree with @carlmjohnson that we should add to maps:

func SortedKeys[K constraints.Ordered, V any](m map[K]V) []K

Regarding adding this to sort vs. maps, also note that @rsc proposed adding the slice-sorting stuff to slices instead of sort in #47619 (comment), and also we don't need to add a dependency on sort to have maps provide this function.

I also think in the future for a lot of these use cases I might instead use a sorted container instead (a map that maintains the keys in sorted order; presumably backed by a tree). However, that requires more API design work (especially around iteration) and I expect we won't see anything like that in the standard library before 1.19.

@rsc
Copy link
Contributor

@rsc rsc commented Sep 1, 2021

I am not sure we should do the extra return value - it will look like maybe it returns a different slice.

I still believe we should think about slices.Sort instead of sort.NewSliceName; see #47619 (comment).

@eliben
Copy link
Member Author

@eliben eliben commented Sep 1, 2021

Having these functions in the slices package certainly makes the naming prettier.

We can just deprecate sort.Ints, sort.Strings etc. without worrying about making them faster; pointing to slices.SortOrdered instead - it replaces both of them.

In your list of new functions:

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

Is Search different from slices.IndexFunc because it assumes the slice is sorted (like the Search* functions from the sort package)? There could be some confusion there, it seems. Since these new Search* functions are not in the sort package, perhaps it will be clearer to call them BinarySearch*?

@eliben
Copy link
Member Author

@eliben eliben commented Sep 29, 2021

More detailed thoughts on implementation, following #47619 (comment)

If we go with a codegen approach, there are two decisions to be made:

  1. Where does this codegen mechanism live? In src/sort? In (the upcoming) src/slices? In some internal directory?
  2. How is the codegen implemented

This comment will discuss alternatives for (2). One approach is to extend the existing strategy wherein the code generator parses and analyzes the data sort.Interface variant of sorting and emits the other variants. The current code in genzfunc.go for doing so is a combination of a lightweight AST rewrite with some regexp text replacements. Extending it to emit the generic versions will be challenging.

The main challenge stems from the AST replacement capabilities of go/ast. The current generator is set up only to replace names of calls (e.g. foo(args) --> foo_func(args)), but for the generic version we'll have to replace:

   data.Less(j, j-1)

by:

   data[j] < data[j-1]

And to do so within expressions. AFAICS, this is hard to do with vanilla go/ast, without writing a large amount of code or using something like https://pkg.go.dev/golang.org/x/tools/go/ast/astutil (a dependency that the repo's go.mod does not currently have).


An alternative approach is to replace the current codegen mechanism by a much simpler scheme which uses a text/template template as the "source of truth" and emits all the required variants from it. https://golang.org/cl/353069 demonstrates a refactoring of the current codegen (just generating the two existing variants) as a demonstration; updating this CL to generate also the generic versions is trivial.

Tradeoffs:

  • In-favor of existing codegen: the source of truth is a .go file which is easier to edit and work with, not needing to use {{... template ...}} tags.
  • In favor of new approach: significantly simpler codegen, without needing to handle edge cases in hacky ways (with regexp rewrites).

[Due to the quiet week I don't expect anyone to be looking at this until Monday, which is fine. I don't plan further work on this until Monday anyway - just wanted to lay out the options]

@gopherbot
Copy link

@gopherbot gopherbot commented Sep 29, 2021

Change https://golang.org/cl/353069 mentions this issue: sort: use a different codegen strategy

@PeterRK
Copy link

@PeterRK PeterRK commented Oct 24, 2021

Completely agree about adding "Binary" per #47619 (comment). Thanks @carlmjohnson.

Otherwise, it sounds like people are generally in favor of:

package slices

func Sort[Elem constraints.Ordered](x []Elem)
func SortFunc[Elem any](x []Elem, less func(a, b Elem) bool)
func SortStable[Elem constraints.Ordered](x []Elem)
func SortStableFunc[Elem any](x []Elem, less func(a, b Elem) bool)
func IsSorted[Elem constraints.Ordered](x []Elem)
func IsSortedFunc[Elem any](x []Elem, less func(a, b Elem) bool)

func BinarySearch[Elem constraints.Ordered](x Slice, target Elem) int
func BinarySearchFunc[Elem any](x []Elem, ok func(Elem) bool) int

(Not completely unanimous but generally in favor.)

How about adding a Order struct instead of APIs with Func suffix?

func Sort[Elem constraints.Ordered](list []Elem)
func SortStable[Elem constraints.Ordered](list []Elem)
func IsSorted[Elem constraints.Ordered](list []Elem) bool
func BinarySearch[Elem constraints.Ordered](list []Elem, x Elem) int

type Order[Elem any] struct {
	Less    func(a, b Elem) bool
	RefLess func(a, b *Elem) bool
}

func (od *Order[Elem]) Sort(list []Elem)
func (od *Order[Elem]) SortStable(list []Elem)
func (od *Order[Elem]) IsSorted(list []Elem) bool
func (od *Order[Elem]) BinarySearch(list []Elem, x Elem) int

It works with at least one of Less and RefLess is set. When both of them are set, we can pick the faster one.
A demo implement: https://github.com/PeterRK/slices

@Merovius
Copy link

@Merovius Merovius commented Oct 24, 2021

@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.

@PeterRK
Copy link

@PeterRK PeterRK commented Oct 24, 2021

@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.

I can't see how it makes calls bulky.
There are many similar design, having both APIs with and without receiver, like math/rand and net/http.
It's easy to get func SortFunc[Elem any](list []Elem, less func(a, b Elem) bool) or func SortFunc[Elem any](list []Elem, less func(a, b *Elem) bool) by wrapping func (od *Order[Elem]) Sort(list []Elem), for people who think APIs with receiver are less readable.

@Merovius
Copy link

@Merovius Merovius commented Oct 24, 2021

I can't see how it makes calls bulky.

(&slices.Order[MyType]{Less:MyType.Less}).Sort(a) is more bulky than slices.SortFunc(a, MyType.Less).

@PeterRK
Copy link

@PeterRK PeterRK commented Oct 24, 2021

If Less is predefined, Order can also be predefined.
MyType.Order.Sort(list) is not bulky than slices.SortFunc(list, MyType.Less)

But (&slices.Order[MyType]{Less: func(a, b MyType) bool { ... }}).Sort(list) is a little bulky than slices.SortFunc(list, func(a, b MyType) bool { ... })

@anacrolix
Copy link
Contributor

@anacrolix anacrolix commented Nov 29, 2021

Is there an experimental implementation per #47619 (comment)? I would like to try this out.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Nov 29, 2021

@anacrolix A nonoptimal implementation is straightforward: https://gotipplay.golang.org/p/l8ZyZHk2rIZ

@anacrolix
Copy link
Contributor

@anacrolix anacrolix commented Nov 29, 2021

@ianlancetaylor it's the optimal implementation I'm after, the reflection overhead in the existing sort.Slice is very high.

@DeedleFake
Copy link

@DeedleFake DeedleFake commented Nov 29, 2021

The implementation that @ianlancetaylor posted is probably still more efficient than sort.Slice() as it doesn't need any reflection, but it does still have some slowdown from the dynamic dispatch of the interface.

I'm not sure how feasible it is as I'm not particularly familiar with the code, but you could probably make a copy of the sort package and modify it. My guess is that reimplementing sort.Sort() to specifically sort a generic slice shouldn't be too bad.

@PeterRK
Copy link

@PeterRK PeterRK commented Nov 30, 2021

Is there an experimental implementation per #47619 (comment)? I would like to try this out.

@anacrolix Here is an unofficial implement.

Benchmark based on eliben's

cpu: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
BenchmarkSortInts-6                	      96	  11628975 ns/op
BenchmarkHandwritten-6             	     201	   6037514 ns/op
BenchmarkGeneric-6                 	     202	   6002725 ns/op
BenchmarkGenericFunc-6             	     127	   9042840 ns/op
BenchmarkGenericUnofficial-6       	     260	   4745175 ns/op
BenchmarkGenericFuncUnofficial-6   	     144	   8216196 ns/op

@anacrolix

This comment has been minimized.

@cespare

This comment has been minimized.

@zhangyunhao116
Copy link
Contributor

@zhangyunhao116 zhangyunhao116 commented Dec 21, 2021

I agree with having separate versions of the implementation for sort and slices.

Here is two implementations using same sorting algorithm:

The generic version is 2x faster in the benchmark, significantly faster than the interface-based one.

Also here is another issue(#50154 ) that suggests using pdqsort in the sort package, I wonder if we can use the generic implementation for this proposal.

@PeterRK
Copy link

@PeterRK PeterRK commented Dec 27, 2021

Is there an experimental implementation per #47619 (comment)? I would like to try this out.

@anacrolix Here is an unofficial implement.

Benchmark based on eliben's

cpu: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
BenchmarkSortInts-6                	      96	  11628975 ns/op
BenchmarkHandwritten-6             	     201	   6037514 ns/op
BenchmarkGeneric-6                 	     202	   6002725 ns/op
BenchmarkGenericFunc-6             	     127	   9042840 ns/op
BenchmarkGenericUnofficial-6       	     260	   4745175 ns/op
BenchmarkGenericFuncUnofficial-6   	     144	   8216196 ns/op

Another benchmark: https://gist.github.com/PeterRK/e2fa03a2657d4a406ee289c80612380b

Result:

benchmark                     std ns/op     new ns/op     delta
Benchmark/Small-1K-6          32930         19088         -42.03%
Benchmark/Small-10K-6         580943        245059        -57.82%
Benchmark/Small-100K-6        7299951       3016324       -58.68%
Benchmark/Small-1M-6          96994308      39039379      -59.75%
Benchmark/Random-1K-6         72789         36152         -50.33%
Benchmark/Random-10K-6        933827        401895        -56.96%
Benchmark/Random-100K-6       11455999      4604136       -59.81%
Benchmark/Random-1M-6         138147588     53966610      -60.94%
Benchmark/Constant-1K-6       7324          1110          -84.84%
Benchmark/Constant-10K-6      61366         8325          -86.43%
Benchmark/Constant-100K-6     602951        100609        -83.31%
Benchmark/Constant-1M-6       5397124       1112368       -79.39%
Benchmark/Descent-1K-6        28712         2190          -92.37%
Benchmark/Descent-10K-6       366450        19432         -94.70%
Benchmark/Descent-100K-6      4323979       205271        -95.25%
Benchmark/Descent-1M-6        49287429      1834082       -96.28%
Benchmark/Ascent-1K-6         26286         1228          -95.33%
Benchmark/Ascent-10K-6        360613        12602         -96.51%
Benchmark/Ascent-100K-6       4455140       125210        -97.19%
Benchmark/Ascent-1M-6         50476172      1252582       -97.52%
Benchmark/Mixed-1K-6          42709         20608         -51.75%
Benchmark/Mixed-10K-6         536684        239532        -55.37%
Benchmark/Mixed-100K-6        6978755       2389427       -65.76%
Benchmark/Mixed-1M-6          83379650      29073586      -65.13%

eliben added a commit to eliben/go that referenced this issue Jan 12, 2022
The existing codegen strategy in sort.go relied on parsing the sort.go source
with go/ast and a combination of an AST rewrite + code text rewrite with regexes
to generate zfuncversion -- the same sort functionality with a different variant
of data.

In preparation for implementing golang#47619, we need a more robust codegen
strategy. To generate variants required for the generic sort functions
in the slices package, we'd need significanly more complicated AST
rewrites, which would make genzfunc.go much heavier.

Instead, redo the codegen strategy to use text/template instead of AST rewrites.
gen_sort_variants.go now contains the code for the underlying sort functions,
and generates multiple versions of them based on Variant configuration structs.
With this approach, adding new variants to generate generic sort functions for
the slices package becomes trivial.

See the discussion in golang#47619 for more details on the design decisions.

Change-Id: I8af784c41b1dc8ef92aaf6321359e8faa5fe106c
eliben added a commit to eliben/go that referenced this issue Jan 12, 2022
The existing codegen strategy in sort.go relied on parsing the sort.go source
with go/ast and a combination of an AST rewrite + code text rewrite with regexes
to generate zfuncversion -- the same sort functionality with a different variant
of data.

In preparation for implementing golang#47619, we need a more robust codegen
strategy. To generate variants required for the generic sort functions
in the slices package, we'd need significanly more complicated AST
rewrites, which would make genzfunc.go much heavier.

Instead, redo the codegen strategy to use text/template instead of AST rewrites.
gen_sort_variants.go now contains the code for the underlying sort functions,
and generates multiple versions of them based on Variant configuration structs.
With this approach, adding new variants to generate generic sort functions for
the slices package becomes trivial.

See the discussion in golang#47619 for more details on the design decisions.

Change-Id: I8af784c41b1dc8ef92aaf6321359e8faa5fe106c
eliben added a commit to eliben/go that referenced this issue Jan 13, 2022
The existing codegen strategy in sort.go relied on parsing the sort.go source
with go/ast and a combination of an AST rewrite + code text rewrite with regexes
to generate zfuncversion -- the same sort functionality with a different variant
of data.

In preparation for implementing golang#47619, we need a more robust codegen
strategy. To generate variants required for the generic sort functions
in the slices package, we'd need significanly more complicated AST
rewrites, which would make genzfunc.go much heavier.

Instead, redo the codegen strategy to use text/template instead of AST rewrites.
gen_sort_variants.go now contains the code for the underlying sort functions,
and generates multiple versions of them based on Variant configuration structs.
With this approach, adding new variants to generate generic sort functions for
the slices package becomes trivial.

See the discussion in golang#47619 for more details on the design decisions.

Change-Id: I8af784c41b1dc8ef92aaf6321359e8faa5fe106c
@gopherbot
Copy link

@gopherbot gopherbot commented Jan 13, 2022

Change https://golang.org/cl/378134 mentions this issue: slices: initial implementation of sorting functions

gopherbot pushed a commit to golang/exp that referenced this issue Jan 21, 2022
Implements golang/go#47619 in the exp/slices package as a
testing ground prior to inclusion in the standard library.

Relies on the modified sorting function code generator proposed
in https://go-review.googlesource.com/c/go/+/353069 to
automatically generate the code of the sorting functions.

Benchmark comparing sort.Ints with the generic Sort function
added in this CL to sort a slice of int:

name           old time/op  new time/op  delta
Sort-8         12.0ms ± 1%   6.5ms ± 1%  -46.02%  (p=0.000 n=9+10)

Benchmark comparing sort.Sort with SortFunc to sort a slice of
struct pointers based on one field in the struct:

name           old time/op  new time/op  delta
SortStructs-8  18.6ms ± 2%  15.9ms ± 3%  -14.43%  (p=0.000 n=10+10)

Change-Id: Ic301aae7e5b8f99144e39b8a77fde897779588ed
Reviewed-on: https://go-review.googlesource.com/c/exp/+/378134
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Trust: Cody Oss <codyoss@google.com>
Trust: Jeremy Faller <jeremy@golang.org>
@eliben
Copy link
Member Author

@eliben eliben commented Jan 21, 2022

With https://go-review.googlesource.com/c/exp/+/378134, the functions outlined in #47619 (comment) are now implemented in the slices package in x/exp.

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?

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jan 21, 2022

Let's leave this open for consideration for 1.19. I'll put it on hold for now.

@PeterRK
Copy link

@PeterRK PeterRK commented Jan 22, 2022

With https://go-review.googlesource.com/c/exp/+/378134, the functions outlined in #47619 (comment) are now implemented in the slices package in x/exp.

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?

I ran a detail benchmark including this implement.

cpu: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
BenchmarkIntUno/Small-1K-6         	   88856	     12702 ns/op
BenchmarkIntUno/Small-10K-6        	    6394	    185139 ns/op
BenchmarkIntUno/Small-100K-6       	     507	   2621073 ns/op
BenchmarkIntUno/Small-1M-6         	      38	  32514718 ns/op
BenchmarkIntUno/Random-1K-6        	   34459	     31133 ns/op
BenchmarkIntUno/Random-10K-6       	    3592	    367725 ns/op
BenchmarkIntUno/Random-100K-6      	     298	   4083428 ns/op
BenchmarkIntUno/Random-1M-6        	      22	  48688205 ns/op
BenchmarkIntUno/Constant-1K-6      	 1247536	       999 ns/op
BenchmarkIntUno/Constant-10K-6     	  175213	      7144 ns/op
BenchmarkIntUno/Constant-100K-6    	   17924	     71266 ns/op
BenchmarkIntUno/Constant-1M-6      	    1905	    635953 ns/op
BenchmarkIntUno/Descent-1K-6       	  559680	      1788 ns/op
BenchmarkIntUno/Descent-10K-6      	   75807	     15175 ns/op
BenchmarkIntUno/Descent-100K-6     	    6780	    148670 ns/op
BenchmarkIntUno/Descent-1M-6       	     799	   1422321 ns/op
BenchmarkIntUno/Ascent-1K-6        	 1249099	      1047 ns/op
BenchmarkIntUno/Ascent-10K-6       	  177018	      7024 ns/op
BenchmarkIntUno/Ascent-100K-6      	   14989	     74116 ns/op
BenchmarkIntUno/Ascent-1M-6        	    1575	    877049 ns/op
BenchmarkIntUno/Mixed-1K-6         	   78850	     17578 ns/op
BenchmarkIntUno/Mixed-10K-6        	    5616	    203427 ns/op
BenchmarkIntUno/Mixed-100K-6       	     480	   2498868 ns/op
BenchmarkIntUno/Mixed-1M-6         	      57	  26758177 ns/op
BenchmarkIntExp/Small-1K-6         	   81180	     14876 ns/op
BenchmarkIntExp/Small-10K-6        	    4948	    250853 ns/op
BenchmarkIntExp/Small-100K-6       	     327	   3690185 ns/op
BenchmarkIntExp/Small-1M-6         	      25	  47416352 ns/op
BenchmarkIntExp/Random-1K-6        	   29671	     39187 ns/op
BenchmarkIntExp/Random-10K-6       	    2259	    476909 ns/op
BenchmarkIntExp/Random-100K-6      	     199	   5955907 ns/op
BenchmarkIntExp/Random-1M-6        	      15	  71280120 ns/op
BenchmarkIntExp/Constant-1K-6      	 1000000	      1158 ns/op
BenchmarkIntExp/Constant-10K-6     	  142221	      9571 ns/op
BenchmarkIntExp/Constant-100K-6    	   12907	     98832 ns/op
BenchmarkIntExp/Constant-1M-6      	    1246	    957315 ns/op
BenchmarkIntExp/Descent-1K-6       	  240742	      6722 ns/op
BenchmarkIntExp/Descent-10K-6      	   14536	     82609 ns/op
BenchmarkIntExp/Descent-100K-6     	    1220	    973254 ns/op
BenchmarkIntExp/Descent-1M-6       	     100	  11278199 ns/op
BenchmarkIntExp/Ascent-1K-6        	  246343	      4476 ns/op
BenchmarkIntExp/Ascent-10K-6       	   15201	     79119 ns/op
BenchmarkIntExp/Ascent-100K-6      	    1146	    947925 ns/op
BenchmarkIntExp/Ascent-1M-6        	     100	  11384724 ns/op
BenchmarkIntExp/Mixed-1K-6         	   58015	     19641 ns/op
BenchmarkIntExp/Mixed-10K-6        	    5206	    209231 ns/op
BenchmarkIntExp/Mixed-100K-6       	     478	   2643171 ns/op
BenchmarkIntExp/Mixed-1M-6         	      38	  34377868 ns/op
BenchmarkIntStd/Small-1K-6         	   34884	     33001 ns/op
BenchmarkIntStd/Small-10K-6        	    2343	    528399 ns/op
BenchmarkIntStd/Small-100K-6       	     157	   7641057 ns/op
BenchmarkIntStd/Small-1M-6         	      12	  98196642 ns/op
BenchmarkIntStd/Random-1K-6        	   16496	     75977 ns/op
BenchmarkIntStd/Random-10K-6       	    1353	    915797 ns/op
BenchmarkIntStd/Random-100K-6      	     100	  11402767 ns/op
BenchmarkIntStd/Random-1M-6        	       8	 135574825 ns/op
BenchmarkIntStd/Constant-1K-6      	  241622	      4882 ns/op
BenchmarkIntStd/Constant-10K-6     	   24147	     51507 ns/op
BenchmarkIntStd/Constant-100K-6    	    2793	    509029 ns/op
BenchmarkIntStd/Constant-1M-6      	     254	   4940786 ns/op
BenchmarkIntStd/Descent-1K-6       	   53043	     27615 ns/op
BenchmarkIntStd/Descent-10K-6      	    3361	    339852 ns/op
BenchmarkIntStd/Descent-100K-6     	     288	   4196527 ns/op
BenchmarkIntStd/Descent-1M-6       	      27	  48652700 ns/op
BenchmarkIntStd/Ascent-1K-6        	   38326	     28718 ns/op
BenchmarkIntStd/Ascent-10K-6       	    3510	    360407 ns/op
BenchmarkIntStd/Ascent-100K-6      	     307	   3914663 ns/op
BenchmarkIntStd/Ascent-1M-6        	      26	  50059788 ns/op
BenchmarkIntStd/Mixed-1K-6         	   30819	     41571 ns/op
BenchmarkIntStd/Mixed-10K-6        	    2488	    547777 ns/op
BenchmarkIntStd/Mixed-100K-6       	     188	   6374281 ns/op
BenchmarkIntStd/Mixed-1M-6         	      15	  77249980 ns/op
BenchmarkFloatUno/1K-6             	   33598	     33534 ns/op
BenchmarkFloatUno/10K-6            	    3982	    389529 ns/op
BenchmarkFloatUno/100K-6           	     278	   4513018 ns/op
BenchmarkFloatUno/1M-6             	      22	  49476723 ns/op
BenchmarkFloatExp/1K-6             	   28581	     42989 ns/op
BenchmarkFloatExp/10K-6            	    2132	    503563 ns/op
BenchmarkFloatExp/100K-6           	     202	   6412895 ns/op
BenchmarkFloatExp/1M-6             	      14	  76248986 ns/op
BenchmarkFloatStd/1K-6             	   14424	     83750 ns/op
BenchmarkFloatStd/10K-6            	    1215	    983385 ns/op
BenchmarkFloatStd/100K-6           	      91	  13324582 ns/op
BenchmarkFloatStd/1M-6             	       7	 159035971 ns/op
BenchmarkStrUno/1K-6               	   12822	     93458 ns/op
BenchmarkStrUno/10K-6              	     888	   1195814 ns/op
BenchmarkStrUno/100K-6             	      66	  16102803 ns/op
BenchmarkStrUno/1M-6               	       4	 264538425 ns/op
BenchmarkStrExp/1K-6               	   10000	    103434 ns/op
BenchmarkStrExp/10K-6              	     909	   1255396 ns/op
BenchmarkStrExp/100K-6             	      66	  17768198 ns/op
BenchmarkStrExp/1M-6               	       4	 273693950 ns/op
BenchmarkStrStd/1K-6               	   10000	    118131 ns/op
BenchmarkStrStd/10K-6              	     728	   1604916 ns/op
BenchmarkStrStd/100K-6             	      57	  20938753 ns/op
BenchmarkStrStd/1M-6               	       3	 337909400 ns/op
BenchmarkStructUno/1K-6            	   19466	     68228 ns/op
BenchmarkStructUno/10K-6           	    1027	   1038254 ns/op
BenchmarkStructUno/100K-6          	      80	  12747764 ns/op
BenchmarkStructUno/1M-6            	       7	 146953986 ns/op
BenchmarkStructExp/1K-6            	   10000	    100100 ns/op
BenchmarkStructExp/10K-6           	    1006	   1385711 ns/op
BenchmarkStructExp/100K-6          	      73	  16141007 ns/op
BenchmarkStructExp/1M-6            	       5	 201379500 ns/op
BenchmarkStructStd/1K-6            	    9746	    128873 ns/op
BenchmarkStructStd/10K-6           	     871	   1595922 ns/op
BenchmarkStructStd/100K-6          	      56	  18510054 ns/op
BenchmarkStructStd/1M-6            	       5	 234134520 ns/op
BenchmarkStableUno/1K-6            	   15109	     73802 ns/op
BenchmarkStableUno/10K-6           	     939	   1396880 ns/op
BenchmarkStableUno/100K-6          	      76	  15213303 ns/op
BenchmarkStableUno/1M-6            	       6	 175452000 ns/op
BenchmarkStableExp/1K-6            	    7580	    196757 ns/op
BenchmarkStableExp/10K-6           	     400	   2775955 ns/op
BenchmarkStableExp/100K-6          	      26	  42022438 ns/op
BenchmarkStableExp/1M-6            	       2	 626086600 ns/op
BenchmarkStableStd/1K-6            	    2514	    489098 ns/op
BenchmarkStableStd/10K-6           	     141	   8142265 ns/op
BenchmarkStableStd/100K-6          	       8	 129273925 ns/op
BenchmarkStableStd/1M-6            	       1	1965630400 ns/op
BenchmarkPointerUno/1K-6           	   21015	     56851 ns/op
BenchmarkPointerUno/10K-6          	    1628	    743322 ns/op
BenchmarkPointerUno/100K-6         	     100	  10213240 ns/op
BenchmarkPointerUno/1M-6           	       5	 250836860 ns/op
BenchmarkPointerExp/1K-6           	   18240	     65947 ns/op
BenchmarkPointerExp/10K-6          	    1204	    884783 ns/op
BenchmarkPointerExp/100K-6         	     100	  12133220 ns/op
BenchmarkPointerExp/1M-6           	       4	 260696700 ns/op
BenchmarkPointerStd/1K-6           	   14588	     79407 ns/op
BenchmarkPointerStd/10K-6          	    1094	   1112762 ns/op
BenchmarkPointerStd/100K-6         	      84	  14619202 ns/op
BenchmarkPointerStd/1M-6           	       4	 305192700 ns/op

@PeterRK
Copy link

@PeterRK PeterRK commented Jan 28, 2022

little

@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.

See benchmark result on EPYC-7K83 machine.

name                 std time/op  exp time/op  delta
Struct/1K-8           135µs ± 1%   132µs ± 1%   -2.07%  (p=0.000 n=9+10)
Struct/10K-8         1.74ms ± 1%  1.77ms ± 0%   +1.98%  (p=0.000 n=9+10)
Struct/100K-8        21.3ms ± 1%  22.2ms ± 0%   +3.86%  (p=0.000 n=10+10)
Struct/1M-8           251ms ± 1%   265ms ± 1%   +5.47%  (p=0.000 n=10+10)
Pointer/1K-8         87.0µs ± 4%  72.8µs ± 1%  -16.33%  (p=0.000 n=10+10)
Pointer/10K-8        1.23ms ± 1%  1.05ms ± 1%  -14.53%  (p=0.000 n=9+10)
Pointer/100K-8       17.1ms ± 1%  14.5ms ± 0%  -14.70%  (p=0.000 n=10+9)
Pointer/1M-8          289ms ± 2%   244ms ± 1%  -15.66%  (p=0.000 n=10+10)

Performance benefit of reference compare fcunc is significant.

name                 exp time/op  uno time/op  delta
Struct/1K-8           132µs ± 1%    70µs ± 0%  -47.14%  (p=0.000 n=10+10)
Struct/10K-8         1.77ms ± 0%  1.11ms ± 0%  -37.57%  (p=0.000 n=10+10)
Struct/100K-8        22.2ms ± 0%  13.3ms ± 0%  -40.17%  (p=0.000 n=10+10)
Struct/1M-8           265ms ± 1%   153ms ± 0%  -42.23%  (p=0.000 n=10+9)
Pointer/1K-8         72.8µs ± 1%  62.1µs ± 1%  -14.60%  (p=0.000 n=10+8)
Pointer/10K-8        1.05ms ± 1%  0.90ms ± 0%  -14.11%  (p=0.000 n=10+10)
Pointer/100K-8       14.5ms ± 0%  12.5ms ± 0%  -14.06%  (p=0.000 n=9+10)
Pointer/1M-8          244ms ± 1%   225ms ± 3%   -7.93%  (p=0.000 n=10+10)

Pointer array will be sorted faster than struct array only when size is small engouth to cache.

gopherbot pushed a commit that referenced this issue Mar 3, 2022
The existing codegen strategy in sort.go relied on parsing the sort.go source
with go/ast and a combination of an AST rewrite + code text rewrite with regexes
to generate zfuncversion -- the same sort functionality with a different variant
of data.

In preparation for implementing #47619, we need a more robust codegen
strategy. To generate variants required for the generic sort functions
in the slices package, we'd need significanly more complicated AST
rewrites, which would make genzfunc.go much heavier.

Instead, redo the codegen strategy to use text/template instead of AST rewrites.
gen_sort_variants.go now contains the code for the underlying sort functions,
and generates multiple versions of them based on Variant configuration structs.
With this approach, adding new variants to generate generic sort functions for
the slices package becomes trivial.

See the discussion in #47619 for more details on the design decisions.

Change-Id: I8af784c41b1dc8ef92aaf6321359e8faa5fe106c
Reviewed-on: https://go-review.googlesource.com/c/go/+/353069
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Trust: Than McIntosh <thanm@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Proposals
Accepted
Development

No branches or pull requests