Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

feat: improve the backoff calculation to O(1) #131714

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
Merged
merged 1 commit into from
May 14, 2025
Merged

feat: improve the backoff calculation to O(1) #131714

merged 1 commit into from
May 14, 2025

Conversation

sanposhiho
Copy link
Member

@sanposhiho sanposhiho commented May 11, 2025 •
edited
Loading

What type of PR is this?

/kind feature

What this PR does / why we need it:

Currently, we're calculating the backoff time with O(attempt), and this PR improves it to O(1).

func BenchmarkBackoffQueue_calculateBackoffDuration(b *testing.B) {
	benchmarks := []struct {
		name                   string
		initialBackoffDuration time.Duration
		maxBackoffDuration     time.Duration
		attempts               int32
	}{
		{
			name:                   "10000",
			initialBackoffDuration: 1 * time.Nanosecond,
			maxBackoffDuration:     math.MaxInt64 * time.Nanosecond,
			attempts:               10000,
		},
	}

	for _, bm := range benchmarks {
		b.Run(bm.name, func(b *testing.B) {
			bq := newBackoffQueue(clock.RealClock{}, bm.initialBackoffDuration, bm.maxBackoffDuration, newDefaultQueueSort(), true)
			podInfo := &framework.QueuedPodInfo{Attempts: int(bm.attempts)}
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				_ = bq.calculateBackoffDuration(podInfo)
			}
		})
	}
}

before

Running tool: /usr/local/go/bin/go test -benchmem -run=^$ -bench ^BenchmarkBackoffQueue_calculateBackoffDuration$ k8s.io/kubernetes/pkg/scheduler/backend/queue

goos: darwin
goarch: arm64
pkg: k8s.io/kubernetes/pkg/scheduler/backend/queue
cpu: Apple M2 Pro
BenchmarkBackoffQueue_calculateBackoffDuration/10000-12         	57746674	        20.86 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	k8s.io/kubernetes/pkg/scheduler/backend/queue	2.027s

after

Running tool: /usr/local/go/bin/go test -benchmem -run=^$ -bench ^BenchmarkBackoffQueue_calculateBackoffDuration$ k8s.io/kubernetes/pkg/scheduler/backend/queue

goos: darwin
goarch: arm64
pkg: k8s.io/kubernetes/pkg/scheduler/backend/queue
cpu: Apple M2 Pro
BenchmarkBackoffQueue_calculateBackoffDuration/10000-12         	1000000000	         0.4540 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	k8s.io/kubernetes/pkg/scheduler/backend/queue	1.283s

Which issue(s) this PR fixes:

Fixes #

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

@k8s-ci-robot k8s-ci-robot added release-note-none Denotes a PR that doesn't merit a release note. kind/feature Categorizes issue or PR as related to a new feature. size/S Denotes a PR that changes 10-29 lines, ignoring generated files. cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. do-not-merge/needs-sig Indicates an issue or PR lacks a `sig/foo` label and requires one. needs-triage Indicates an issue or PR lacks a `triage/foo` label and requires one. labels May 11, 2025
@k8s-ci-robot
Copy link
Contributor

This issue is currently awaiting triage.

If a SIG or subproject determines this is a relevant issue, they will accept it by applying the triage/accepted label and provide further guidance.

The triage/accepted label can be added by org members by writing /triage accepted in a comment.

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.

@k8s-ci-robot k8s-ci-robot added needs-priority Indicates a PR lacks a `priority/foo` label and requires one. approved Indicates a PR has been approved by an approver from all required OWNERS files. labels May 11, 2025
@k8s-ci-robot k8s-ci-robot requested review from damemi and macsko May 11, 2025 23:08
@k8s-ci-robot k8s-ci-robot added sig/scheduling Categorizes an issue or PR as relevant to SIG Scheduling. and removed do-not-merge/needs-sig Indicates an issue or PR lacks a `sig/foo` label and requires one. labels May 11, 2025
@sanposhiho
Copy link
Member Author

sanposhiho commented May 11, 2025 •
edited
Loading

/hold

(not to merge the pr without the approver's approval

@k8s-ci-robot k8s-ci-robot added the do-not-merge/hold Indicates that a PR should not merge because someone has issued a /hold command. label May 11, 2025
@sanposhiho sanposhiho changed the title feat: improve the backoff calculation to o(1) feat: improve the backoff calculation to O(1) May 11, 2025
@sanposhiho
Copy link
Member Author

/retest

@sanposhiho
Copy link
Member Author

/cc @dom4ha @macsko

@k8s-ci-robot k8s-ci-robot requested a review from dom4ha May 12, 2025 10:43
dom4ha
dom4ha reviewed May 13, 2025
View reviewed changes
pkg/scheduler/backend/queue/backoff_queue.go
}
duration += duration
shift := podInfo.Attempts - 1
if bq.podInitialBackoff > bq.podMaxBackoff>>shift {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
if bq.podInitialBackoff > bq.podMaxBackoff>>shift {
if bq.podInitialBackoff > bq.podMaxBackoff >> shift {

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

gofmt doesn't allow that format.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm curious why they format >> to be A>>B, while do << to be A << B (like L246) though.

Copy link
Member

@macsko macsko May 14, 2025 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's to emphasize precedence of operators. In bq.podInitialBackoff > bq.podMaxBackoff>>shift it shows that >> will be executed before >. Similarly, it's a*b + c, but a * b. So, gofmt puts spaces between operators, but for the most important one it removes the spaces (if there are multiple ops).

Copy link
Member Author

@sanposhiho sanposhiho May 14, 2025 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I see, interesting

@dom4ha
Copy link
Member

dom4ha commented May 13, 2025

/approve

Awesome, just formatting comment

@macsko
Copy link
Member

macsko commented May 14, 2025

Great improvement!

/lgtm
/approve

@k8s-ci-robot k8s-ci-robot added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label May 14, 2025
@k8s-ci-robot
Copy link
Contributor

LGTM label has been added.

Git tree hash: 092f7bf6a1786a9af128039e9c9d1febbe3b46d2

@k8s-ci-robot
Copy link
Contributor

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: dom4ha, macsko, sanposhiho

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:

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

@sanposhiho
Copy link
Member Author

/unhold

@k8s-ci-robot k8s-ci-robot removed the do-not-merge/hold Indicates that a PR should not merge because someone has issued a /hold command. label May 14, 2025
@k8s-ci-robot k8s-ci-robot merged commit feb3933 into kubernetes:master May 14, 2025
14 checks passed
@k8s-ci-robot k8s-ci-robot added this to the v1.34 milestone May 14, 2025
@sanposhiho sanposhiho mentioned this pull request May 15, 2025
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@dom4ha dom4ha dom4ha left review comments

@damemi damemi Awaiting requested review from damemi

@macsko macsko Awaiting requested review from macsko

Assignees

@macsko macsko

Labels
approved Indicates a PR has been approved by an approver from all required OWNERS files. cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. kind/feature Categorizes issue or PR as related to a new feature. lgtm "Looks good to me", indicates that a PR is ready to be merged. needs-priority Indicates a PR lacks a `priority/foo` label and requires one. needs-triage Indicates an issue or PR lacks a `triage/foo` label and requires one. release-note-none Denotes a PR that doesn't merit a release note. sig/scheduling Categorizes an issue or PR as relevant to SIG Scheduling. size/S Denotes a PR that changes 10-29 lines, ignoring generated files.
Projects
None yet
Milestone
v1.34
Development

Successfully merging this pull request may close these issues.
4 participants
@sanposhiho @k8s-ci-robot @dom4ha @macsko
Morty Proxy This is a proxified and sanitized view of the page, visit original site.