Improve DeltaFIFO function 'ListKeys' #104725

NoicFank · 2021-09-02T06:06:18Z

What type of PR is this?

/kind cleanup

What this PR does / why we need it:

In function ListKeys, it better to use ‘queue’ instead of 'items' to get all the keys.

Here is the reasons:

More efficient. After testing locally, it's nearly 5-10 times faster than using 'items', while the number of items in 'queue'/'items' is 10000 and the average time is obtained by 10000 repetitions in each testing. Since the type of 'items' is map, and the type of 'queue' is slice.
More reasonable. Although the keys are one-to-one correspondence in queue and items, it is more reasonable to get keys from the 'queue', since keys are queued in the 'queue' for processing by HandleDeltas, which reflects the idea of FIFO, and 'items' is considered as a kind of storage. Therefore, getting the keys from the 'queue' is more intuitive and easy to understand.
Ordered results. Golang maps is a collection of unordered pairs of key-value, thus the traversed key set from 'items' cannot reflect the queuing order of objects, but using 'queue' can provide this information.

Which issue(s) this PR fixes:

Fixes #

Special notes for your reviewer:

benchmark results with DelfaFIFO:

current impl

$ go test -test.bench DeltaFIFOListKeys -test.run DeltaFIFOListKeys -count=10
goos: darwin
goarch: amd64
pkg: k8s.io/client-go/tools/cache
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkDeltaFIFOListKeys-12              77949             14921 ns/op
BenchmarkDeltaFIFOListKeys-12              82304             15016 ns/op
BenchmarkDeltaFIFOListKeys-12              82227             14624 ns/op
BenchmarkDeltaFIFOListKeys-12              80166             14884 ns/op
BenchmarkDeltaFIFOListKeys-12              83228             14847 ns/op
BenchmarkDeltaFIFOListKeys-12              80178             15167 ns/op
BenchmarkDeltaFIFOListKeys-12              80023             14952 ns/op
BenchmarkDeltaFIFOListKeys-12              78912             15647 ns/op
BenchmarkDeltaFIFOListKeys-12              73502             16353 ns/op
BenchmarkDeltaFIFOListKeys-12              73690             16669 ns/op
PASS
ok      k8s.io/client-go/tools/cache    14.151s

pull request impl

$ go test -test.bench DeltaFIFOListKeys -test.run DeltaFIFOListKeys -count=10
goos: darwin
goarch: amd64
pkg: k8s.io/client-go/tools/cache
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkDeltaFIFOListKeys-12             161652              7621 ns/op
BenchmarkDeltaFIFOListKeys-12             156442              7468 ns/op
BenchmarkDeltaFIFOListKeys-12             158258              7577 ns/op
BenchmarkDeltaFIFOListKeys-12             159350              7639 ns/op
BenchmarkDeltaFIFOListKeys-12             156450              8074 ns/op
BenchmarkDeltaFIFOListKeys-12             160190              7664 ns/op
BenchmarkDeltaFIFOListKeys-12             159818              7426 ns/op
BenchmarkDeltaFIFOListKeys-12             156006              7522 ns/op
BenchmarkDeltaFIFOListKeys-12             169120              7368 ns/op
BenchmarkDeltaFIFOListKeys-12             151201              7358 ns/op
PASS
ok      k8s.io/client-go/tools/cache    13.005s

Does this PR introduce a user-facing change?

NONE

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

k8s-ci-robot · 2021-09-02T06:06:25Z

Welcome @NoicFank!

It looks like this is your first PR to kubernetes/kubernetes 🎉. 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/kubernetes 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. 😃

k8s-ci-robot · 2021-09-02T06:06:26Z

Hi @NoicFank. Thanks for your PR.

I'm waiting for a kubernetes 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.

sxllwx · 2021-09-02T06:37:27Z

staging/src/k8s.io/client-go/tools/cache/delta_fifo.go

