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.

Sign up for GitHub

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

Jump to bottom

sort: forward fixed-type slice sorting to slices package #61180

Closed
eliben opened this issue Jul 5, 2023 · 5 comments
Closed

sort: forward fixed-type slice sorting to slices package #61180

eliben opened this issue Jul 5, 2023 · 5 comments
Assignees
@eliben
Labels
NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone
Go1.22

Comments

@eliben
Copy link
Member

eliben commented Jul 5, 2023 •
edited by gabyhelp
Loading

The sorting functions in the slices package are generally faster than their equivalents in the sort package. We've added doc comments to the sort package in 1.21 pointing at the faster equivalents, but for now did not modify their implementation. Issues like #60777 show that there could be some rare scenarios where a change would introduce a regression.

In 1.22 we should consider forwarding the implementation of functions like sort.Ints to slices.Sort:

func Ints(x []int) {
  slices.Sort(x)
}

The following functions can be forwarded:

  • sort.Ints
  • sort.Strings
  • sort.Float64s (but we'll need to double check that the FP semantics align, e.g. NaN)
  • sort.IntsAreSorted
  • sort.StringsAreSorted
  • sort.Float64sAreSorted

The other functions in the sort package have slightly different semantics, so it may just be sufficient to retain comments suggesting to consider the slices package instead.
@eliben eliben added this to the Go1.22 milestone Jul 5, 2023
@eliben eliben self-assigned this Jul 5, 2023
@rsc
Copy link
Contributor

rsc commented Jul 5, 2023

sort.Float64s can call slices.Sort. We defined cmp.Compare the way we did specifically so that the two would match.

@bcmills bcmills added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Jul 5, 2023
@rsc rsc changed the title sort: consider forwarding some sort package functions to slices package functions sort: forward slice sorting to slices package Jul 5, 2023
@rsc rsc changed the title sort: forward slice sorting to slices package sort: forward fixed-type slice sorting to slices package Jul 5, 2023
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/508135 mentions this issue: sort: forward fixed-type slice sorting to slices package

@eliben
Copy link
Member Author

eliben commented Jul 7, 2023

The attached CL is running into a bootstrapping issue, since the sort package is used in the Go compiler. Our current bootstrap version is 1.17 which doesn't even support generics. slices only makes it into the stdlib in 1.21, and the CL is making sort depend on slices.

According to #54265 we plan to bump the bootstrap version to 1.20 in the 1.22 time frame.

@eliben
Copy link
Member Author

eliben commented Jul 12, 2023

https://go.dev/cl/508135 was updated to work around the bootstrapping issue by using build constraints, per suggestions from @ianlancetaylor and @neild

AlexanderYastrebov added a commit to zalando/skipper that referenced this issue Sep 5, 2023
@AlexanderYastrebov
eskip: sort built-in predicates
bd9d522 
PRs #2202 and #2208 added SortPredicates flag to PrettyPrintInfo
and -sort-predicates flag to eskip tool which enables sorting
of built-in and regular predicates.

Several built-in predicates represented as maps internally therefore
sorting is necessary to obtain stable eskip serialization of a route.

This was planned to be used in routesrv which serves routes in eskip
format and supports HTTP caching via ETag.

Regular predicates are evaluated in ordered and short-circuit manner
which makes it possible to put "cheap" predicates before "expensive".
Sorting regular predicates therefore breaks short-circuit evaluation.

With the above in mind it makes sense to sort built-in predicates
unconditionally and leave regular predicates intact.

This change:

* sorts built-in predicates unconditionally in-place using string representation to reduce allocations
* does not sort regular predicates
* removes SortPredicates flag from PrettyPrintInfo
* removes -sort-predicates from eskip

Benchmark results to demonstrate the cost of sorting:
```
goos: linux
goarch: amd64
pkg: github.com/zalando/skipper/eskip
cpu: Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz
              │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new    │
              │            sec/op             │   sec/op     vs base               │
RouteString-8                     11.69µ ± 2%   12.49µ ± 1%  +6.83% (p=0.000 n=10)

              │ /tmp/BenchmarkRouteString.old │    /tmp/BenchmarkRouteString.new    │
              │             B/op              │     B/op      vs base               │
RouteString-8                    1.789Ki ± 0%   1.883Ki ± 0%  +5.24% (p=0.000 n=10)

              │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new   │
              │           allocs/op           │ allocs/op   vs base               │
RouteString-8                      63.00 ± 0%   67.00 ± 0%  +6.35% (p=0.000 n=10)
```
Extra allocations should go away in the future thanks to golang/go#61180

Followup on #2208

Signed-off-by: Alexander Yastrebov <[email protected]>
AlexanderYastrebov added a commit to zalando/skipper that referenced this issue Sep 5, 2023
@AlexanderYastrebov
eskip: sort built-in predicates
3507120 
PRs #2202 and #2208 added SortPredicates flag to PrettyPrintInfo
and -sort-predicates flag to eskip tool which enables sorting
of built-in and regular predicates.

Several built-in predicates represented as maps internally therefore
sorting is necessary to obtain stable eskip serialization of a route.

This was planned to be used in routesrv which serves routes in eskip
format and supports HTTP caching via ETag.

Regular predicates are evaluated in ordered and short-circuit manner
which makes it possible to put "cheap" predicates before "expensive".
Sorting regular predicates therefore breaks short-circuit evaluation.

With the above in mind it makes sense to sort built-in predicates
unconditionally and leave regular predicates intact.

This change:

* sorts built-in predicates unconditionally in-place using string representation to reduce allocations
* does not sort regular predicates
* removes SortPredicates flag from PrettyPrintInfo
* removes -sort-predicates from eskip

Benchmark results to demonstrate the cost of sorting:
```
goos: linux
goarch: amd64
pkg: github.com/zalando/skipper/eskip
cpu: Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz
              │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new    │
              │            sec/op             │   sec/op     vs base               │
RouteString-8                     11.69µ ± 2%   12.49µ ± 1%  +6.83% (p=0.000 n=10)

              │ /tmp/BenchmarkRouteString.old │    /tmp/BenchmarkRouteString.new    │
              │             B/op              │     B/op      vs base               │
RouteString-8                    1.789Ki ± 0%   1.883Ki ± 0%  +5.24% (p=0.000 n=10)

              │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new   │
              │           allocs/op           │ allocs/op   vs base               │
RouteString-8                      63.00 ± 0%   67.00 ± 0%  +6.35% (p=0.000 n=10)
```
Extra allocations should go away in the future thanks to golang/go#61180

Followup on #2208
Updates #2519

Signed-off-by: Alexander Yastrebov <[email protected]>
@AlexanderYastrebov AlexanderYastrebov mentioned this issue Sep 5, 2023
Merged
AlexanderYastrebov added a commit to zalando/skipper that referenced this issue Sep 5, 2023
@AlexanderYastrebov
eskip: sort built-in predicates
988636d 
PRs #2202 and #2208 added SortPredicates flag to PrettyPrintInfo
and -sort-predicates flag to eskip tool which enables sorting
of built-in and regular predicates.

Several built-in predicates represented as maps internally therefore
sorting is necessary to obtain stable eskip serialization of a route.

This was planned to be used in routesrv which serves routes in eskip
format and supports HTTP caching via ETag.

Regular predicates are evaluated in ordered and short-circuit manner
which makes it possible to put "cheap" predicates before "expensive".
Sorting regular predicates therefore breaks short-circuit evaluation.

With the above in mind it makes sense to sort built-in predicates
unconditionally and leave regular predicates intact.

This change:

* sorts built-in predicates unconditionally in-place using string representation to reduce allocations
* does not sort regular predicates
* removes SortPredicates flag from PrettyPrintInfo
* removes -sort-predicates from eskip

Benchmark results to demonstrate the cost of sorting:
```
goos: linux
goarch: amd64
pkg: github.com/zalando/skipper/eskip
cpu: Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz
                                  │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new    │
                                  │            sec/op             │   sec/op     vs base               │
RouteString-8                                         13.67µ ± 1%   14.43µ ± 1%  +5.52% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                     7.086µ ± 1%   7.092µ ± 1%       ~ (p=0.424 n=10)
geomean                                               9.843µ        10.11µ       +2.77%

                                  │ /tmp/BenchmarkRouteString.old │     /tmp/BenchmarkRouteString.new     │
                                  │             B/op              │     B/op      vs base                 │
RouteString-8                                        2.430Ki ± 0%   2.523Ki ± 0%  +3.86% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                    1.211Ki ± 0%   1.211Ki ± 0%       ~ (p=1.000 n=10) ¹
geomean                                              1.715Ki        1.748Ki       +1.91%
¹ all samples are equal

                                  │ /tmp/BenchmarkRouteString.old │    /tmp/BenchmarkRouteString.new    │
                                  │           allocs/op           │ allocs/op   vs base                 │
RouteString-8                                          94.00 ± 0%   98.00 ± 0%  +4.26% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                      53.00 ± 0%   53.00 ± 0%       ~ (p=1.000 n=10) ¹
geomean                                                70.58        72.07       +2.11%
¹ all samples are equal
```

Extra allocations should go away in the future thanks to golang/go#61180

Followup on #2208
Updates #2519

Signed-off-by: Alexander Yastrebov <[email protected]>
AlexanderYastrebov added a commit to zalando/skipper that referenced this issue Sep 5, 2023
@AlexanderYastrebov
eskip: sort built-in predicates
e8d6c31 
PRs #2202 and #2208 added SortPredicates flag to PrettyPrintInfo
and -sort-predicates flag to eskip tool which enables sorting
of built-in and regular predicates.

Header and HeaderRegexp built-in predicates are represented as maps
internally therefore sorting is necessary to obtain stable
eskip serialization of a route.

This was planned to be used in routesrv which serves routes in eskip
format and supports HTTP caching via ETag.

Regular predicates are evaluated in ordered and short-circuit manner
which makes it possible to put "cheap" predicates before "expensive".
Sorting regular predicates therefore breaks short-circuit evaluation.

With the above in mind it makes sense to sort built-in Header and
HeaderRegexp predicates unconditionally and leave regular predicates intact.

This change:

* sorts built-in Header and HeaderRegexp predicates unconditionally in-place
  using string representation to reduce allocations
* does not sort regular predicates
* removes SortPredicates flag from PrettyPrintInfo
* removes -sort-predicates from eskip

Benchmark results to demonstrate the cost of sorting:
```
goos: linux
goarch: amd64
pkg: github.com/zalando/skipper/eskip
cpu: Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz
                                  │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new    │
                                  │            sec/op             │   sec/op     vs base               │
RouteString-8                                         13.70µ ± 2%   14.07µ ± 2%  +2.74% (p=0.009 n=10)
RouteStringNoRepeatedPredicates-8                     7.083µ ± 3%   7.102µ ± 1%       ~ (p=0.079 n=10)
geomean                                               9.850µ        9.997µ       +1.50%

                                  │ /tmp/BenchmarkRouteString.old │     /tmp/BenchmarkRouteString.new     │
                                  │             B/op              │     B/op      vs base                 │
RouteString-8                                        2.430Ki ± 0%   2.477Ki ± 0%  +1.93% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                    1.211Ki ± 0%   1.211Ki ± 0%       ~ (p=1.000 n=10) ¹
geomean                                              1.715Ki        1.732Ki       +0.96%
¹ all samples are equal

                                  │ /tmp/BenchmarkRouteString.old │    /tmp/BenchmarkRouteString.new    │
                                  │           allocs/op           │ allocs/op   vs base                 │
RouteString-8                                          94.00 ± 0%   96.00 ± 0%  +2.13% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                      53.00 ± 0%   53.00 ± 0%       ~ (p=1.000 n=10) ¹
geomean                                                70.58        71.33       +1.06%
¹ all samples are equal
```

Note that sorting only happens when there are several Header or HeaderRegexp predicates in the route.
Extra allocations should go away in the future thanks to golang/go#61180

Followup on #2208
Updates #2519

Signed-off-by: Alexander Yastrebov <[email protected]>
AlexanderYastrebov added a commit to zalando/skipper that referenced this issue Sep 6, 2023
@AlexanderYastrebov
eskip: sort built-in predicates (#2576)
15513a5 
PRs #2202 and #2208 added SortPredicates flag to PrettyPrintInfo
and -sort-predicates flag to eskip tool which enables sorting
of built-in and regular predicates.

Header and HeaderRegexp built-in predicates are represented as maps
internally therefore sorting is necessary to obtain stable
eskip serialization of a route.

This was planned to be used in routesrv which serves routes in eskip
format and supports HTTP caching via ETag.

Regular predicates are evaluated in ordered and short-circuit manner
which makes it possible to put "cheap" predicates before "expensive".
Sorting regular predicates therefore breaks short-circuit evaluation.

With the above in mind it makes sense to sort built-in Header and
HeaderRegexp predicates unconditionally and leave regular predicates intact.

This change:

* sorts built-in Header and HeaderRegexp predicates unconditionally in-place
  using string representation to reduce allocations
* does not sort regular predicates
* removes SortPredicates flag from PrettyPrintInfo
* removes -sort-predicates from eskip

Benchmark results to demonstrate the cost of sorting:
```
goos: linux
goarch: amd64
pkg: github.com/zalando/skipper/eskip
cpu: Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz
                                  │ /tmp/BenchmarkRouteString.old │   /tmp/BenchmarkRouteString.new    │
                                  │            sec/op             │   sec/op     vs base               │
RouteString-8                                         13.70µ ± 2%   14.07µ ± 2%  +2.74% (p=0.009 n=10)
RouteStringNoRepeatedPredicates-8                     7.083µ ± 3%   7.102µ ± 1%       ~ (p=0.079 n=10)
geomean                                               9.850µ        9.997µ       +1.50%

                                  │ /tmp/BenchmarkRouteString.old │     /tmp/BenchmarkRouteString.new     │
                                  │             B/op              │     B/op      vs base                 │
RouteString-8                                        2.430Ki ± 0%   2.477Ki ± 0%  +1.93% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                    1.211Ki ± 0%   1.211Ki ± 0%       ~ (p=1.000 n=10) ¹
geomean                                              1.715Ki        1.732Ki       +0.96%
¹ all samples are equal

                                  │ /tmp/BenchmarkRouteString.old │    /tmp/BenchmarkRouteString.new    │
                                  │           allocs/op           │ allocs/op   vs base                 │
RouteString-8                                          94.00 ± 0%   96.00 ± 0%  +2.13% (p=0.000 n=10)
RouteStringNoRepeatedPredicates-8                      53.00 ± 0%   53.00 ± 0%       ~ (p=1.000 n=10) ¹
geomean                                                70.58        71.33       +1.06%
¹ all samples are equal
```

Note that sorting only happens when there are several Header or HeaderRegexp predicates in the route.
Extra allocations should go away in the future thanks to golang/go#61180

Followup on #2208
Updates #2519

Signed-off-by: Alexander Yastrebov <[email protected]>

---------

Signed-off-by: Alexander Yastrebov <[email protected]>
@dmitshur dmitshur added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Nov 13, 2023
gopherbot pushed a commit that referenced this issue Aug 21, 2024
@tklauser @gopherbot
sort: drop implementation for Go <1.21
b5ee80a 
Now that Go 1.22.6 is the minimum bootstrap toolchain (cf. CL 606156),
the fallback implementation for Go versions <1.21 can be dropped.

For #61180
For #64751

Change-Id: Idfeca0a6e9f490e1ab0f308ead372612402923ea
Reviewed-on: https://go-review.googlesource.com/c/go/+/607315
Reviewed-by: Dmitri Shuralyov <[email protected]>
LUCI-TryBot-Result: Go LUCI <[email protected]>
Reviewed-by: Ian Lance Taylor <[email protected]>
Commit-Queue: Tobias Klauser <[email protected]>
Reviewed-by: Dmitri Shuralyov <[email protected]>
Auto-Submit: Tobias Klauser <[email protected]>
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/607315 mentions this issue: sort: drop implementation for Go <1.21

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@eliben eliben

Labels
NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Milestone
Go1.22
Development

No branches or pull requests
5 participants
@rsc @eliben @dmitshur @bcmills @gopherbot