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.

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

Optimize random string generator to avoid multiple locks & use bit-masking #53720

Merged
merged 2 commits into from
Oct 13, 2017
Merged

Optimize random string generator to avoid multiple locks & use bit-masking #53720

merged 2 commits into from
Oct 13, 2017

Conversation

shyamjvs
Copy link
Member

@shyamjvs shyamjvs commented Oct 11, 2017 •
edited
Loading

Ref #53327

We recently started seeing a 50% decrease in scheduling throughput (for e.g in kubemark-500 scale job) and turns out #53135 introduced it.
The reason is this call to create a random 32-length string.
From the code of the rand utility (which is being heavily used throughout the system for randomizing object names), I noticed following performance issues:

  • to create an n-length string, we are making n calls to rand.Intn() each of which does a lock+unlock operation on the RNG.. while just 1 lock+unlock operation is enough for all
  • we're choosing one character (from an alphabet of 27 chars) per each random integer.. while we can select 10 characters using a single int63 (by masking and bit-shifting) as 1 character uses just 5 bits of randomness
  • the character set is defined as a global slice (mutable), so the compiler needs to fetch length of the slice on each invocation to len() (we're making n of those).. while we can just use a const string (immutable) which will make len directly available as a cached constant (yes, go does it!)

This PR is making the above fixes. I'll try to add some benchmarking to measure the difference (as @wojtek-t suggested).

/cc @kubernetes/sig-scalability-misc @kubernetes/sig-scheduling-bugs @kubernetes/sig-api-machinery-misc @wojtek-t @smarterclayton

@shyamjvs shyamjvs added the do-not-merge DEPRECATED. Indicates that a PR should not merge. Label can only be manually applied/removed. label Oct 11, 2017
@k8s-ci-robot k8s-ci-robot added do-not-merge/release-note-label-needed Indicates that a PR should not merge because it's missing one of the release note labels. 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 Oct 11, 2017
@k8s-github-robot k8s-github-robot added the approved Indicates a PR has been approved by an approver from all required OWNERS files. label Oct 11, 2017
@shyamjvs
Copy link
Member Author

/test pull-kubernetes-kubemark-e2e-gce-big

@k8s-ci-robot k8s-ci-robot added size/L Denotes a PR that changes 100-499 lines, ignoring generated files. and removed size/XS Denotes a PR that changes 0-9 lines, ignoring generated files. labels Oct 11, 2017
@k8s-github-robot k8s-github-robot removed the approved Indicates a PR has been approved by an approver from all required OWNERS files. label Oct 11, 2017
@shyamjvs
Copy link
Member Author

/test pull-kubernetes-kubemark-e2e-gce-big

@k8s-ci-robot k8s-ci-robot added size/S Denotes a PR that changes 10-29 lines, ignoring generated files. and removed size/L Denotes a PR that changes 100-499 lines, ignoring generated files. labels Oct 11, 2017
@shyamjvs
Copy link
Member Author

/test pull-kubernetes-kubemark-e2e-gce-big

1 similar comment
@shyamjvs
Copy link
Member Author

/test pull-kubernetes-kubemark-e2e-gce-big

@k8s-ci-robot k8s-ci-robot added size/L Denotes a PR that changes 100-499 lines, ignoring generated files. and removed size/S Denotes a PR that changes 10-29 lines, ignoring generated files. labels Oct 12, 2017
@shyamjvs
Copy link
Member Author

/test pull-kubernetes-kubemark-e2e-gce-big

@k8s-ci-robot k8s-ci-robot added size/M Denotes a PR that changes 30-99 lines, ignoring generated files. and removed size/L Denotes a PR that changes 100-499 lines, ignoring generated files. labels Oct 12, 2017
@shyamjvs
Copy link
Member Author

/test pull-kubernetes-kubemark-e2e-gce-big

@shyamjvs
Copy link
Member Author

/test pull-kubernetes-kubemark-e2e-gce-big

@shyamjvs shyamjvs changed the title [Do not merge] PR for kubemark-500 experiment Optimize random string generator to avoid multiple locks & use bit-masking Oct 12, 2017
@shyamjvs shyamjvs added release-note Denotes a PR that will be considered when it comes time to generate release notes. and removed do-not-merge DEPRECATED. Indicates that a PR should not merge. Label can only be manually applied/removed. labels Oct 12, 2017
@shyamjvs
Copy link
Member Author

@jsafrane would be able to answer.

@shyamjvs shyamjvs force-pushed the test-kubemark branch 2 times, most recently from 0d913d8 to 42c0314 Compare October 12, 2017 16:46
@smarterclayton
Copy link
Contributor

smarterclayton commented Oct 12, 2017 •
edited
Loading

Why are we using a global static utility function that needs a global static lock? That seems... bad.

We should be initializing a random source for whatever components need it and let them do their locking. The volume controller should only be contending with itself, in which case just give it a seed per worker (which should be easy).

@shyamjvs shyamjvs mentioned this pull request Oct 13, 2017
Open
@shyamjvs
Copy link
Member Author

@smarterclayton I filed #53888 for the issue you stated. I'd prefer having that change in a separate PR as there are multiple places where the change needs to be made (i.e replace global RNG references with newRNG() calls).

@wojtek-t
Copy link
Member

@smarterclayton I filed #53888 for the issue you stated. I'd prefer having that change in a separate PR as there are multiple places where the change needs to be made (i.e replace global RNG references with newRNG() calls).

I agree - let's not try to solve all the problems of random library as a resolving scalability regression.

/lgtm

@k8s-ci-robot k8s-ci-robot added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Oct 13, 2017
@wojtek-t
Copy link
Member

/approve

@k8s-github-robot k8s-github-robot added the approved Indicates a PR has been approved by an approver from all required OWNERS files. label Oct 13, 2017
@k8s-github-robot k8s-github-robot removed the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Oct 13, 2017
@shyamjvs
Copy link
Member Author

@wojtek-t Also added the benchmark (though I'm still trying to make it run locally). Could you re-lgtm?

@wojtek-t
Copy link
Member

/lgtm

@k8s-ci-robot k8s-ci-robot added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Oct 13, 2017
@k8s-github-robot
Copy link

[APPROVALNOTIFIER] This PR is APPROVED

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

Associated issue: 53327

The full list of commands accepted by this bot can be found here.

Needs approval from an approver in each of these OWNERS Files:

You can indicate your approval by writing /approve in a comment
You can cancel your approval by writing /approve cancel in a comment

@shyamjvs
Copy link
Member Author

Results of benchmark:

without this PR:

BenchmarkRandomStringGeneration-12    	  300000	      4129 ns/op

with this PR:

BenchmarkRandomStringGeneration-12    	 5000000	       337 ns/op

@wojtek-t
Copy link
Member

Cool, but that's something I expected.
Looking forward to see the impact on kubemark test jobs.

@k8s-github-robot
Copy link

/test all [submit-queue is verifying that this PR is safe to merge]

@k8s-github-robot
Copy link

Automatic merge from submit-queue. If you want to cherry-pick this change to another branch, please follow the instructions here.

@k8s-github-robot k8s-github-robot merged commit f1d9962 into kubernetes:master Oct 13, 2017
@shyamjvs shyamjvs deleted the test-kubemark branch October 13, 2017 13:11
@smarterclayton
Copy link
Contributor

smarterclayton commented Oct 13, 2017 via email

@aveshagarwal aveshagarwal mentioned this pull request Oct 13, 2017
Merged
@wojtek-t
Copy link
Member

Changing it is fine, I just want to make sure we don't continue the pattern
(i.e. if we cut ourselves on a sharp corner, we should fix the corner, not
put a sign up that says "don't touch"). This should be the last time
someone regresses on this by accidentally using this package.

Agree. I just wanted to fix regression ASAP and this seemed to fix it (and already existed).
But I completely agree that we should get rid of that package (or rework it somehow to at least not be global).

openshift-merge-robot added a commit to openshift/origin that referenced this pull request Oct 25, 2017
@openshift-merge-robot
Merge pull request #16864 from aveshagarwal/master-backport-53793-53884
145cdaf 
Automatic merge from submit-queue.

UPSTREAM: 53989: Remove repeated random string generations in scheduler volume predicate

@sjenning @smarterclayton

Though the upstream PR 53793 has been backported to kube 1.7 branch (53884). I am not sure if we have a plan for another origin rebase to latest kube 1.7, and if we would want to wait for that.

So this backports following 3 PRs:
kubernetes/kubernetes#53793 
kubernetes/kubernetes#53720 (partial)
kubernetes/kubernetes#53989
@shyamjvs shyamjvs mentioned this pull request Mar 21, 2018
Closed
3 tasks
@shyamjvs shyamjvs mentioned this pull request May 18, 2018
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees

@gmarek gmarek

@wojtek-t wojtek-t

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. lgtm "Looks good to me", indicates that a PR is ready to be merged. release-note Denotes a PR that will be considered when it comes time to generate release notes. size/M Denotes a PR that changes 30-99 lines, ignoring generated files.
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
7 participants
@shyamjvs @k8s-ci-robot @liggitt @smarterclayton @wojtek-t @k8s-github-robot @gmarek