-	list := make([]string, 0, len(f.items))
-	for key := range f.items {
+	list := make([]string, 0, len(f.queue))
+	for _, key := range f.queue {
 		list = append(list, key)


Maybe we can use copy func to complete this work.

The time consumption between using copy func and current method are nearly same.

NoicFank · 2021-09-02T07:23:45Z

benchmark

 archelurong@ARCHELURONG-MB0  ~/go/src/test1  go run main.go 10000
Average time per 10000 times
using queue: 83.75µs
using items: 1128.9µs
Improving:  13.479402985074627
 archelurong@ARCHELURONG-MB0  ~/go/src/test1  go run main.go 10000
Average time per 10000 times
using queue: 88.09µs
using items: 1103.31µs
Improving:  12.524804177545692
 archelurong@ARCHELURONG-MB0  ~/go/src/test1  go run main.go 10000
Average time per 10000 times
using queue: 85.78µs
using items: 1145.68µs
Improving:  13.356027045931453
 archelurong@ARCHELURONG-MB0  ~/go/src/test1 

NoicFank · 2021-09-02T08:24:18Z

official benchmark

current impl

$ go test -test.bench DeltaFIFOListKeys -test.run DeltaFIFOListKeys -count=10
goos: darwin
goarch: amd64
pkg: k8s.io/client-go/tools/cache
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkDeltaFIFOListKeys-12              77949             14921 ns/op
BenchmarkDeltaFIFOListKeys-12              82304             15016 ns/op
BenchmarkDeltaFIFOListKeys-12              82227             14624 ns/op
BenchmarkDeltaFIFOListKeys-12              80166             14884 ns/op
BenchmarkDeltaFIFOListKeys-12              83228             14847 ns/op
BenchmarkDeltaFIFOListKeys-12              80178             15167 ns/op
BenchmarkDeltaFIFOListKeys-12              80023             14952 ns/op
BenchmarkDeltaFIFOListKeys-12              78912             15647 ns/op
BenchmarkDeltaFIFOListKeys-12              73502             16353 ns/op
BenchmarkDeltaFIFOListKeys-12              73690             16669 ns/op
PASS
ok      k8s.io/client-go/tools/cache    14.151s

pull request impl

$ go test -test.bench DeltaFIFOListKeys -test.run DeltaFIFOListKeys -count=10
goos: darwin
goarch: amd64
pkg: k8s.io/client-go/tools/cache
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkDeltaFIFOListKeys-12             161652              7621 ns/op
BenchmarkDeltaFIFOListKeys-12             156442              7468 ns/op
BenchmarkDeltaFIFOListKeys-12             158258              7577 ns/op
BenchmarkDeltaFIFOListKeys-12             159350              7639 ns/op
BenchmarkDeltaFIFOListKeys-12             156450              8074 ns/op
BenchmarkDeltaFIFOListKeys-12             160190              7664 ns/op
BenchmarkDeltaFIFOListKeys-12             159818              7426 ns/op
BenchmarkDeltaFIFOListKeys-12             156006              7522 ns/op
BenchmarkDeltaFIFOListKeys-12             169120              7368 ns/op
BenchmarkDeltaFIFOListKeys-12             151201              7358 ns/op
PASS
ok      k8s.io/client-go/tools/cache    13.005s

k8s-ci-robot · 2021-09-02T09:15:59Z

Thanks for your pull request. Before we can look at your pull request, you'll need to sign a Contributor License Agreement (CLA).

📝 Please follow instructions at https://git.k8s.io/community/CLA.md#the-contributor-license-agreement to sign the CLA.

It may take a couple minutes for the CLA signature to be fully registered; after that, please reply here with a new comment and we'll verify. Thanks.

If you've already signed a CLA, it's possible we don't have your GitHub username or you're using a different email address. Check your existing CLA data and verify that your email is set on your git commits.
If you signed the CLA as a corporation, please sign in with your organization's credentials at https://identity.linuxfoundation.org/projects/cncf to be authorized.
If you have done the above and are still having issues with the CLA being reported as unsigned, please log a ticket with the Linux Foundation Helpdesk: https://support.linuxfoundation.org/
Should you encounter any issues with the Linux Foundation Helpdesk, send a message to the backup e-mail support address at: login-issues@jira.linuxfoundation.org

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

fedebongio · 2021-09-02T20:10:38Z

/assign @deads2k
David, we thought you might be interested in this one. Thanks
/triage accepted

pacoxu · 2021-09-03T03:47:20Z

/kind cleanup
/ok-to-test

staging/src/k8s.io/client-go/tools/cache/delta_fifo.go

wojtek-t · 2021-09-03T06:34:33Z

staging/src/k8s.io/client-go/tools/cache/fifo.go

@@ -235,8 +235,8 @@ func (f *FIFO) List() []interface{} {
 func (f *FIFO) ListKeys() []string {
 	f.lock.RLock()
 	defer f.lock.RUnlock()
-	list := make([]string, 0, len(f.items))
-	for key := range f.items {
+	list := make([]string, 0, len(f.queue))


This isn't correct change - queue contains only "not yet consumed' items.

However - this isn't correct change here.

In particular in Delete method - you may return something from items without touching queue:
https://github.com/kubernetes/kubernetes/blob/master/staging/src/k8s.io/client-go/tools/cache/fifo.go#L218

So let's revert the change to fifo - and I can then approve the changes to delta_fifo.

yes, done. The changes to fifo had rolled back.

Besides, would it be better to keep the internal keys of queue and items consistent in fifo?

Good question - we would need to examine better the consequences and current usage.

@wojtek-t please review #105166 , which is the PR about keeping keys consistent between queue and items in fifo.

wojtek-t · 2021-09-03T06:35:00Z

This isn't a correct change.

/hold

wojtek-t · 2021-09-13T10:52:52Z

@NoicFank - please squash commits

/hold cancel

In function ListKeys, it better to use ‘queue’ instead of 'items' to get all the keys.

NoicFank · 2021-09-13T11:06:57Z

@NoicFank - please squash commits

/hold cancel

@wojtek-t ok, done.

wojtek-t · 2021-09-13T11:20:48Z

/lgtm
/approve

k8s-ci-robot · 2021-09-13T11:21:19Z

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: NoicFank, wojtek-t

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:

~~staging/src/k8s.io/client-go/tools/cache/OWNERS~~ [wojtek-t]

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

k8s-ci-robot added needs-triage Indicates an issue or PR lacks a `triage/foo` label and requires one. needs-ok-to-test Indicates a PR that requires an org member to verify it is safe to test. needs-priority Indicates a PR lacks a `priority/foo` label and requires one. labels Sep 2, 2021

k8s-ci-robot requested review from caesarxuchao and soltysh September 2, 2021 06:06

k8s-ci-robot added sig/api-machinery Categorizes an issue or PR as relevant to SIG API Machinery. and removed do-not-merge/needs-sig Indicates an issue or PR lacks a `sig/foo` label and requires one. labels Sep 2, 2021

sxllwx reviewed Sep 2, 2021

View reviewed changes

k8s-ci-robot added size/M Denotes a PR that changes 30-99 lines, ignoring generated files. and removed size/XS Denotes a PR that changes 0-9 lines, ignoring generated files. cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. labels Sep 2, 2021

k8s-ci-robot added the cncf-cla: no Indicates the PR's author has not signed the CNCF CLA. label Sep 2, 2021

NoicFank force-pushed the master branch 2 times, most recently from 71462ab to 96344ea Compare September 2, 2021 09:36

k8s-ci-robot added cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. and removed cncf-cla: no Indicates the PR's author has not signed the CNCF CLA. labels Sep 2, 2021

k8s-ci-robot assigned deads2k Sep 2, 2021

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 Sep 2, 2021

k8s-ci-robot added the sig/testing Categorizes an issue or PR as relevant to SIG Testing. label Sep 3, 2021

NoicFank force-pushed the master branch from 63c8d5e to 96344ea Compare September 3, 2021 02:18

k8s-ci-robot added release-note-none Denotes a PR that doesn't merit a release note. and removed do-not-merge/release-note-label-needed Indicates that a PR should not merge because it's missing one of the release note labels. labels Sep 3, 2021

wojtek-t reviewed Sep 3, 2021

View reviewed changes

staging/src/k8s.io/client-go/tools/cache/delta_fifo.go Show resolved Hide resolved

wojtek-t reviewed Sep 3, 2021

View reviewed changes

k8s-ci-robot added the do-not-merge/hold Indicates that a PR should not merge because someone has issued a /hold command. label Sep 3, 2021

NoicFank requested a review from wojtek-t September 4, 2021 11:39

wojtek-t self-assigned this Sep 13, 2021

NoicFank force-pushed the master branch from 6c9e897 to cd9a373 Compare September 13, 2021 10:51

k8s-ci-robot added size/S Denotes a PR that changes 10-29 lines, ignoring generated files. and removed size/M Denotes a PR that changes 30-99 lines, ignoring generated files. labels Sep 13, 2021

k8s-ci-robot removed the do-not-merge/hold Indicates that a PR should not merge because someone has issued a /hold command. label Sep 13, 2021

Improve DeltaFIFO function 'ListKeys'

f0ce875

In function ListKeys, it better to use ‘queue’ instead of 'items' to get all the keys.

NoicFank force-pushed the master branch from cd9a373 to f0ce875 Compare September 13, 2021 11:06

k8s-ci-robot added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Sep 13, 2021

k8s-ci-robot added the approved Indicates a PR has been approved by an approver from all required OWNERS files. label Sep 13, 2021

k8s-ci-robot merged commit 170f64d into kubernetes:master Sep 13, 2021

k8s-ci-robot added this to the v1.23 milestone Sep 13, 2021

NoicFank mentioned this pull request Jan 6, 2022

bugfix fifo: duplicate keys in queue #107381

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Improve DeltaFIFO function 'ListKeys' #104725

Improve DeltaFIFO function 'ListKeys' #104725

NoicFank commented Sep 2, 2021 •

edited

k8s-ci-robot commented Sep 2, 2021

k8s-ci-robot commented Sep 2, 2021

sxllwx Sep 2, 2021

NoicFank Sep 2, 2021

NoicFank commented Sep 2, 2021

NoicFank commented Sep 2, 2021

k8s-ci-robot commented Sep 2, 2021

fedebongio commented Sep 2, 2021

pacoxu commented Sep 3, 2021

wojtek-t Sep 3, 2021

wojtek-t Sep 13, 2021

NoicFank Sep 13, 2021

wojtek-t Sep 13, 2021

NoicFank Sep 21, 2021

wojtek-t commented Sep 3, 2021

wojtek-t commented Sep 13, 2021

NoicFank commented Sep 13, 2021

wojtek-t commented Sep 13, 2021

k8s-ci-robot commented Sep 13, 2021

Improve DeltaFIFO function 'ListKeys' #104725

Improve DeltaFIFO function 'ListKeys' #104725

Conversation

NoicFank commented Sep 2, 2021 • edited

What type of PR is this?

What this PR does / why we need it:

Which issue(s) this PR fixes:

Special notes for your reviewer:

Does this PR introduce a user-facing change?

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

k8s-ci-robot commented Sep 2, 2021

k8s-ci-robot commented Sep 2, 2021

sxllwx Sep 2, 2021

Choose a reason for hiding this comment

NoicFank Sep 2, 2021

Choose a reason for hiding this comment

NoicFank commented Sep 2, 2021

NoicFank commented Sep 2, 2021

k8s-ci-robot commented Sep 2, 2021

fedebongio commented Sep 2, 2021

pacoxu commented Sep 3, 2021

wojtek-t Sep 3, 2021

Choose a reason for hiding this comment

wojtek-t Sep 13, 2021

Choose a reason for hiding this comment

NoicFank Sep 13, 2021

Choose a reason for hiding this comment

wojtek-t Sep 13, 2021

Choose a reason for hiding this comment

NoicFank Sep 21, 2021

Choose a reason for hiding this comment

wojtek-t commented Sep 3, 2021

wojtek-t commented Sep 13, 2021

NoicFank commented Sep 13, 2021

wojtek-t commented Sep 13, 2021

k8s-ci-robot commented Sep 13, 2021

NoicFank commented Sep 2, 2021 •

edited