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.

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

api/resource: optimize scale function #18170

Merged
merged 1 commit into from Dec 9, 2015
Merged

Conversation

xiang90
Copy link
Contributor

@xiang90 xiang90 commented Dec 3, 2015

The original scale function takes around 800ns/op with more
than 10 allocations. It significantly slow down scheduler
and other components that heavily relys on resource pkg.
For more information see #18126.

This pull request tries to optimize scale function. It takes
two approach:

  1. when the value is small, only use normal math ops.
  2. when the value is large, use math.Big with buffer pool.

The final result is:

BenchmarkScaledValueSmall-4 20000000            66.9 ns/op         0 B/op          0 allocs/op
BenchmarkScaledValueLarge-4  2000000           711 ns/op          48 B/op          1 allocs/op

I also run the scheduler benchmark again. It doubles the throughput of
scheduler for 1000 nodes case.

/cc @timstclair

@k8s-bot
Copy link

k8s-bot commented Dec 3, 2015

Can one of the admins verify that this patch is reasonable to test? (reply "ok to test", or if you trust the user, reply "add to whitelist")

If this message is too spammy, please complain to ixdy.

1 similar comment
@k8s-bot
Copy link

k8s-bot commented Dec 3, 2015

Can one of the admins verify that this patch is reasonable to test? (reply "ok to test", or if you trust the user, reply "add to whitelist")

If this message is too spammy, please complain to ixdy.

@k8s-github-robot
Copy link

Labelling this PR as size/L

@k8s-github-robot k8s-github-robot added the size/L Denotes a PR that changes 100-499 lines, ignoring generated files. label Dec 3, 2015
@xiang90 xiang90 changed the title resource: optimize scale function api/resource: optimize scale function Dec 3, 2015
// If any intermediate operation causes overflow, the result will
// overflow.
if dif < 0 {
return unscaled.Int64() * int64(math.Pow(float64(10), float64(-dif)))

Choose a reason for hiding this comment

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

Prefer math.Pow10, or implement your own int64 version.

}()

// a = 10^(dif)
a.Exp(bigTen, b.SetInt64(int64(dif)), nil)

Choose a reason for hiding this comment

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

Consider making a lookup table for these values, similar to how math.Pow10 works.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

Can we add a TODO for now? I did not find this cost too much for now.

Choose a reason for hiding this comment

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

OK

@timstclair
Copy link

@k8s-bot ok to test

@xiang90
Copy link
Contributor Author

xiang90 commented Dec 3, 2015

@timstclair All fixed. PTAL.

// We have to be careful about the intermediate operations.

// fast path when unscaled < max.Int64 and exp(10,dif) < max.Int64
log10MaxInt64 := 19

Choose a reason for hiding this comment

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

const

Copy link
Contributor Author

Choose a reason for hiding this comment

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

fixed.


for i, tt := range tests {
old := &big.Int{}
old.SetBytes(tt.unscaled.Bytes())

Choose a reason for hiding this comment

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

(nit) prefer: old := &big.Int{}.Set(tt.unscaled)

Copy link
Contributor Author

Choose a reason for hiding this comment

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

fixed.

@xiang90 xiang90 force-pushed the scale branch 2 times, most recently from 2f53a9a to c4effc0 Compare December 4, 2015 00:10
if got != tt.want {
t.Errorf("#%d: got = %v, want %v", i, got, tt.want)
}
if !reflect.DeepEqual(tt.unscaled, old) {

Choose a reason for hiding this comment

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

Prefer tt.unscaled.Cmp(old) != 0

@timstclair
Copy link

This looks great, mostly style issues remaining. Thanks!

For future reference, respond to feedback on PRs in separate commits. It makes it much easier to review.

@timstclair timstclair assigned timstclair and unassigned eparis Dec 4, 2015
@timstclair timstclair added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Dec 4, 2015
@k8s-github-robot
Copy link

@k8s-bot ok to test
@k8s-bot test this

pr builder appears to be missing, activating due to 'lgtm' label.

@k8s-github-robot
Copy link

Travis continuous integration appears to have missed, closing and re-opening to trigger it

@k8s-bot
Copy link

k8s-bot commented Dec 4, 2015

GCE e2e build/test failed for commit cf82d6b.

@xiang90
Copy link
Contributor Author

xiang90 commented Dec 4, 2015

@timstclair Any idea why the CI fails? Or how should I find it out myself?

@timstclair
Copy link

Both look like flakes.

@k8s-bot test this
@k8s-bot unit test this

@k8s-bot
Copy link

k8s-bot commented Dec 4, 2015

GCE e2e test build/test passed for commit cf82d6b.

@k8s-github-robot
Copy link

The author of this PR is not in the whitelist for merge, can one of the admins add the 'ok-to-merge' label?

@k8s-github-robot
Copy link

@k8s-bot test this

Tests are more than 48 hours old. Re-running tests.

@k8s-bot
Copy link

k8s-bot commented Dec 6, 2015

GCE e2e test build/test passed for commit cf82d6b.

@k8s-github-robot
Copy link

@k8s-bot test this

Tests are more than 48 hours old. Re-running tests.

@k8s-bot
Copy link

k8s-bot commented Dec 8, 2015

GCE e2e build/test failed for commit cf82d6b.

@xiang90
Copy link
Contributor Author

xiang90 commented Dec 9, 2015

@timstclair Can we get this merged soon?

@davidopp
Copy link
Member

davidopp commented Dec 9, 2015

ref/ #18418

@gmarek
Copy link
Contributor

gmarek commented Dec 9, 2015

@k8s-bot test this

@k8s-bot
Copy link

k8s-bot commented Dec 9, 2015

GCE e2e test build/test passed for commit cf82d6b.

@wojtek-t
Copy link
Member

wojtek-t commented Dec 9, 2015

tests passing - merging manually to unblock further performance experiments

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
lgtm "Looks good to me", indicates that a PR is ready to be merged. size/L Denotes a PR that changes 100-499 lines, ignoring generated files.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

10 participants