Skip to content

Optimize sets.Set #133231

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
Open
wants to merge 7 commits into
base: master
Choose a base branch
from
Open

Optimize sets.Set #133231

wants to merge 7 commits into from

Conversation

ash2k
Copy link
Member

@ash2k ash2k commented Jul 26, 2025

What type of PR is this?

/kind cleanup

What this PR does / why we need it:

Optimize set operations and usage. Please see individual commits.

Which issue(s) this PR is related to:

Special notes for your reviewer:

Does this PR introduce a user-facing change?

NONE

Additional documentation e.g., KEPs (Kubernetes Enhancement Proposals), usage docs, etc.:

/sig api-machinery

@k8s-ci-robot k8s-ci-robot added release-note-none Denotes a PR that doesn't merit a release note. kind/cleanup Categorizes issue or PR as related to cleaning up code, process, or technical debt. size/L Denotes a PR that changes 100-499 lines, ignoring generated files. sig/api-machinery Categorizes an issue or PR as relevant to SIG API Machinery. needs-triage Indicates an issue or PR lacks a `triage/foo` label and requires one. needs-priority Indicates a PR lacks a `priority/foo` label and requires one. cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. area/code-generation area/ipvs area/kube-proxy area/kubectl area/kubelet area/test sig/apps Categorizes an issue or PR as relevant to SIG Apps. sig/autoscaling Categorizes an issue or PR as relevant to SIG Autoscaling. labels Jul 26, 2025
@k8s-ci-robot k8s-ci-robot added sig/cli Categorizes an issue or PR as relevant to SIG CLI. sig/network Categorizes an issue or PR as relevant to SIG Network. labels Jul 26, 2025
@github-project-automation github-project-automation bot moved this to Needs Triage in SIG Apps Jul 26, 2025
@k8s-ci-robot k8s-ci-robot added the sig/node Categorizes an issue or PR as relevant to SIG Node. label Jul 26, 2025
@k8s-ci-robot k8s-ci-robot requested review from aojea and bart0sh July 26, 2025 04:40
@k8s-ci-robot k8s-ci-robot added sig/storage Categorizes an issue or PR as relevant to SIG Storage. sig/testing Categorizes an issue or PR as relevant to SIG Testing. labels Jul 26, 2025
@github-project-automation github-project-automation bot moved this to Needs Triage in SIG CLI Jul 26, 2025
@ash2k
Copy link
Member Author

ash2k commented Jul 30, 2025

Just pushed a commit with a benchmark. Here is an excerpt with the relevant output:

goos: darwin
goarch: arm64
pkg: k8s.io/apimachinery/pkg/util/sets
cpu: Apple M4 Max

BenchmarkStringSet/difference-20
BenchmarkStringSet/difference-20-16                   	  882244	      1335 ns/op	    1636 B/op	       6 allocs/op
BenchmarkStringSet/difference-seq-20
BenchmarkStringSet/difference-seq-20-16               	 2687314	       444.2 ns/op	      56 B/op	       3 allocs/op
BenchmarkStringSet/difference-50
BenchmarkStringSet/difference-50-16                   	  363456	      3267 ns/op	    3457 B/op	       8 allocs/op
BenchmarkStringSet/difference-seq-50
BenchmarkStringSet/difference-seq-50-16               	 1000000	      1164 ns/op	      56 B/op	       3 allocs/op
BenchmarkStringSet/difference-100
BenchmarkStringSet/difference-100-16                  	  190008	      6237 ns/op	    6938 B/op	      10 allocs/op
BenchmarkStringSet/difference-seq-100
BenchmarkStringSet/difference-seq-100-16              	  500174	      2382 ns/op	      56 B/op	       3 allocs/op
BenchmarkStringSet/difference-500
BenchmarkStringSet/difference-500-16                  	   30966	     38250 ns/op	   54276 B/op	      16 allocs/op
BenchmarkStringSet/difference-seq-500
BenchmarkStringSet/difference-seq-500-16              	  118758	      9658 ns/op	      56 B/op	       3 allocs/op
BenchmarkStringSet/difference-1000
BenchmarkStringSet/difference-1000-16                 	   14876	     80534 ns/op	  108803 B/op	      21 allocs/op
BenchmarkStringSet/difference-seq-1000
BenchmarkStringSet/difference-seq-1000-16             	   50556	     23123 ns/op	      56 B/op	       3 allocs/op

@ash2k
Copy link
Member Author

ash2k commented Jul 30, 2025

/retest

@BenTheElder
Copy link
Member

thanks -- do we have before/after?

this diff also exposes more APIs, some of which seem to be missing tests.

@ash2k
Copy link
Member Author

ash2k commented Jul 30, 2025 •
edited
Loading

thanks -- do we have before/after?

I've added the same test to master and ran it:

goos: darwin
goarch: arm64
pkg: k8s.io/apimachinery/pkg/util/sets
cpu: Apple M4 Max
BenchmarkStringSet
BenchmarkStringSet/difference-20
BenchmarkStringSet/difference-20-16         	  800041	      1353 ns/op	    1636 B/op	       6 allocs/op
BenchmarkStringSet/difference-50
BenchmarkStringSet/difference-50-16         	  354494	      3314 ns/op	    3457 B/op	       8 allocs/op
BenchmarkStringSet/difference-100
BenchmarkStringSet/difference-100-16        	  183486	      6295 ns/op	    6938 B/op	      10 allocs/op
BenchmarkStringSet/difference-500
BenchmarkStringSet/difference-500-16        	   29953	     39356 ns/op	   54291 B/op	      16 allocs/op
BenchmarkStringSet/difference-1000
BenchmarkStringSet/difference-1000-16       	   14665	     81578 ns/op	  108807 B/op	      21 allocs/op

