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

quantity: Add multiplication methods #117411

Merged
merged 6 commits into from
Oct 14, 2023

Conversation

tenzen-y
Copy link
Member

@tenzen-y tenzen-y commented Apr 17, 2023

Add multiplication functionality to Quantity.

What type of PR is this?

/kind feature

What this PR does / why we need it:

I added multiplication functionally to Quantity.
Please see #117044 about the background.

Which issue(s) this PR fixes:

Fixes #117044

Special notes for your reviewer:

Does this PR introduce a user-facing change?

Add multiplication functionality to Quantity.

Additional documentation e.g., KEPs (Kubernetes Enhancement Proposals), usage docs, etc.:

Usage:

ps := kueue.PodSet{
	Name:  "test",
	Count: int32(100),
	Template: corev1.PodTemplateSpec{
		Spec: corev1.PodSpec{
			Containers: []corev1.Container{
				{
					Name: "main",
					Resources: corev1.ResourceRequirements{
						Requests: corev1.ResourceList{
							corev1.ResourceMemory: resource.MustParse("32Gi"),
						},
					},
				},
			},
		},
	},
}

requestedMemory := ps.Template.Spec.Containers[0].Resources.Requests[corev1.ResourceMemory]
ok := requestedMemory.Mul(int64(ps.Count))

// Output:
//
//	requestedMemory: 3200Gi
fmt.Sprintf("requestedMemory: %s\n", requestedMemory.String())

@k8s-ci-robot k8s-ci-robot added release-note Denotes a PR that will be considered when it comes time to generate release notes. size/L Denotes a PR that changes 100-499 lines, ignoring generated files. kind/feature Categorizes issue or PR as related to a new feature. kind/api-change Categorizes issue or PR as related to adding, removing, or otherwise changing an API 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. needs-priority Indicates a PR lacks a `priority/foo` label and requires one. labels Apr 17, 2023
@tenzen-y
Copy link
Member Author

/sig api-machinery
/wg batch

@k8s-ci-robot k8s-ci-robot added sig/api-machinery Categorizes an issue or PR as relevant to SIG API Machinery. wg/batch Categorizes an issue or PR as relevant to WG Batch. and removed do-not-merge/needs-sig Indicates an issue or PR lacks a `sig/foo` label and requires one. labels Apr 17, 2023
@k8s-triage-robot
Copy link

This PR may require API review.

If so, when the changes are ready, complete the pre-review checklist and request an API review.

Status of requested reviews is tracked in the API Review project.

@tenzen-y
Copy link
Member Author

tenzen-y commented Apr 17, 2023

I think this PR doesn't include API changes.

/remove-kind api-change

@k8s-ci-robot k8s-ci-robot removed the kind/api-change Categorizes issue or PR as related to adding, removing, or otherwise changing an API label Apr 17, 2023
@fedebongio
Copy link
Contributor

/help

@cici37 cici37 added the help wanted Denotes an issue that needs help from a contributor. Must meet "help wanted" guidelines. label Apr 25, 2023
@tenzen-y
Copy link
Member Author

@kubernetes/sig-api-machinery-members Could you review this PR when you get a chance? Thanks in advance.

@@ -592,6 +592,19 @@ func (q *Quantity) Sub(y Quantity) {
q.ToDec().d.Dec.Sub(q.d.Dec, y.AsDec())
}

// Mul multiplies the provided y quantity to the current value. If the current value is zero,
// the format of the quantity will be updated to the format of y.
func (q *Quantity) Mul(y Quantity) {
Copy link
Member

Choose a reason for hiding this comment

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

I strongly recommend multiplying by a scalar instead (i.e., just a plain int or int64).

Quantities are implicitly typed (either milliCPU or RAM) and multiplying them together gives units like squared milliCPU (which would be microCPU) or squared bytes. For your use case I think multiplying by a scalar makes much more sense. The implementation will be simpler too.

The actual invariant you need to test / prove is that repeated addition gives the same answer as the multiplication. The point of this type is that there isn't floating point error accumulation.

Copy link
Member

Choose a reason for hiding this comment

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

I think the signature of this function needs to be able to visibly fail on overflow.

Copy link
Member

Choose a reason for hiding this comment

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

or if not overflow, it could have a return value indicating when the result is inexact (e.g. because it had to change scale to avoid overflow and repeated addition might get a different final answer).

Copy link
Member Author

Choose a reason for hiding this comment

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

Thank you for some suggestions!

I strongly recommend multiplying by a scalar instead (i.e., just a plain int or int64).

It sounds much more reasonable to me.

I will change the implementation so that this function has an arg typed int64 since I don't have any reasons to want to use a Quantity instead of a scaler.

IIUC, I can address your other comments once I change this implementation as you suggested (Quantity -> scalar).

return false
}
a.value = c
case a.scale > b.scale:
Copy link
Member

