Uses container/heap for DelayingQueue #45070

alindeman · 2017-04-28T03:56:09Z

The current implementation of DelayingQueue doesn't perform very well when a large number of items (at random delays) are inserted. The original authors seemed to be aware of this and noted it in a TODO comment. This is my attempt at switching the implementation to use a priority queue based on container/heap.

Benchmarks from before the change:

╰─ go test -bench=. -benchmem | tee /tmp/before.txt
BenchmarkDelayingQueue_AddAfter-8         300000            256824 ns/op             520 B/op          3 allocs/op
PASS
ok      k8s.io/kubernetes/staging/src/k8s.io/client-go/util/workqueue   77.237s

After:

╰─ go test -bench=. -benchmem | tee /tmp/after.txt
BenchmarkDelayingQueue_AddAfter-8         500000              3519 ns/op             406 B/op          4 allocs/op
PASS
ok      k8s.io/kubernetes/staging/src/k8s.io/client-go/util/workqueue   2.969s

Comparison:

╰─ benchcmp /tmp/before.txt /tmp/after.txt
benchmark                             old ns/op     new ns/op     delta
BenchmarkDelayingQueue_AddAfter-8     256824        3519          -98.63%

benchmark                             old allocs     new allocs     delta
BenchmarkDelayingQueue_AddAfter-8     3              4              +33.33%

benchmark                             old bytes     new bytes     delta
BenchmarkDelayingQueue_AddAfter-8     520           406           -21.92%

I also find the container/heap-based code a bit more easy to understand. The implementation of the PriorityQueue is based on the documentation for container/heap.

Feedback definitely welcomed. This is one of my first contributions.

NONE

k8s-ci-robot · 2017-04-28T03:56:16Z

Hi @alindeman. 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 @k8s-bot 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.

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. I understand the commands that are listed here.

k8s-reviewable · 2017-04-28T03:56:17Z

This change is

grodrigues3 · 2017-05-01T20:26:44Z

@k8s-bot ok to test

alindeman · 2017-05-02T01:42:13Z

@k8s-bot gce etcd3 e2e test this

alindeman · 2017-05-03T12:10:58Z

/assign @deads2k

deads2k · 2017-05-10T12:50:23Z

staging/src/k8s.io/client-go/util/workqueue/delaying_queue.go

