mesos-reviews mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Benjamin Mahler <bmah...@apache.org>
Subject Re: Review Request 70497: Optimize the random sorter with random sampling.
Date Wed, 01 May 2019 20:02:51 GMT

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/70497/#review214981
-----------------------------------------------------------



This was a pretty nice read, thanks!

Mostly just left some readablity suggestions. The only thing that's a bit worrying is the
double precision equality bucketing.


src/master/allocator/sorter/random/sorter.hpp
Line 146 (original), 146 (patched)
<https://reviews.apache.org/r/70497/#comment301264>

    How about `clientsByWeight()` here and elsewhere?



src/master/allocator/sorter/random/sorter.hpp
Line 164 (original), 163 (patched)
<https://reviews.apache.org/r/70497/#comment301263>

    double as a map key scares me.. :)
    
    the double multiplication to produce these keys is a bit concerning, I wonder if we should
do something to keep only a significant number of digits, or CHECK that all nodes at same
level with same ancestor weights are in the same bucket (but.. if that check fails we're screwed)



src/master/allocator/sorter/random/sorter.cpp
Lines 629 (patched)
<https://reviews.apache.org/r/70497/#comment301253>

    Won't show up in benchmarks since these will be 1 item vectors since we don't benchmark
mixed weights, especially since they're usually small, but might as well reserve:
    
    weights.reserve(weightToClients.size());
    clients.reserve(weightToClients.size());



src/master/allocator/sorter/random/sorter.cpp
Lines 634 (patched)
<https://reviews.apache.org/r/70497/#comment301262>

    Can you do this in the initializer list?



src/master/allocator/sorter/random/sorter.cpp
Lines 647-648 (patched)
<https://reviews.apache.org/r/70497/#comment301255>

    Can we frame step 1 here and below as choosing a bucket? Bucket seems to convey to the
reader that they are bucketed by weight.



src/master/allocator/sorter/random/sorter.cpp
Lines 650-652 (patched)
<https://reviews.apache.org/r/70497/#comment301256>

    Ditto here, I think this would read better if it talks about the chosen bucket rather
than vectors of clients and clients[i] vectors?
    
    vector is the container but bucket seems like the logical way to think about it, clients
are bucketed by weight



src/master/allocator/sorter/random/sorter.cpp
Lines 658-661 (patched)
<https://reviews.apache.org/r/70497/#comment301258>

    How about:
    
    ```
      // Step 1: Pick a client bucket.
      size_t bucketIndex =
        std::discrete_distribution<>(weightBuckets.begin(), weightBuckets.end())(*generator);
        
      vector<Node*>& clientBucket = clientBuckets[bucketIndex];
      
      // Step 2: Pick a client from the bucket.
      size_t clientIndex =
        std::uniform_int_distribution<>(0, clientBucket.size() - 1)(*generator);
        
      const Node* client = clientBucket[clientIndex];
    ```



src/master/allocator/sorter/random/sorter.cpp
Lines 675 (patched)
<https://reviews.apache.org/r/70497/#comment301259>

    maybe this is more readable since it shows the swap-with-last intent more clearly?
    
    ```
    std::swap(clientBucket[clientIndex], clientBucket[clientBucket.size() - 1]);
    clientBucket.pop_back();
    ```
    
    There won't be any efficiency difference either from the current code which avoids moving
the item into the last position.



src/master/allocator/sorter/random/sorter.cpp
Lines 678-684 (patched)
<https://reviews.apache.org/r/70497/#comment301260>

    Ditto here with std::swap to show the swap-with-last intent, note that it will std::move
them so won't be any less efficient.



src/master/allocator/sorter/random/sorter.cpp
Lines 686 (patched)
<https://reviews.apache.org/r/70497/#comment301261>

    hm.. you should be able to just do:
    
    ```
    return cref(chosenClient->clientPath());
    ```
    
    https://en.cppreference.com/w/cpp/utility/functional/ref


- Benjamin Mahler


On May 1, 2019, 1:36 a.m., Meng Zhu wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/70497/
> -----------------------------------------------------------
> 
> (Updated May 1, 2019, 1:36 a.m.)
> 
> 
> Review request for mesos, Andrei Sekretenko and Benjamin Mahler.
> 
> 
> 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
> -----
> 
>   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/
> 
> 
> Testing
> -------
> 
> 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
> 
>


Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message