-
vmpstr authored
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 Cr-Commit-Position: refs/heads/master@{#439686}
b80d4419
