craigcondit commented on code in PR #548:
URL: https://github.com/apache/yunikorn-core/pull/548#discussion_r1265918340
##########
pkg/scheduler/objects/node_iterator.go:
##########
@@ -19,103 +19,44 @@
package objects
import (
- "math/rand"
+ "github.com/google/btree"
)
// NodeIterator iterates over a list of nodes based on the defined policy
type NodeIterator interface {
- // returns true if there are more values to iterate over
- HasNext() bool
- // returns the next node from the iterator
- Next() *Node
- // reset the iterator to a clean state
+ // Reset the iterator to a clean state
Reset()
-}
-
-// All iterators extend the base iterator
-type baseIterator struct {
- NodeIterator
- countIdx int
- size int
- nodes []*Node
-}
-
-// Reset the iterator to start from the beginning
-func (bi *baseIterator) Reset() {
- bi.countIdx = 0
-}
-
-// HasNext returns true if there is a next element in the array.
-// Returns false if there are no more elements or list is empty.
-func (bi *baseIterator) HasNext() bool {
- return !(bi.countIdx+1 > bi.size)
-}
-
-// Next returns the next element and advances to next element in array.
-// Returns nil at the end of iteration.
-func (bi *baseIterator) Next() *Node {
- if (bi.countIdx + 1) > bi.size {
- return nil
- }
- value := bi.nodes[bi.countIdx]
- bi.countIdx++
- return value
+ // ForEachNode Calls the provided function on each Node object unil it
returns false
+ ForEachNode(func(*Node) bool)
}
-// Default iterator, wraps the base iterator.
-// Iterates over the list from the start, position zero, to end.
-type defaultNodeIterator struct {
- baseIterator
+type treeIterator struct {
+ accept func(*Node) bool
+ getTree func() *btree.BTree
+ tree *btree.BTree
}
-// Create a new default iterator
-func NewDefaultNodeIterator(schedulerNodes []*Node) NodeIterator {
- it := &defaultNodeIterator{}
- it.nodes = schedulerNodes
- it.size = len(schedulerNodes)
- return it
+func (ti *treeIterator) Reset() {
+ ti.tree = ti.getTree()
}
-// Random iterator, wraps the base iterator
-// Iterates over the list from a random starting position in the list.
-// The iterator automatically wraps at the end of the list.
-type roundRobinNodeIterator struct {
- baseIterator
- startIdx int
-}
+func (ti *treeIterator) ForEachNode(f func(*Node) bool) {
+ ti.tree.Ascend(func(item btree.Item) bool {
+ node := item.(nodeRef).node
+ if ti.accept(node) {
+ return f(node)
+ }
-// The starting point is randomised in the slice.
-func NewRoundRobinNodeIterator(schedulerNodes []*Node) NodeIterator {
- it := &roundRobinNodeIterator{}
- it.nodes = schedulerNodes
- it.size = len(schedulerNodes)
- if it.size > 0 {
- it.startIdx = rand.Intn(it.size)
- }
- return it
+ return true
+ })
}
-// Next returns the next element and advances to next element in array.
-// Returns nil at the end of iteration.
-func (ri *roundRobinNodeIterator) Next() *Node {
- // prevent panic on Next when slice is empty
- if (ri.countIdx + 1) > ri.size {
- return nil
- }
-
- // after reset initialize the rand seed based on number of nodes.
- if ri.startIdx == -1 {
- ri.startIdx = rand.Intn(ri.size)
+func NewTreeIterator(accept func(*Node) bool, getTree func() *btree.BTree)
*treeIterator {
+ ti := &treeIterator{
+ getTree: getTree,
+ accept: accept,
}
-
- idx := (ri.countIdx + ri.startIdx) % ri.size
- value := ri.nodes[idx]
- ri.countIdx++
- return value
-}
-
-func (ri *roundRobinNodeIterator) Reset() {
- ri.countIdx = 0
- ri.startIdx = -1
+ ti.tree = getTree()
Review Comment:
We can do an optimization here by not calling getTree() and storing the
result. Instead, just do it in ForEachNode():
Instead of ti.tree.Ascend(...) use ti.getTree().Ascend(...).
This means we only compute the tree if ForEachNode is actually called.
##########
pkg/scheduler/objects/node_iterator.go:
##########
@@ -19,103 +19,44 @@
package objects
import (
- "math/rand"
+ "github.com/google/btree"
)
// NodeIterator iterates over a list of nodes based on the defined policy
type NodeIterator interface {
- // returns true if there are more values to iterate over
- HasNext() bool
- // returns the next node from the iterator
- Next() *Node
- // reset the iterator to a clean state
+ // Reset the iterator to a clean state
Reset()
-}
-
-// All iterators extend the base iterator
-type baseIterator struct {
- NodeIterator
- countIdx int
- size int
- nodes []*Node
-}
-
-// Reset the iterator to start from the beginning
-func (bi *baseIterator) Reset() {
- bi.countIdx = 0
-}
-
-// HasNext returns true if there is a next element in the array.
-// Returns false if there are no more elements or list is empty.
-func (bi *baseIterator) HasNext() bool {
- return !(bi.countIdx+1 > bi.size)
-}
-
-// Next returns the next element and advances to next element in array.
-// Returns nil at the end of iteration.
-func (bi *baseIterator) Next() *Node {
- if (bi.countIdx + 1) > bi.size {
- return nil
- }
- value := bi.nodes[bi.countIdx]
- bi.countIdx++
- return value
+ // ForEachNode Calls the provided function on each Node object unil it
returns false
+ ForEachNode(func(*Node) bool)
}
-// Default iterator, wraps the base iterator.
-// Iterates over the list from the start, position zero, to end.
-type defaultNodeIterator struct {
- baseIterator
+type treeIterator struct {
+ accept func(*Node) bool
+ getTree func() *btree.BTree
+ tree *btree.BTree
}
-// Create a new default iterator
-func NewDefaultNodeIterator(schedulerNodes []*Node) NodeIterator {
- it := &defaultNodeIterator{}
- it.nodes = schedulerNodes
- it.size = len(schedulerNodes)
- return it
+func (ti *treeIterator) Reset() {
Review Comment:
The Reset() method and all callers can be removed as this is a No-Op on the
tree.
##########
pkg/scheduler/objects/node_iterator.go:
##########
@@ -19,103 +19,44 @@
package objects
import (
- "math/rand"
+ "github.com/google/btree"
)
// NodeIterator iterates over a list of nodes based on the defined policy
type NodeIterator interface {
- // returns true if there are more values to iterate over
- HasNext() bool
- // returns the next node from the iterator
- Next() *Node
- // reset the iterator to a clean state
+ // Reset the iterator to a clean state
Reset()
-}
-
-// All iterators extend the base iterator
-type baseIterator struct {
- NodeIterator
- countIdx int
- size int
- nodes []*Node
-}
-
-// Reset the iterator to start from the beginning
-func (bi *baseIterator) Reset() {
- bi.countIdx = 0
-}
-
-// HasNext returns true if there is a next element in the array.
-// Returns false if there are no more elements or list is empty.
-func (bi *baseIterator) HasNext() bool {
- return !(bi.countIdx+1 > bi.size)
-}
-
-// Next returns the next element and advances to next element in array.
-// Returns nil at the end of iteration.
-func (bi *baseIterator) Next() *Node {
- if (bi.countIdx + 1) > bi.size {
- return nil
- }
- value := bi.nodes[bi.countIdx]
- bi.countIdx++
- return value
+ // ForEachNode Calls the provided function on each Node object unil it
returns false
+ ForEachNode(func(*Node) bool)
}
-// Default iterator, wraps the base iterator.
-// Iterates over the list from the start, position zero, to end.
-type defaultNodeIterator struct {
- baseIterator
+type treeIterator struct {
+ accept func(*Node) bool
+ getTree func() *btree.BTree
+ tree *btree.BTree
}
-// Create a new default iterator
-func NewDefaultNodeIterator(schedulerNodes []*Node) NodeIterator {
- it := &defaultNodeIterator{}
- it.nodes = schedulerNodes
- it.size = len(schedulerNodes)
- return it
+func (ti *treeIterator) Reset() {
+ ti.tree = ti.getTree()
}
-// Random iterator, wraps the base iterator
-// Iterates over the list from a random starting position in the list.
-// The iterator automatically wraps at the end of the list.
-type roundRobinNodeIterator struct {
- baseIterator
- startIdx int
-}
+func (ti *treeIterator) ForEachNode(f func(*Node) bool) {
Review Comment:
This function could use documentation, especially wrt the passed-in function.
##########
pkg/scheduler/objects/node_iterator.go:
##########
@@ -19,103 +19,44 @@
package objects
import (
- "math/rand"
+ "github.com/google/btree"
)
// NodeIterator iterates over a list of nodes based on the defined policy
type NodeIterator interface {
- // returns true if there are more values to iterate over
- HasNext() bool
- // returns the next node from the iterator
- Next() *Node
- // reset the iterator to a clean state
+ // Reset the iterator to a clean state
Reset()
-}
-
-// All iterators extend the base iterator
-type baseIterator struct {
- NodeIterator
- countIdx int
- size int
- nodes []*Node
-}
-
-// Reset the iterator to start from the beginning
-func (bi *baseIterator) Reset() {
- bi.countIdx = 0
-}
-
-// HasNext returns true if there is a next element in the array.
-// Returns false if there are no more elements or list is empty.
-func (bi *baseIterator) HasNext() bool {
- return !(bi.countIdx+1 > bi.size)
-}
-
-// Next returns the next element and advances to next element in array.
-// Returns nil at the end of iteration.
-func (bi *baseIterator) Next() *Node {
- if (bi.countIdx + 1) > bi.size {
- return nil
- }
- value := bi.nodes[bi.countIdx]
- bi.countIdx++
- return value
+ // ForEachNode Calls the provided function on each Node object unil it
returns false
Review Comment:
Nit: typo (unil -> until)
##########
pkg/scheduler/objects/node_iterator.go:
##########
@@ -19,103 +19,44 @@
package objects
import (
- "math/rand"
+ "github.com/google/btree"
)
// NodeIterator iterates over a list of nodes based on the defined policy
type NodeIterator interface {
- // returns true if there are more values to iterate over
- HasNext() bool
- // returns the next node from the iterator
- Next() *Node
- // reset the iterator to a clean state
+ // Reset the iterator to a clean state
Review Comment:
Remove as this is now a no-op for the only implementation. Calling it has no
effect on the result of ForEachNode().
##########
pkg/scheduler/objects/node_collection.go:
##########
@@ -154,43 +163,15 @@ func (nc *baseNodeCollection) GetNodes() []*Node {
// Create an ordered node iterator for unreserved nodes based on the sort
policy set for this collection.
// The iterator is nil if there are no unreserved nodes available.
func (nc *baseNodeCollection) GetNodeIterator() NodeIterator {
- return nc.getNodeIteratorInternal(func(node *Node) bool {
- return !node.IsReserved()
- })
+ nc.unreservedIterator.Reset()
Review Comment:
Remove Reset() call as it doesn't do anything.
##########
pkg/scheduler/objects/node_iterator.go:
##########
@@ -19,103 +19,44 @@
package objects
import (
- "math/rand"
+ "github.com/google/btree"
)
// NodeIterator iterates over a list of nodes based on the defined policy
type NodeIterator interface {
- // returns true if there are more values to iterate over
- HasNext() bool
- // returns the next node from the iterator
- Next() *Node
- // reset the iterator to a clean state
+ // Reset the iterator to a clean state
Reset()
-}
-
-// All iterators extend the base iterator
-type baseIterator struct {
- NodeIterator
- countIdx int
- size int
- nodes []*Node
-}
-
-// Reset the iterator to start from the beginning
-func (bi *baseIterator) Reset() {
- bi.countIdx = 0
-}
-
-// HasNext returns true if there is a next element in the array.
-// Returns false if there are no more elements or list is empty.
-func (bi *baseIterator) HasNext() bool {
- return !(bi.countIdx+1 > bi.size)
-}
-
-// Next returns the next element and advances to next element in array.
-// Returns nil at the end of iteration.
-func (bi *baseIterator) Next() *Node {
- if (bi.countIdx + 1) > bi.size {
- return nil
- }
- value := bi.nodes[bi.countIdx]
- bi.countIdx++
- return value
+ // ForEachNode Calls the provided function on each Node object unil it
returns false
+ ForEachNode(func(*Node) bool)
}
-// Default iterator, wraps the base iterator.
-// Iterates over the list from the start, position zero, to end.
-type defaultNodeIterator struct {
- baseIterator
+type treeIterator struct {
+ accept func(*Node) bool
+ getTree func() *btree.BTree
+ tree *btree.BTree
}
-// Create a new default iterator
-func NewDefaultNodeIterator(schedulerNodes []*Node) NodeIterator {
- it := &defaultNodeIterator{}
- it.nodes = schedulerNodes
- it.size = len(schedulerNodes)
- return it
+func (ti *treeIterator) Reset() {
+ ti.tree = ti.getTree()
}
-// Random iterator, wraps the base iterator
-// Iterates over the list from a random starting position in the list.
-// The iterator automatically wraps at the end of the list.
-type roundRobinNodeIterator struct {
- baseIterator
- startIdx int
-}
+func (ti *treeIterator) ForEachNode(f func(*Node) bool) {
+ ti.tree.Ascend(func(item btree.Item) bool {
+ node := item.(nodeRef).node
+ if ti.accept(node) {
+ return f(node)
+ }
-// The starting point is randomised in the slice.
-func NewRoundRobinNodeIterator(schedulerNodes []*Node) NodeIterator {
- it := &roundRobinNodeIterator{}
- it.nodes = schedulerNodes
- it.size = len(schedulerNodes)
- if it.size > 0 {
- it.startIdx = rand.Intn(it.size)
- }
- return it
+ return true
+ })
}
-// Next returns the next element and advances to next element in array.
-// Returns nil at the end of iteration.
-func (ri *roundRobinNodeIterator) Next() *Node {
- // prevent panic on Next when slice is empty
- if (ri.countIdx + 1) > ri.size {
- return nil
- }
-
- // after reset initialize the rand seed based on number of nodes.
- if ri.startIdx == -1 {
- ri.startIdx = rand.Intn(ri.size)
+func NewTreeIterator(accept func(*Node) bool, getTree func() *btree.BTree)
*treeIterator {
+ ti := &treeIterator{
+ getTree: getTree,
+ accept: accept,
}
-
- idx := (ri.countIdx + ri.startIdx) % ri.size
- value := ri.nodes[idx]
- ri.countIdx++
- return value
-}
-
-func (ri *roundRobinNodeIterator) Reset() {
- ri.countIdx = 0
- ri.startIdx = -1
+ ti.tree = getTree()
Review Comment:
Alternatively, we could compute the tree here and simply iterate the same
copy of it each time. We should not do both, however.
##########
pkg/scheduler/objects/node_collection.go:
##########
@@ -154,43 +163,15 @@ func (nc *baseNodeCollection) GetNodes() []*Node {
// Create an ordered node iterator for unreserved nodes based on the sort
policy set for this collection.
// The iterator is nil if there are no unreserved nodes available.
func (nc *baseNodeCollection) GetNodeIterator() NodeIterator {
- return nc.getNodeIteratorInternal(func(node *Node) bool {
- return !node.IsReserved()
- })
+ nc.unreservedIterator.Reset()
+ return nc.unreservedIterator
}
// Create an ordered node iterator for all nodes based on the sort policy set
for this collection.
// The iterator is nil if there are no nodes available.
func (nc *baseNodeCollection) GetFullNodeIterator() NodeIterator {
- return nc.getNodeIteratorInternal(func(node *Node) bool {
- return true
- })
-}
-
-func (nc *baseNodeCollection) getNodeIteratorInternal(allow func(*Node) bool)
NodeIterator {
- sortingStart := time.Now()
- tree := nc.cloneSortedNodes()
-
- length := tree.Len()
- if length == 0 {
- return nil
- }
-
- nodes := make([]*Node, 0, length)
- tree.Ascend(func(item btree.Item) bool {
- node := item.(nodeRef).node
- if allow(node) {
- nodes = append(nodes, node)
- }
- return true
- })
- metrics.GetSchedulerMetrics().ObserveNodeSortingLatency(sortingStart)
-
- if len(nodes) == 0 {
- return nil
- }
-
- return NewDefaultNodeIterator(nodes)
+ nc.fullIterator.Reset()
Review Comment:
Remove Reset() call as it doesn't do anything.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
