🌱 refactor SortForCreate to use sort.Slice

[kokes]

What this PR does / why we need it:

I found SortForCreate to be very inefficient, it's basically O(n^2), it also needlessly allocates. In order to keep the contract (even though this exported function is not widely used), I didn't change this function's behaviour (i.e. its purity), but I did deprecate it. (It could've been even faster if we opted for an in-place sort, but I didn't want to change the function's behaviour.)

The function doesn't appear to be used in any tight loops or with a large number of elements, so it's a low prio PR, but it's something that could bite people applying a large number of small resources (see how it falls off a cliff with 10k elements).

Benchmark comparison

name             old time/op    new time/op    delta
Sort/sort-10       10.0µs ±31%     3.7µs ±55%  -63.11%  (p=0.000 n=10+10)
Sort/sort-100       423µs ±10%      58µs ±28%  -86.35%  (p=0.000 n=10+10)
Sort/sort-1000     45.0ms ±13%     0.5ms ±12%  -98.83%  (p=0.000 n=10+9)
Sort/sort-10000     5.90s ±22%     0.01s ±30%  -99.86%  (p=0.000 n=10+10)

name             old alloc/op   new alloc/op   delta
Sort/sort-10         248B ± 0%      136B ± 0%  -45.16%  (p=0.000 n=10+10)
Sort/sort-100      2.04kB ± 0%    0.95kB ± 0%  -53.33%  (p=0.000 n=10+10)
Sort/sort-1000     25.2kB ± 0%     8.2kB ± 0%  -67.28%  (p=0.000 n=10+10)
Sort/sort-10000     358kB ± 0%      82kB ± 0%  -77.08%  (p=0.000 n=10+10)

name             old allocs/op  new allocs/op  delta
Sort/sort-10         5.00 ± 0%      3.00 ± 0%  -40.00%  (p=0.000 n=10+10)
Sort/sort-100        8.00 ± 0%      3.00 ± 0%  -62.50%  (p=0.000 n=10+10)
Sort/sort-1000       12.0 ± 0%       3.0 ± 0%  -75.00%  (p=0.000 n=10+10)
Sort/sort-10000      20.0 ± 0%       3.0 ± 0%  -85.00%  (p=0.000 n=10+10)

GH issue
Fixes #9253

/area util

[linux-foundation-easycla]

The committers listed above are authorized under a signed CLA.

• ✅ login: kokes / name: Ondrej Kokes (39d93e5)

[k8s-ci-robot]

Hi @kokes. Thanks for your PR.

I'm waiting for a kubernetes-sigs member to verify that this patch is reasonable to test. If it is, they should reply with /ok-to-test on its own line. Until that is done, I will not automatically test new commits in this PR, but the usual testing commands by org members will still work. Regular contributors should join the org to skip this step.

Once the patch is verified, the new status will be reflected by the ok-to-test label.

I understand the commands that are listed here.

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes/test-infra repository.

[k8s-ci-robot]

Welcome @kokes!

It looks like this is your first PR to kubernetes-sigs/cluster-api 🎉. Please refer to our pull request process documentation to help your PR have a smooth ride to approval.

You will be prompted by a bot to use commands during the review process. Do not be afraid to follow the prompts! It is okay to experiment. Here is the bot commands documentation.

You can also check if kubernetes-sigs/cluster-api has its own contribution guidelines.

You may want to refer to our testing guide if you run into trouble with your tests not passing.

If you are having difficulty getting your pull request seen, please follow the recommended escalation practices. Also, for tips and tricks in the contribution process you may want to read the Kubernetes contributor cheat sheet. We want to make sure your contribution gets all the attention it needs!

Thank you, and welcome to Kubernetes. 😃

[killianmuldoon]

/ok-to-test

[kokes]

I redid it a bit - I decided not to deprecate SortForOrder after all, because the sort.Slice usage is quite clunky (due to the closure that's required) and should only be used in a performance-critical scenario (and anyone can use it, should they need it). The new (allocating) implementation is good enough, so I'll leave it that way.

We could also:

1. Unexport PriorityLess to keep the API surface smaller.
2. Create a function to satisfy SortFunc, though that API so super new that it won't be leveraged until 1.21 is the oldest Go version supported, which is probably quite far away atm.

Neither is a priority tho.

[killianmuldoon]

/ok-to-test

[richardcase]

The behaviour of the SortForCreate stays the same. Interestingly, the original implementation doesn't match the comments and the tests don't cover the scenarios.

For example, the comments say that Pods go before Replicaset but if you extend the test to include pods, deployments, replicasets like this:

	cm := unstructured.Unstructured{}
	cm.SetKind("ConfigMap")

	ns := unstructured.Unstructured{}
	ns.SetKind("Namespace")

	ep := unstructured.Unstructured{}
	ep.SetKind("Endpoint")

	dp := unstructured.Unstructured{}
	dp.SetKind("Deployment")

	rs := unstructured.Unstructured{}
	rs.SetKind("ReplicaSet")

	pd := unstructured.Unstructured{}
	pd.SetKind("Pod")

	resources := []unstructured.Unstructured{ep, cm, ns, dp, rs, pd}

The replicaset is sorted before the pod. The issue is mainly that in the original implementation the slice should have contained Pod & Endpoint instead of Pods & Endpoints.

[richardcase]

@killianmuldoon @enxebre - do we care that the original behaviour doesn't match the comments in the code? I see we use it in the CRS and clusterctl (for cert-manager) code but i don't have any context on its original inclusion.

(If we do care i'd say its out of scope for this PR though)

[killianmuldoon]

@killianmuldoon @enxebre - do we care that the original behaviour doesn't match the comments in the code? I see we use it in the CRS and clusterctl (for cert-manager) code but i don't have any context on its original inclusion.

IMO it's clear the current behaviour is a bug which could actually cause issues in e.g. a ClusterResourceSet. Fine with properly fixing that here so long as we update the tests to cover the full behavior of the sort.

[killianmuldoon]

Looks good - just a couple of asks for the tests.

Could you update the test to add all of the types listed in resources, and a couple that aren't e.g. `Deployment'. It would also be good to define them in a map and convert that to an input sice to ensure we get multiple permutations in the test.

[kokes]

I've pushed two commits, where I:

• unexported PriorityLess since we don't use it anywhere othere than this package
• removed the benchmark since we don't run benchmarks in this projects apparently
• fixed the plural of Pods and Endpoints
• reworked the existing test to include elements with no priority to check they are assigned least priority
• added a new, more comprehensive test, where I add all sorts of resources, repeatedly shuffle and check that sorting these always results in all the kinds with priorities frontloaded and the rest of resources with no particular order

[killianmuldoon]

Looks great! Thanks for the testing improvements.

Could you squash the commits?

[kokes]

Done

[killianmuldoon]

/lgtm

Thanks for this!

[k8s-ci-robot]

LGTM label has been added.

Git tree hash: ad8b2f469df1126c134f06745627bd4753e561c9

[richardcase]

/lgtm

[killianmuldoon]

Thanks again!

/approve

[k8s-ci-robot]

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: killianmuldoon

The full list of commands accepted by this bot can be found here.

The pull request process is described here

Needs approval from an approver in each of these files:

• OWNERS [killianmuldoon]

Approvers can indicate their approval by writing /approve in a comment
Approvers can cancel approval by writing /approve cancel in a comment