-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/70497/
-----------------------------------------------------------
(Updated April 30, 2019, 6:36 p.m.)
Review request for mesos, Andrei Sekretenko and Benjamin Mahler.
Changes
-------
Rebased and updated benchmark result.
Bugs: MESOS-9725
https://issues.apache.org/jira/browse/MESOS-9725
Repository: mesos
Description
-------
This patch optimizes the random sorter by avoiding
clients shuffling. The sorter now does random sampling
as the caller asks for the next client.
The random sampling works in two steps. Clients with the same
relative weights are grouped together. In the first phase, we
randomly pick a group of clients. This requires the generation
of a weighted random number. In the second phase, a client within
the group is picked. Since all clients in the group have the same
weight, this can be done in constant time. This two step approach
minimizes the cost of generating weighted random number which
could be expensive given the size of the weights.
Diffs (updated)
-----
src/master/allocator/sorter/random/sorter.hpp
55e22d7705f163fe47d5aa47416ee0714c5a87c0
src/master/allocator/sorter/random/sorter.cpp
813f5b55d38dd9fa822de53ee944c3f72251a69d
Diff: https://reviews.apache.org/r/70497/diff/2/
Changes: https://reviews.apache.org/r/70497/diff/1-2/
Testing (updated)
-------
make check
Benchmarking: ran
`QuotaParam/BENCHMARK_HierarchicalAllocator_WithQuotaParam.LargeAndSmallQuota/5`
with optimized build
Before:
Added 3000 agents in 101.884509ms
Added 3000 frameworks in 19.711779311secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks, with random sorter
Made 3856 allocations in 16.283607645secs
Made 0 allocation in 16.31197771secs
After r/70419, r/70576 and r/70497 :
Added 3000 agents in 87.147084ms
Added 3000 frameworks in 19.246494668secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks, with random sorter
Made 3872 allocations in 12.230518989secs
Made 0 allocation in 12.012211914secs
Thanks,
Meng Zhu
