scheduler: Use heap-sort instead of quickselect#1550
Merged
LK4D4 merged 1 commit intomoby:masterfrom Sep 20, 2016
Merged
Conversation
Collaborator
Author
|
Benchmark results: As expected, this is a big improvement if there are many more nodes than tasks being scheduled. Otherwise, the difference is minor. |
Current coverage is 54.30% (diff: 92.00%)@@ master #1550 diff @@
==========================================
Files 82 82
Lines 13528 13539 +11
Methods 0 0
Messages 0 0
Branches 0 0
==========================================
+ Hits 7305 7353 +48
+ Misses 5233 5207 -26
+ Partials 990 979 -11
|
The HA scheduling algorithm introduced code that built a slice of all nodes meeting the constraints, then selected the k best nodes from that slice. Building the slice can be expensive if there are a lot of nodes. To improve performance, we can build a max-heap of nodes and pop all of the elements to perform a heap sort. We never need to have more than k items in the heap at any time, since the heap enables a trivial optimization to check if a node is "better" than the root of the heap. If it isn't, we can skip that node, and if it is, we can replace the root of the heap with it. This approach needs less memory allocation with k << len(nodes). It also removes the dependency on quickselect. Thanks to LK4D4 for the idea. Signed-off-by: Aaron Lehmann <aaron.lehmann@docker.com>
c6d3ee5 to
6c8cb80
Compare
|
|
||
| // findBestNodes returns n nodes (or < n if fewer nodes are available) that | ||
| // rank best (lowest) according to the sorting function. | ||
| func (ns *nodeSet) findBestNodes(n int, meetsConstraints func(*NodeInfo) bool, nodeLess func(*NodeInfo, *NodeInfo) bool) []NodeInfo { |
Contributor
There was a problem hiding this comment.
Just to confirm: Is this argument n the same as k in the above description, when findBestNodes actually gets called?
Contributor
|
LGTM |
stevvooe
reviewed
Sep 19, 2016
| // If there are fewer then n nodes in the heap, we add this | ||
| // node if it meets the constraints. Otherwise, the heap has | ||
| // n nodes, and if this node is better than the worst node in | ||
| // the heap, we replace the worst node and then fix the heap. |
Contributor
There was a problem hiding this comment.
Does this imply that we have a minHeap, rather than a maxHeap?
Contributor
There was a problem hiding this comment.
I think in this case "less" means better, so for all the nodes in the heap, the worst ("largest") is at the top.
Collaborator
Author
There was a problem hiding this comment.
The comparator is defined so that Less(a, b) is true if a is better than b.
So the "greatest" node is the least favored, and that's the one we want at the root of our heap so we can easily check if we can replace it with a better one.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
6 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
The HA scheduling algorithm introduced code that built a slice of all
nodes meeting the constraints, then selected the k best nodes from that
slice.
Building the slice can be expensive if there are a lot of nodes.
To improve performance, we can build a max-heap of nodes and pop all of
the elements to perform a heap sort. We never need to have more than k
items in the heap at any time, since the heap enables a trivial
optimization to check if a node is "better" than the root of the heap.
If it isn't, we can skip that node, and if it is, we can replace the
root of the heap with it.
This approach needs less memory allocation with k << len(nodes).
It also removes the dependency on quickselect.
Thanks to @LK4D4 for the idea.