this diff also exposes more APIs, some of which seem to be missing tests.

  • I've added a test for pre-existing Clone()
  • DifferenceSeq() is covered by tests for Difference() as the former is used by the later.
  • I've added a test for InsertSet().

@ash2k
Copy link
Member Author

ash2k commented Jul 30, 2025 •
edited
Loading

To make it easier to see, I've combined the above results below:

this PR:

BenchmarkStringSet/difference-20
BenchmarkStringSet/difference-20-16                   	  882244	      1335 ns/op	    1636 B/op	       6 allocs/op
BenchmarkStringSet/difference-50
BenchmarkStringSet/difference-50-16                   	  363456	      3267 ns/op	    3457 B/op	       8 allocs/op
BenchmarkStringSet/difference-100
BenchmarkStringSet/difference-100-16                  	  190008	      6237 ns/op	    6938 B/op	      10 allocs/op
BenchmarkStringSet/difference-500
BenchmarkStringSet/difference-500-16                  	   30966	     38250 ns/op	   54276 B/op	      16 allocs/op
BenchmarkStringSet/difference-1000
BenchmarkStringSet/difference-1000-16                 	   14876	     80534 ns/op	  108803 B/op	      21 allocs/op


master:

BenchmarkStringSet/difference-20
BenchmarkStringSet/difference-20-16         	  800041	      1353 ns/op	    1636 B/op	       6 allocs/op
BenchmarkStringSet/difference-50
BenchmarkStringSet/difference-50-16         	  354494	      3314 ns/op	    3457 B/op	       8 allocs/op
BenchmarkStringSet/difference-100
BenchmarkStringSet/difference-100-16        	  183486	      6295 ns/op	    6938 B/op	      10 allocs/op
BenchmarkStringSet/difference-500
BenchmarkStringSet/difference-500-16        	   29953	     39356 ns/op	   54291 B/op	      16 allocs/op
BenchmarkStringSet/difference-1000
BenchmarkStringSet/difference-1000-16       	   14665	     81578 ns/op	  108807 B/op	      21 allocs/op

@ash2k
Copy link
Member Author

ash2k commented Jul 30, 2025

/retest

@SergeyKanzhelev SergeyKanzhelev moved this from Triage to Archive-it in SIG Node CI/Test Board Jul 30, 2025
@ash2k
Copy link
Member Author

ash2k commented Aug 5, 2025

/retest

@ash2k ash2k changed the title Optimize set Optimize sets.Set Aug 5, 2025
@ash2k
Copy link
Member Author

ash2k commented Aug 5, 2025

/retest

@BenTheElder
Copy link
Member

/cc @thockin

@k8s-ci-robot k8s-ci-robot requested a review from thockin August 5, 2025 19:46
@seans3
Copy link
Contributor

seans3 commented Aug 5, 2025

/triage accepted

@k8s-ci-robot k8s-ci-robot added triage/accepted Indicates an issue or PR is ready to be actively worked on. and removed needs-triage Indicates an issue or PR lacks a `triage/foo` label and requires one. labels Aug 5, 2025
@ash2k ash2k force-pushed the optimize-set branch 2 times, most recently from 662f298 to 84ae77f Compare August 8, 2025 09:12
@k8s-ci-robot
Copy link
Contributor

@ash2k: The following tests failed, say /retest to rerun all failed tests or /retest-required to rerun all mandatory failed tests:

Test name Commit Details Required Rerun command
pull-kubernetes-dra-integration d56b9f1 link false /test pull-kubernetes-dra-integration
pull-kubernetes-kind-dra-n-1 d56b9f1 link false /test pull-kubernetes-kind-dra-n-1
pull-kubernetes-unit-windows-master d56b9f1 link false /test pull-kubernetes-unit-windows-master
pull-kubernetes-kind-dra-all d56b9f1 link false /test pull-kubernetes-kind-dra-all

Full PR test history. Your PR dashboard. Please help us cut down on flakes by linking to an open issue when you hit one in your PR.

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-sigs/prow repository. I understand the commands that are listed here.

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

@adrianmoisey adrianmoisey adrianmoisey left review comments

@aojea aojea Awaiting requested review from aojea

@bart0sh bart0sh Awaiting requested review from bart0sh

@thockin thockin Awaiting requested review from thockin

Assignees
No one assigned
Labels
area/code-generation area/ipvs area/kube-proxy area/kubectl area/kubelet area/test cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. kind/cleanup Categorizes issue or PR as related to cleaning up code, process, or technical debt. needs-priority Indicates a PR lacks a `priority/foo` label and requires one. release-note-none Denotes a PR that doesn't merit a release note. sig/api-machinery Categorizes an issue or PR as relevant to SIG API Machinery. sig/apps Categorizes an issue or PR as relevant to SIG Apps. sig/autoscaling Categorizes an issue or PR as relevant to SIG Autoscaling. sig/cli Categorizes an issue or PR as relevant to SIG CLI. sig/network Categorizes an issue or PR as relevant to SIG Network. sig/node Categorizes an issue or PR as relevant to SIG Node. sig/storage Categorizes an issue or PR as relevant to SIG Storage. sig/testing Categorizes an issue or PR as relevant to SIG Testing. size/L Denotes a PR that changes 100-499 lines, ignoring generated files. triage/accepted Indicates an issue or PR is ready to be actively worked on. wg/device-management Categorizes an issue or PR as relevant to WG Device Management.
Projects
Dynamic Resource Allocation
Status: 🆕 New
SIG Apps
Status: Needs Triage
SIG CLI
Status: Needs Triage
SIG Node CI/Test Board
Status: Archive-it
SIG Node: code and documentation PRs
Status: Triage
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
5 participants
@ash2k @k8s-ci-robot @BenTheElder @seans3 @adrianmoisey