This CL replaces the edge index data structure, a
TreeMap<S2CellId,TreeSet<Integer>>, with an alternate that is an order of
magnitude smaller and faster. Inspiration for this work is owed to Frank
Warmerdam, who first recognized the performance consequences of the TreeMap as
implemented in Java.
Storing the index this way requires 10 fewer references for all edges A that are
alone in their cell, and 5 fewer references for all edges B that share a cell.
So assuming 64 bits/reference, this saves 80*size(A)+40*size(B) bytes. With the
consideration that A>>B for most large real world polygons, the RAM savings here
are quite significant.
Querying the index this way is also significantly faster. We got the submap of
the tree under the cell and tested the size of the submap, but because the cell
testing starts at the top and therefore the submaps initially enclose most of
the loop's edges, and because size() is a linear operation on a TreeMap's
submap, this made index queries linear on the number of elements instead of the
expected O(log n). The double binary search to find the edges of the query
region is truly O(log N) because size() on a subList() is O(1).
The javatests suite passed. A robust set of measurements was taken against the
old and new algorithms with millions of real GT polygons. The plot of all these
measurements shows quadratic and nearly linear curves for the old and new data
structures, respectively. At the low end, constructing S2Polygons with loops
just big enough to require an edge index takes essentially the same time as
before. Anything above about 5000 vertices is several times faster. And at the
high end, constructing huge country polygons, a process that was taking over a
minute for the bad cases now takes milliseconds.
Incredible find Frank!
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=24623432
1 file changed