Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2591533002:
cc: Change RTree nodes container to be a vector (with reserve). (Closed)
Descriptioncc: Change RTree nodes container to be a vector (with reserve).
This patch changes the nodes container in the rtree to use a vector.
In order to preserve the consistent access to elements, it reserves the
vector to the needed capacity. The wasted space is <= 6 elements.
Added a unittest to verify the reserve path is correct for up to 1000
rects. However, locally I've tested this for up to 520k rects (and
still testing for up to 1m rects).
The perf results from N7v2 are below.
Before the patch:
[ RUN ] RTreePerfTest.Construct
*RESULT rtree_construct: 100= 75723.8671875 runs/s
*RESULT rtree_construct: 1000= 11985 runs/s
*RESULT rtree_construct: 10000= 715.2415161132812 runs/s
*RESULT rtree_construct: 100000= 54.19050216674805 runs/s
[ OK ] RTreePerfTest.Construct (8243 ms)
[ RUN ] RTreePerfTest.Search
*RESULT rtree_search: 100= 352105 runs/s
*RESULT rtree_search: 1000= 97542.0234375 runs/s
*RESULT rtree_search: 10000= 10274.0595703125 runs/s
*RESULT rtree_search: 100000= 866.167236328125 runs/s
[ OK ] RTreePerfTest.Search (8122 ms)
After the patch:
[ RUN ] RTreePerfTest.Construct
*RESULT rtree_construct: 100= 112420 runs/s (+48%)
*RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%)
*RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%)
*RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%)
[ OK ] RTreePerfTest.Construct (8340 ms)
[ RUN ] RTreePerfTest.Search
*RESULT rtree_search: 100= 365225 runs/s
*RESULT rtree_search: 1000= 98002.0078125 runs/s
*RESULT rtree_search: 10000= 10344.048828125 runs/s
*RESULT rtree_search: 100000= 866.0883178710938 runs/s
[ OK ] RTreePerfTest.Search (8092 ms)
BUG=674169
R=danakj@chromium.org, dskiba@chromium.org
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel
Committed: https://crrev.com/b80d44193d48fb38e2fffa7c3f16d89979351371
Cr-Commit-Position: refs/heads/master@{#439686}
Patch Set 1 #Patch Set 2 : cont: update #
Total comments: 6
Patch Set 3 : comments #Patch Set 4 : compile fix #
Messages
Total messages: 22 (13 generated)
Description was changed from ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 200k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org ========== to ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 200k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel ==========
Behold, a patch!
LGTM https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree.cc File cc/base/rtree.cc (right): https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree.cc#newcode24 cc/base/rtree.cc:24: // existing nodes, so verify that capacity < size. u mean > ? https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree.h File cc/base/rtree.h (right): https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree.h#newcode82 cc/base/rtree.h:82: kMinChildren; clang format why https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree_unittest.cc File cc/base/rtree_unittest.cc (right): https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree_unittest.... cc/base/rtree_unittest.cc:15: // is correct. (This test would DCHECK if broken). say where it would
Whats the wasted space now in the scenarios from the bug?
Description was changed from ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 200k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel ========== to ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 440k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel ==========
https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree.cc File cc/base/rtree.cc (right): https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree.cc#newcode24 cc/base/rtree.cc:24: // existing nodes, so verify that capacity < size. On 2016/12/19 22:20:50, danakj_OOO_and_slow wrote: > u mean > ? Err yes, thx https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree.h File cc/base/rtree.h (right): https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree.h#newcode82 cc/base/rtree.h:82: kMinChildren; On 2016/12/19 22:20:50, danakj_OOO_and_slow wrote: > clang format why v_v https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree_unittest.cc File cc/base/rtree_unittest.cc (right): https://codereview.chromium.org/2591533002/diff/20001/cc/base/rtree_unittest.... cc/base/rtree_unittest.cc:15: // is correct. (This test would DCHECK if broken). On 2016/12/19 22:20:50, danakj_OOO_and_slow wrote: > say where it would Done.
Description was changed from ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 440k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel ========== to ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 500k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel ==========
Description was changed from ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 500k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel ========== to ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 450k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel ==========
Description was changed from ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 450k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel ========== to ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 520k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel ==========
The CQ bit was checked by vmpstr@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from danakj@chromium.org Link to the patchset: https://codereview.chromium.org/2591533002/#ps40001 (title: "comments")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: win_chromium_compile_dbg_ng on master.tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_comp...)
The CQ bit was checked by vmpstr@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from danakj@chromium.org Link to the patchset: https://codereview.chromium.org/2591533002/#ps60001 (title: "compile fix")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
CQ is committing da patch.
Bot data: {"patchset_id": 60001, "attempt_start_ts": 1482195332560660,
"parent_rev": "c12ccfe11396646fffdfd11c89607f65182902ff", "commit_rev":
"5e30fa66f3bb0bf5c7d4c5c995d54e86a81e8f04"}
Message was sent while issue was closed.
Description was changed from ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 520k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel ========== to ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 520k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel Review-Url: https://codereview.chromium.org/2591533002 ==========
Message was sent while issue was closed.
Committed patchset #4 (id:60001)
Message was sent while issue was closed.
Description was changed from ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 520k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel Review-Url: https://codereview.chromium.org/2591533002 ========== to ========== cc: Change RTree nodes container to be a vector (with reserve). This patch changes the nodes container in the rtree to use a vector. In order to preserve the consistent access to elements, it reserves the vector to the needed capacity. The wasted space is <= 6 elements. Added a unittest to verify the reserve path is correct for up to 1000 rects. However, locally I've tested this for up to 520k rects (and still testing for up to 1m rects). The perf results from N7v2 are below. Before the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 75723.8671875 runs/s *RESULT rtree_construct: 1000= 11985 runs/s *RESULT rtree_construct: 10000= 715.2415161132812 runs/s *RESULT rtree_construct: 100000= 54.19050216674805 runs/s [ OK ] RTreePerfTest.Construct (8243 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 352105 runs/s *RESULT rtree_search: 1000= 97542.0234375 runs/s *RESULT rtree_search: 10000= 10274.0595703125 runs/s *RESULT rtree_search: 100000= 866.167236328125 runs/s [ OK ] RTreePerfTest.Search (8122 ms) After the patch: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 112420 runs/s (+48%) *RESULT rtree_construct: 1000= 13482.32421875 runs/s (+12%) *RESULT rtree_construct: 10000= 666.6328125 runs/s (-7%) *RESULT rtree_construct: 100000= 55.98017501831055 runs/s (+3%) [ OK ] RTreePerfTest.Construct (8340 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 365225 runs/s *RESULT rtree_search: 1000= 98002.0078125 runs/s *RESULT rtree_search: 10000= 10344.048828125 runs/s *RESULT rtree_search: 100000= 866.0883178710938 runs/s [ OK ] RTreePerfTest.Search (8092 ms) BUG=674169 R=danakj@chromium.org, dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel Committed: https://crrev.com/b80d44193d48fb38e2fffa7c3f16d89979351371 Cr-Commit-Position: refs/heads/master@{#439686} ==========
Message was sent while issue was closed.
Patchset 4 (id:??) landed as https://crrev.com/b80d44193d48fb38e2fffa7c3f16d89979351371 Cr-Commit-Position: refs/heads/master@{#439686} |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
