cc: Change Nodes collection to use base::ContiguousContainer instead of deque.

This patch changes the the underlying structure to be
base::ContiguousContainer. This provides better memory behavior
and impacts performance as demonstrated by the results below.
This is an acceptable change in performance with the benefit
of memory savings.

(N7v2)
Before:
[ RUN      ] RTreePerfTest.Construct
*RESULT rtree_construct: 100= 91842.1953125 runs/s
*RESULT rtree_construct: 1000= 9855.638671875 runs/s
*RESULT rtree_construct: 10000= 747.183837890625 runs/s
*RESULT rtree_construct: 100000= 63.701416015625 runs/s
[       OK ] RTreePerfTest.Construct (8245 ms)
[ RUN      ] RTreePerfTest.Search
*RESULT rtree_search: 100= 363610 runs/s
*RESULT rtree_search: 1000= 97453.4921875 runs/s
*RESULT rtree_search: 10000= 13022.0244140625 runs/s
*RESULT rtree_search: 100000= 848.8214111328125 runs/s
[       OK ] RTreePerfTest.Search (8093 ms)

After:
[ RUN      ] RTreePerfTest.Construct
*RESULT rtree_construct: 100= 74468.8828125 runs/s (-19%)
*RESULT rtree_construct: 1000= 12053.529296875 runs/s (+22%)
*RESULT rtree_construct: 10000= 716.7188720703125 runs/s (-4%)
*RESULT rtree_construct: 100000= 54.01991653442383 runs/s (-16%)
[       OK ] RTreePerfTest.Construct (8182 ms)
[ RUN      ] RTreePerfTest.Search
*RESULT rtree_search: 100= 351755 runs/s
*RESULT rtree_search: 1000= 96155 runs/s
*RESULT rtree_search: 10000= 10232.65625 runs/s
*RESULT rtree_search: 100000= 863.5242309570312 runs/s
[       OK ] RTreePerfTest.Search (8176 ms)

Additionally this changes the union operation to be faster than
gfx::Rect::Union, since there are some assumptions that we can
make. Also, Union shows up as the hottest function on Linux profiles.

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/2570393002
Cr-Commit-Position: refs/heads/master@{#439258}
2 files changed