Speed up counting of bits in allocator

[twpayne]

What type of PR is this?

/kind cleanup

What this PR does / why we need it:

This PR tidies up counting of bits in pkg/registry/core/service/allocator.

Switching from using math/big.Int.Bytes to math/big.Int.Bits has two effects:

• It removes an allocation (there is no longer a need for an intermediate []byte).
• It allows the bits to be counted 64 at a time instead of 8 at a time.

Which issue(s) this PR fixes:

NONE

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]

@twpayne: 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/test-infra repository.

[k8s-ci-robot]

Welcome @twpayne!

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]

Hi @twpayne. 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.

[twpayne]

/assign @smarterclayton

[twpayne]

/unassign @smarterclayton

[aojea]

we should have some benchmarks demonstrating this

[twpayne]

we should have some benchmarks demonstrating this

The code that this replaces performs the following steps:

1. Allocates a []byte for the words in n (a math/big.Int).
2. Calls this function to copy n's words (effectively a []unit64) into a []byte.
3. Iterates over each byte, counting the set bits 8 at a time.

The replacement code in this PR performs the following steps:

1. Iterates over n's words counting the set bits 64 at a time.

Is it necessary to demonstrate that the replacement code is faster than the replaced code with a benchmark?

[aojea]

Is it necessary to demonstrate that the replacement code is faster than the replaced code with a benchmark?

yep

[twpayne]

OK, benchmark:

Before:

goos: linux
goarch: amd64
pkg: k8s.io/kubernetes/pkg/registry/core/service/allocator
cpu: Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz
BenchmarkCountBits-8     9459236               140.4 ns/op

After:

goos: linux
goarch: amd64
pkg: k8s.io/kubernetes/pkg/registry/core/service/allocator
cpu: Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz
BenchmarkCountBits-8    140667842                9.541 ns/op

[twpayne]

/assign @smarterclayton

[aojea]

/ok-to-test
/lgtm
/assign @thockin
naive question, can there be some issues in 32 bits architectures?

[twpayne]

naive question, can there be some issues in 32 bits architectures?

On 32-bit machines math/big.Ints use []uint32s instead of []uint64, however the math/bits.OnesCount64 will still correctly count the bits in a uint32 as the upper bits will be zero when Go converts the uint32 to a uint64.

Note that math/bits.OnesCount64 is already used by Kubernetes.

[thockin]

Thanks!

/lgtm
/approve

[thockin]

The docs for math/big.Word say "A Word represents a single digit of a multi-precision unsigned integer" which is certainly not explaining very much.

The docs for Bits() say "Bits is intended to support implementation of missing low-level Int functionality outside this package; it should be avoided otherwise." I guess this counts as "missing low-level Int functionality".

[k8s-ci-robot]

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: aanm, thockin, twpayne

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:

• pkg/registry/OWNERS [thockin]

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

[aojea]

/sig network
as the allocator belong to services???