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
Conversation
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
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. |
Labelling this PR as size/L |
// If any intermediate operation causes overflow, the result will | ||
// overflow. | ||
if dif < 0 { | ||
return unscaled.Int64() * int64(math.Pow(float64(10), float64(-dif))) |
There was a problem hiding this comment.
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) |
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
OK
@k8s-bot ok to test |
@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 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
const
There was a problem hiding this comment.
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()) |
There was a problem hiding this comment.
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)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
fixed.
2f53a9a
to
c4effc0
Compare
if got != tt.want { | ||
t.Errorf("#%d: got = %v, want %v", i, got, tt.want) | ||
} | ||
if !reflect.DeepEqual(tt.unscaled, old) { |
There was a problem hiding this comment.
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
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. |
Travis continuous integration appears to have missed, closing and re-opening to trigger it |
GCE e2e build/test failed for commit cf82d6b. |
@timstclair Any idea why the CI fails? Or how should I find it out myself? |
GCE e2e test build/test passed for commit cf82d6b. |
The author of this PR is not in the whitelist for merge, can one of the admins add the 'ok-to-merge' label? |
@k8s-bot test this Tests are more than 48 hours old. Re-running tests. |
GCE e2e test build/test passed for commit cf82d6b. |
@k8s-bot test this Tests are more than 48 hours old. Re-running tests. |
GCE e2e build/test failed for commit cf82d6b. |
@timstclair Can we get this merged soon? |
ref/ #18418 |
@k8s-bot test this |
GCE e2e test build/test passed for commit cf82d6b. |
tests passing - merging manually to unblock further performance experiments |
api/resource: optimize scale function
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:
The final result is:
I also run the scheduler benchmark again. It doubles the throughput of
scheduler for 1000 nodes case.
/cc @timstclair