+	return item
+}
+func (pq waitForPriorityQueue) Peek() interface{} {
+	return pq[0]


Can you write up an example with the index field filled in? My cursory look at push, pop, and peek seem to suggest that we peek at pq[0], pop from pq[n-1], and push onto the end.

deads2k · 2017-05-10T12:53:53Z

I like the change, but I'm confused by what appears to be an inconsistent push, pop, and peek.

alindeman · 2017-05-11T00:29:44Z

Thanks for the review @deads2k.

The structure of the heap is a little confusing at first, I agree. But it is documented that the minimum element is always at index 0:

The minimum element in the tree is the root, at index 0.

Push and Pop do operate at the other 'end' of the heap, and container/heap will 'percolate' up or down the element into the correct location.

How do you best suggest I clarify this code? By example, do you mean an example test? I'd be happy to work one up if so.

deads2k · 2017-05-11T12:03:01Z

staging/src/k8s.io/client-go/util/workqueue/delaying_queue.go

-		readyEntries := 0
-		for _, entry := range q.waitingForAdd {
+		for waitingForQueue.Len() > 0 {
+			entry := waitingForQueue.Peek().(*waitFor)


So you peek at the [0] element here (which I think is the "earliest") and then you add the popped [n-1] element which I think is the latest.

@deads2k Gotcha, I agree this initially looks confusing but I think it's correct. I'll try to explain it as best I can here, but let me know if you think I can clarify or make the code more clear.

The container/heap docs state that "The minimum element in the tree is the root, at index 0."

But the container/heap#Interface docs state that the Pop method should "remove and return element Len() - 1." and that the Push method should "add x as element Len()"

Basically, the 0th element of the heap is the least element (in this case, the element with the timestamp that will occur next in time). Therefore that's the element we want to Peek. In the Pop case, though, the container/heap will have moved the minimum element to be temporarily at Len() - 1, so we pop off from that end. In the Push case, we add the new element to the 'end' of the heap and the element is percolated up to its correct position by container/heap.

I've created a simple integer-based heap on the playground that might demonstrate this more clearly.

I'd like this comment attached to the peek, push, pop method area.

@deads2k Sounds good. I've added a commit with some documentation. How do you think it reads?

deads2k · 2017-05-11T19:51:08Z

this lgtm

@liggitt want a look?

liggitt · 2017-05-11T20:25:14Z

staging/src/k8s.io/client-go/util/workqueue/delaying_queue.go

+	pq[i].index = i
+	pq[j].index = j
+}
+func (pq *waitForPriorityQueue) Push(x interface{}) {


doc that this is for the heap package to call, and heap.Push should be called instead?

liggitt · 2017-05-11T20:25:36Z

staging/src/k8s.io/client-go/util/workqueue/delaying_queue.go

+	item.index = n
+	*pq = append(*pq, item)
+}
+func (pq *waitForPriorityQueue) Pop() interface{} {


doc that this is for the heap package to call, and heap.Pop should be called instead (especially since it depends on the heap.Pop swap to make sense)

alindeman · 2017-05-11T20:43:28Z

Thanks for the review @liggitt. I've now added some documentation to the functions as well. What do you think?

liggitt · 2017-05-11T20:45:16Z

staging/src/k8s.io/client-go/util/workqueue/delaying_queue_test.go

+
+	for n := 0; n < b.N; n++ {
+		data := fmt.Sprintf("%d", n)
+		q.AddAfter(data, time.Duration(r.Int63n(int64(10*time.Minute))))


I'd like to see removal (add N items, pop N items, etc) exercised as well... the new impl must sweep every pending item on every Pop() to update indices...

liggitt · 2017-05-12T00:54:37Z

staging/src/k8s.io/client-go/util/workqueue/delaying_queue_test.go

+	for q.Len() > 0 {
+		_, _ = q.Get()
+	}
+}


thanks, curious what the effect on the benchmark was (mind updating the description)?

@liggitt 👍 I'm glad you brought it up. I've updated the original description with the new benchmark. It appears to be pretty negligible.

great, thanks

alindeman · 2017-05-14T02:03:21Z

@k8s-bot pull-kubernetes-federation-e2e-gce test this

liggitt · 2017-05-14T02:09:17Z

/lgtm

alindeman · 2017-05-14T23:29:41Z

@k8s-bot pull-kubernetes-federation-e2e-gce test this

deads2k · 2017-05-15T11:54:26Z

@k8s-bot pull-kubernetes-federation-e2e-gce test this

alindeman · 2017-05-15T12:45:04Z

@deads2k Thanks, looks like we're fully green now. Let me know if you have any other feedback.

deads2k · 2017-05-15T12:47:19Z

/approve

k8s-github-robot · 2017-05-15T12:47:23Z

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: alindeman, deads2k, liggitt

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

~~staging/src/k8s.io/client-go/OWNERS~~ [deads2k]

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

k8s-github-robot · 2017-05-15T14:06:02Z

Automatic merge from submit-queue

k8s-ci-robot added the cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. label Apr 28, 2017

k8s-ci-robot added the needs-ok-to-test Indicates a PR that requires an org member to verify it is safe to test. label Apr 28, 2017

k8s-github-robot assigned erictune and pmorie Apr 28, 2017

k8s-github-robot added size/L Denotes a PR that changes 100-499 lines, ignoring generated files. release-note-label-needed release-note-none Denotes a PR that doesn't merit a release note. and removed release-note-label-needed labels Apr 28, 2017

k8s-ci-robot removed the needs-ok-to-test Indicates a PR that requires an org member to verify it is safe to test. label May 1, 2017

k8s-ci-robot assigned deads2k May 3, 2017

deads2k reviewed May 10, 2017

View reviewed changes

deads2k reviewed May 11, 2017

View reviewed changes

liggitt reviewed May 11, 2017

View reviewed changes

alindeman force-pushed the container-heap branch from 118411e to 914a3b3 Compare May 11, 2017 20:42

liggitt reviewed May 11, 2017

View reviewed changes

alindeman force-pushed the container-heap branch from 914a3b3 to c6e3a13 Compare May 11, 2017 21:09

liggitt reviewed May 12, 2017

View reviewed changes

Adds benchmark test

21ca6c4

alindeman force-pushed the container-heap branch 2 times, most recently from f5e632a to 51dbb74 Compare May 13, 2017 20:42

Uses container/heap

dad6445

alindeman force-pushed the container-heap branch from 51dbb74 to dad6445 Compare May 13, 2017 21:21

k8s-ci-robot assigned liggitt May 14, 2017

k8s-ci-robot added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label May 14, 2017

k8s-github-robot added the approved Indicates a PR has been approved by an approver from all required OWNERS files. label May 15, 2017

k8s-github-robot merged commit 9590b94 into kubernetes:master May 15, 2017

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uses container/heap for DelayingQueue #45070

Uses container/heap for DelayingQueue #45070

alindeman commented Apr 28, 2017 •

edited

k8s-ci-robot commented Apr 28, 2017

k8s-reviewable commented Apr 28, 2017

grodrigues3 commented May 1, 2017

alindeman commented May 2, 2017

alindeman commented May 3, 2017

deads2k May 10, 2017

deads2k commented May 10, 2017

alindeman commented May 11, 2017

deads2k May 11, 2017

alindeman May 11, 2017 •

edited

deads2k May 11, 2017

alindeman May 11, 2017

deads2k commented May 11, 2017

liggitt May 11, 2017

liggitt May 11, 2017

alindeman commented May 11, 2017

liggitt May 11, 2017 •

edited

liggitt May 12, 2017 •

edited

alindeman May 13, 2017

liggitt May 14, 2017

alindeman commented May 14, 2017

liggitt commented May 14, 2017

alindeman commented May 14, 2017

deads2k commented May 15, 2017

alindeman commented May 15, 2017

deads2k commented May 15, 2017

k8s-github-robot commented May 15, 2017

k8s-github-robot commented May 15, 2017

Uses container/heap for DelayingQueue #45070

Uses container/heap for DelayingQueue #45070

Conversation

alindeman commented Apr 28, 2017 • edited

k8s-ci-robot commented Apr 28, 2017

k8s-reviewable commented Apr 28, 2017

grodrigues3 commented May 1, 2017

alindeman commented May 2, 2017

alindeman commented May 3, 2017

Choose a reason for hiding this comment

deads2k commented May 10, 2017

alindeman commented May 11, 2017

Choose a reason for hiding this comment

alindeman May 11, 2017 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

deads2k commented May 11, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

alindeman commented May 11, 2017

liggitt May 11, 2017 • edited

Choose a reason for hiding this comment

liggitt May 12, 2017 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

alindeman commented May 14, 2017

liggitt commented May 14, 2017

alindeman commented May 14, 2017

deads2k commented May 15, 2017

alindeman commented May 15, 2017

deads2k commented May 15, 2017

k8s-github-robot commented May 15, 2017

k8s-github-robot commented May 15, 2017

alindeman commented Apr 28, 2017 •

edited

alindeman May 11, 2017 •

edited

liggitt May 11, 2017 •

edited

liggitt May 12, 2017 •

edited