> On April 20, 2017, 9:35 a.m., Michael Park wrote: > > src/master/allocator/sorter/drf/sorter.hpp > > Line 263 (original), 380 (patched) > > <https://reviews.apache.org/r/57254/diff/19/?file=1693589#file1693589line482> > > > > `s/DRFComparator/compare/`? > > > > We typically name the parameters `left` and `right` > > Neil Conway wrote: > Personally I like `DRFComparator` more: it makes it clear that the > function is comparing the two nodes according to DRF. > > I renamed the parameters. > > Michael Park wrote: > `compareDRF`? I guess I was more-so saying that it's no longer an object.
Done. > On April 20, 2017, 9:35 a.m., Michael Park wrote: > > src/master/allocator/sorter/drf/sorter.cpp > > Lines 117-125 (patched) > > <https://reviews.apache.org/r/57254/diff/19/?file=1693590#file1693590line118> > > > > I think this would be cleaner to say: > > ```cpp > > auto iter = std::find_if( > > current->children.begin(), > > current->children.end(), > > [&](const Node* child) { return child->name == element; }); > > > > if (iter != current->children.end()) { > > current = *iter; > > continue; > > } > > > > /* ... */ > > ``` > > Neil Conway wrote: > Happy to discuss further, but this seems more difficult to read, > personally. I feel like we usually use an explicit `foreach` loop in similar > situations elsewhere... Per discussion, I revised the existing loop to remove the `found` variable. > On April 20, 2017, 9:35 a.m., Michael Park wrote: > > src/master/allocator/sorter/drf/sorter.cpp > > Lines 75-77 (original), 143-172 (patched) > > <https://reviews.apache.org/r/57254/diff/19/?file=1693590#file1693590line144> > > > > Kind of seems like it'd be simpler to just modify `current`. > > > > ``` > > parent->removeChild(current); > > > > // Create a node under `parent`. This internal node will become the > > new parent. > > Node* internal = new Node(current->name, parent); > > parent->addChild(internal); > > internal->allocation = current->allocation; > > CHECK_EQ(path, internal->path); > > > > // Update `current` to become the virtual leaf node. > > current->name = "."; > > current->parent = internal; > > internal->addChild(current); > > current->path = strings::join("/", parent->path, current->name); > > > > current = internal; > > ``` > > Neil Conway wrote: > Happy to discuss further, but personally I prefer the current coding > because it seems safer to avoid mutating an existing tree node "in place". > e.g., if there were other pointers to `current` that should _not_ be updated > to point to the virtual leaf node, they will now be dangling pointers (i.e., > clearly wrong) rather than now silently pointing at the virtual leaf node. Per discussion, I changed this to use the approach suggested above. - Neil ----------------------------------------------------------- This is an automatically generated e-mail. To reply, visit: https://reviews.apache.org/r/57254/#review172425 ----------------------------------------------------------- On April 20, 2017, 8:40 p.m., Neil Conway wrote: > > ----------------------------------------------------------- > This is an automatically generated e-mail. To reply, visit: > https://reviews.apache.org/r/57254/ > ----------------------------------------------------------- > > (Updated April 20, 2017, 8:40 p.m.) > > > Review request for mesos, Benjamin Bannier, Benjamin Mahler, and Michael Park. > > > Repository: mesos > > > Description > ------- > > This commit replaces the sorter's flat list of clients with a tree; the > tree represents the hierarchical relationship between sorter clients. > Each node in the tree contains a vector of pointers to child nodes. The > tree might contain nodes that do not correspond directly to sorter > clients. For example, adding clients "a/b" and "c/d" results in the > following tree: > > root > -> a > -> b > -> c > -> d > > The `sort` member function still only returns one result for each active > client in the sorter. This is implemented by ensuring that each sorter > client is associated with a leaf node in the tree (i.e., internal nodes > are not returned by `sort`). Note that it is possible for a leaf node to > be transformed into an internal node by a subsequent insertion; to > handle this case, we "implicitly" create an extra child node, which > maintains the invariant that each client is associated with a leaf > node. For example, if the client "a/b/x" is added to the tree above, the > result is: > > root > -> a > -> b > -> . > -> x > -> c > -> d > > The "." leaf node holds the allocation that has been made to the "a/b" > client itself; the "a/b" node holds the sum of all the allocations that > have been made to the subtree rooted at "a/b", which also includes > "a/b/x". The "." node is called a "virtual leaf node". > > This commit also introduces a new approach to sorting: rather than > keeping a `std::set` of sorter clients, we now keep a tree of > `std::vector`, which is sorted explicitly via `std::sort` when > necessary. The previous implementation tried to optimize the sorting > process by updating the sort order incrementally when a single sorter > client was updated; this commit removes that optimization, and instead > re-sorts the entire tree whenever a change is made that might alter the > sort order. Re-introducing a version of this optimization would make > sense in the future (MESOS-7390), but benchmarking suggests that this > commit results in a net improvement in sorter performance for > non-hierarchical clients, anyway. The performance improvement is likely > due to the introduction of a secondary hashmap that allows the leaf node > associated with a client name to be found efficiently; the previous > implementation required a linear scan of a `std::set`. > > > Diffs > ----- > > src/master/allocator/sorter/drf/metrics.cpp > 15aab32db5ca1a7a14080e9bbb7c65283be3ec20 > src/master/allocator/sorter/drf/sorter.hpp > 76329220e1115c1de7810fb69b943c78c078be59 > src/master/allocator/sorter/drf/sorter.cpp > ed54680cecb637931fc344fbcf8fd3b14cc24295 > src/master/allocator/sorter/sorter.hpp > b3029fcf7342406955760da53f1ae736769f308c > src/tests/hierarchical_allocator_tests.cpp > 33e7b455f8664858eb4f03727b076a10c80cd6e0 > src/tests/master_allocator_tests.cpp > 119e318f8a01d50e8dae5c30cf5fa6a017c3c625 > src/tests/sorter_tests.cpp 43bd85798aef0c89751b725ebf35308a5e9e997a > > > Diff: https://reviews.apache.org/r/57254/diff/22/ > > > Testing > ------- > > > Thanks, > > Neil Conway > >