Choose a reason for hiding this comment

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

This isn't the thing to do at all (see my other comment), but for future reference, the natural way to multiply two numbers in the form a * b ^ c is just a1*a2 * b^(c1+c2). That is, values multiply and scales add. Great care needs to be taken when values are large.

Choose a reason for hiding this comment

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

Good explanation. Thanks, @lavalamp .

"... the natural way to multiply two numbers in the form a * b ^ c is just a1*a2 * b^(c1+c2). That is, values multiply and scales add. Great care needs to be taken when values are large.
"


{int64Amount{value: mostPositive, scale: -1}, int64Amount{value: 1, scale: -1}, int64Amount{value: 9223372036854775807, scale: -1}, true},
{int64Amount{value: mostPositive, scale: -1}, int64Amount{value: 0, scale: -1}, int64Amount{value: 0, scale: -1}, true},
{int64Amount{value: mostPositive / 10, scale: 1}, int64Amount{value: 10, scale: 0}, int64Amount{value: mostPositive, scale: -1}, false},
Copy link
Member

Choose a reason for hiding this comment

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

These last three test cases are very careful to test the cases where the algorithm returns correct answers. Instead, they need to test the cases where the algorithm overflows. I would expect that some overflow can be prevented by changing scale.

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 would expect that some overflow can be prevented by changing scale.

In other operators for an int64Amount, such as Add and Sub, they don't change a scale if overflow or underflow would result, and then they would return false.

So, I implemented Mul so that Mul returns false, not changing a scale.

Note: In Quantity, Mul avoids overflow by changing a scale.

if q.d.Dec == nil && y.d.Dec == nil && q.i.Mul(y.i) {
return
}
q.ToDec().d.Dec.Mul(q.d.Dec, y.AsDec())
Copy link
Member

Choose a reason for hiding this comment

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

In addition to my other reason for using a scalar -- I believe changing the format will destroy the property that multiplication needs to give the exact result of repeated addition. I don't think you should do this.

@alexzielenski
Copy link
Contributor

/triage accepted

@k8s-ci-robot k8s-ci-robot added triage/accepted Indicates an issue or PR is ready to be actively worked on. and removed needs-triage Indicates an issue or PR lacks a `triage/foo` label and requires one. labels Apr 27, 2023
@tenzen-y tenzen-y force-pushed the add-multiply-method branch 3 times, most recently from a1db58c to 82a602a Compare May 6, 2023 18:48
@tenzen-y
Copy link
Member Author

tenzen-y commented Jun 9, 2023

@thockin I updated this PR! Could you take another look? Thanks!

@tenzen-y
Copy link
Member Author

tenzen-y commented Jun 9, 2023

Unrelated error {kubelet kind-worker} Failed: Failed to pull image "registry.k8s.io/e2e-test-images/busybox:1.29-4": pull QPS exceeded occurred.

/test pull-kubernetes-e2e-kind-ipv6

@tenzen-y
Copy link
Member Author

tenzen-y commented Jun 9, 2023

Rebased.

Copy link
Member

@thockin thockin left a comment

Choose a reason for hiding this comment

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

Sorry to be pedantic here - for something as obviously right or wrong as math, we had better be right, and not wrong :)

@tenzen-y
Copy link
Member Author

@thockin I addressed all comments. Could you please take another look at this? Thanks for the review!

Copy link
Member

@thockin thockin left a comment

Choose a reason for hiding this comment

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

sorry

