> On 十月 21, 2016, 8:23 p.m., Benjamin Mahler wrote:
> > Ship It!
>
> Guangya Liu wrote:
> Do you have any comments on the test result? Shall we use a small range
> to reduce the time of this? The `contains` for a boundry case is using 38+s.
>
> ```
> [ RUN ]
> ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/5
> Took 38.23282secs to perform 1 'superset.contains(subset)' operations on
> superset resources ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13...
> contains subset resources ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13...
> [ OK ]
> ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/5 (38279 ms)
> ```
>
> Checked the API of `operator<=` for `Value::Ranges`, and found it is
> already doing some optimization for this: return false if got one non matched
> range, but as my case is a boundry case, so the elapse time is a bit long.
>
> ```
> bool operator<=(const Value::Ranges& _left, const Value::Ranges& _right)
> {
> Value::Ranges left;
> coalesce(&left, {_left});
>
> Value::Ranges right;
> coalesce(&right, {_right});
>
> for (int i = 0; i < left.range_size(); i++) {
> // Make sure this range is a subset of a range in right.
> bool matched = false;
> for (int j = 0; j < right.range_size(); j++) {
> if (left.range(i).begin() >= right.range(j).begin() &&
> left.range(i).end() <= right.range(j).end()) {
> matched = true;
> break;
> }
> }
> if (!matched) {
> return false;
> }
> }
>
> return true;
> }
> ```
>
> Benjamin Mahler wrote:
> How about the following?
>
> ```
> bool operator<=(const Value::Ranges& _left, const Value::Ranges& _right)
> {
> Value::Ranges left;
> coalesce(&left, {_left});
>
> Value::Ranges right;
> coalesce(&right, {_right});
>
> IntervalSet<uint64_t> leftSet = rangesToIntervalSet(left);
> IntervalSet<uint64_t> rightSet = rangesToIntervalSet(right);
>
> return rightSet.contains(leftSet);
> }
> ```
>
> Benjamin Mahler wrote:
> I'll decrease the size of the port ranges until we can figure out how to
> improve the performance.
@Ben, the solution that you proposed works well with the boundry case: `32000
ranges contains 32000 ranges`, but it does not work well for other cases,
please check my test result below:
Without your patch:
```
[ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/2 (11
ms)
[ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/3
Took 1.891727secs to perform 100 'superset.contains(subset)' operations on
superset resources ports(*):[1-64000] contains subset resources ports(*):[1-1,
3-3, 5-5, 7-7, 9-9, 11-11, 13-13...
[ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/3
(1915 ms)
[ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/4
Took 1.197172secs to perform 50 'superset.contains(subset)' operations on
superset resources ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13... contains
subset resources ports(*):[1-64000]
[ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/4
(1219 ms)
[ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/5
Took 32.978883secs to perform 1 'superset.contains(subset)' operations on
superset resources ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13... contains
subset resources ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13...
[ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/5
(33030 ms)
```
With your patch:
```
[ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/2 (9
ms)
[ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/3
Took 14.528628secs to perform 100 'superset.contains(subset)' operations on
superset resources ports(*):[1-64000] contains subset resources ports(*):[1-1,
3-3, 5-5, 7-7, 9-9, 11-11, 13-13...
[ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/3
(14554 ms)
[ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/4
Took 7.538167secs to perform 50 'superset.contains(subset)' operations on
superset resources ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13... contains
subset resources ports(*):[1-64000]
[ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/4
(7563 ms)
[ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/5
Took 294980us to perform 1 'superset.contains(subset)' operations on superset
resources ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13... contains subset
resources ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13...
[ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/5
(343 ms)
```
>From above test result, the current logic works well for some other cases as
>it can always return early when there are no matched ranges except the boundry
>case. I think that we may need to add some benchmark test to for
>`IntervalSet.contains`, `rangesToIntervalSet` to see if there are any
>bottle-neck that can be improved.
- Guangya
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/50551/#review153595
-----------------------------------------------------------
On 十月 21, 2016, 11:27 p.m., Guangya Liu wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/50551/
> -----------------------------------------------------------
>
> (Updated 十月 21, 2016, 11:27 p.m.)
>
>
> Review request for mesos, Benjamin Mahler, Klaus Ma, and Jiang Yan Xu.
>
>
> Bugs: MESOS-5700
> https://issues.apache.org/jira/browse/MESOS-5700
>
>
> Repository: mesos
>
>
> Description
> -------
>
> Added benchmark test for `Resources::contains`.
>
>
> Diffs
> -----
>
> src/tests/resources_tests.cpp 27c52e72764fc6db0a510c367a9659596e723504
>
> Diff: https://reviews.apache.org/r/50551/diff/
>
>
> Testing
> -------
>
> make
> make check
>
> ```
> ./bin/mesos-tests.sh --benchmark
> --gtest_filter="*Resources_Contains_BENCHMARK_Test.Contains/*"
> [==========] Running 9 tests from 1 test case.
> [----------] Global test environment set-up.
> [----------] 9 tests from ResourcesContains/Resources_Contains_BENCHMARK_Test
> [ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/0
> Took 16723us to perform 5000 'superset.contains(subset)' operations on
> superset resources cpus(*):1; gpus(*):1; mem(*):128; disk(*):256 contains
> subset resources cpus(*):1; mem(*):128
> [ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/0
> (17 ms)
> [ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/1
> Took 9675us to perform 5000 'superset.contains(subset)' operations on
> superset resources cpus(*):1; mem(*):128 contains subset resources cpus(*):1;
> gpus(*):1; mem(*):128; disk(*):256
> [ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/1
> (9 ms)
> [ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/2
> Took 10428us to perform 5000 'superset.contains(subset)' operations on
> superset resources cpus(*):1; mem(*):128 contains subset resources cpus(*):1;
> mem(*):128
> [ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/2
> (11 ms)
> [ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/3
> Took 2.016892secs to perform 100 'superset.contains(subset)' operations on
> superset resources ports(*):[1-64000] contains subset resources
> ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13...
> [ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/3
> (2041 ms)
> [ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/4
> Took 1.322314secs to perform 50 'superset.contains(subset)' operations on
> superset resources ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13...
> contains subset resources ports(*):[1-64000]
> [ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/4
> (1343 ms)
> [ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/5
> Took 38.23282secs to perform 1 'superset.contains(subset)' operations on
> superset resources ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13...
> contains subset resources ports(*):[1-1, 3-3, 5-5, 7-7, 9-9, 11-11, 13-13...
> [ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/5
> (38279 ms)
> [ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/6
> Took 2.087117secs to perform 100 'superset.contains(subset)' operations on
> superset resources cpus(*):1; gpus(*):1; mem(*):128; disk(*):256; ...
> contains subset resources cpus(*):1; mem(*):128; ports(*):[1-1, 3-3, 5-5,...
> [ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/6
> (2111 ms)
> [ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/7
> Took 327807us to perform 50 'superset.contains(subset)' operations on
> superset resources cpus(*):1; mem(*):128; ports(*):[1-1, 3-3, 5-5,...
> contains subset resources cpus(*):1; gpus(*):1; mem(*):128; disk(*):256; ...
> [ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/7
> (351 ms)
> [ RUN ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/8
> Took 38.7907secs to perform 1 'superset.contains(subset)' operations on
> superset resources cpus(*):1; mem(*):128; ports(*):[1-1, 3-3, 5-5,...
> contains subset resources cpus(*):1; mem(*):128; ports(*):[1-1, 3-3, 5-5,...
> [ OK ] ResourcesContains/Resources_Contains_BENCHMARK_Test.Contains/8
> (38839 ms)
> [----------] 9 tests from ResourcesContains/Resources_Contains_BENCHMARK_Test
> (83002 ms total)
>
> [----------] Global test environment tear-down
> [==========] 9 tests from 1 test case ran. (83017 ms total)
> [ PASSED ] 9 tests.
> ```
>
>
> Thanks,
>
> Guangya Liu
>
>