if ok != test.ok {
t.Errorf("%v: unexpected ok: %t", test, ok)
}
if ok {
Copy link
Member

Choose a reason for hiding this comment

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

If the result is !ok, should we be relying on the result at all? What I mean is I think it maybe should look like:

if ok && !test.ok {
    t.Errorf("unexpected success: %v", c)
} else if !ok && test.ok {
    t.Errorf("unexpected failure")
} else if ok {
    // confirm result is correct
} else {
    // confirm source is not modified
}

Emphasis being that if ok != test.ok, we do not look any further. Then, in all the cases above where the result is expected to be false, just set c to int64Amount{} so it isn't distracting?

Copy link
Member Author

Choose a reason for hiding this comment

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

Sounds good to me. I will apply the suggestions!

Copy link
Member Author

Choose a reason for hiding this comment

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

Done.

c int64Amount
ok bool
}{
{int64Amount{value: 100, scale: 1}, 1000, int64Amount{value: 100000, scale: 1}, true},
Copy link
Member

Choose a reason for hiding this comment

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

I feel like I'm a pest, but these cases still feel sort of haphazard, can we be a little more systematic? E.g. something like:

https://go.dev/play/p/k4IOkuEvrXD

That may be a bit much, but I hope you see what I mean - I'm staring at these big tables of struct initisalisations, some with function calls in-between and trying to convince myself that all the edge case are covered. Like, 0 * 0 isn't covered. Probably should be.

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 really appreciate your review :)
I'll try to make tests more systematic and add a test case for 0 * 0.

Copy link
Member Author

Choose a reason for hiding this comment

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

@thockin I tried to make test cases more systematic. However, because we need to define expected ok against test cases in advance, it was hard to make test cases more systematic using the way you suggested.

So, how about just adding a formula as a test name like this:

"100×10^1 × 1000 = 100000×10^1": {int64Amount{value: 100, scale: 1}, 1000, int64Amount{value: 100000, scale: 1}, true}
"1×10^100 × 10 = OVERFLOW": {int64Amount{value: 1, scale: 100}, 10, int64Amount{value: 1, scale: 100}, false},

Although this way couldn't make test cases systematic, I believe that this way makes it easier to find leaking edge cases.

Copy link
Member

Choose a reason for hiding this comment

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

I love the idea of adding useful names

Copy link
Member

Choose a reason for hiding this comment

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

Maybe also, for error cases, make t.c be int64Amount{} since we the test loop should not even look at it.

Copy link
Member Author

Choose a reason for hiding this comment

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

Maybe also, for error cases, make t.c be int64Amount{} since we the test loop should not even look at it.

SGTM

@thockin thockin self-assigned this Jul 14, 2023
@tenzen-y
Copy link
Member Author

Sorry for leaving this PR. I try to address the suggestions in the next release cycle (v1.29).

@thockin
Copy link
Member

thockin commented Oct 12, 2023

No updates here?

@tenzen-y
Copy link
Member Author

No updates here?

Oops. Sorry, I missed this PR update. I'm here. I will update this PR today.

Add multiplication functionality to Quantity.

Signed-off-by: Yuki Iwai <[email protected]>
Signed-off-by: Yuki Iwai <[email protected]>
Signed-off-by: Yuki Iwai <[email protected]>
Signed-off-by: Yuki Iwai <[email protected]>
@thockin
Copy link
Member

thockin commented Oct 14, 2023

I'll approve - small things can be followups if you want. Just makes tests clearer.

Thanks!

/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 Oct 14, 2023
@k8s-ci-robot
Copy link
Contributor

LGTM label has been added.

Git tree hash: fbbb444025d391c42c6ad910c238dbc04cabf717

@k8s-ci-robot
Copy link
Contributor

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: tenzen-y, thockin

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

@k8s-ci-robot k8s-ci-robot added the approved Indicates a PR has been approved by an approver from all required OWNERS files. label Oct 14, 2023
@k8s-ci-robot k8s-ci-robot merged commit 52cba2d into kubernetes:master Oct 14, 2023
17 checks passed
@k8s-ci-robot k8s-ci-robot added this to the v1.29 milestone Oct 14, 2023
@tenzen-y
Copy link
Member Author

Thank you so much. I will create a follow-up PR.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
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. help wanted Denotes an issue that needs help from a contributor. Must meet "help wanted" guidelines. 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. release-note Denotes a PR that will be considered when it comes time to generate release notes. sig/api-machinery Categorizes an issue or PR as relevant to SIG API Machinery. size/L Denotes a PR that changes 100-499 lines, ignoring generated files. triage/accepted Indicates an issue or PR is ready to be actively worked on. wg/batch Categorizes an issue or PR as relevant to WG Batch.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Provide a multiplication method for the resource.Quantity